What is the maximum value of $$$a + b$$$ when $$$a \cdot b = x$$$?

[submission:1010182111]

Check which direction is optimal for the next 2 steps and why?

• 2 times Right?

• 2 times Down?

• 1 time Right and 1 time Down?

• 1 time Down 1 time Right?

[submission:1010182111]

#include <bits/stdc++.h>
 
using namespace std;
 
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
 
void solve() {
    string s;
    cin >> s;
 
    vector<bool> used(26);
    used[s[0] - 'a'] = true;
    string t(1, s[0]);
 
    int pos = 0;
    for (int i = 1; i < sz(s); i++) {
        if (used[s[i] - 'a']) {
            if (pos > 0 && t[pos - 1] == s[i]) {
                pos--;
            } else if (pos + 1 < sz(t) && t[pos + 1] == s[i]) {
                pos++;
            } else {
                cout << "NO" << endl;
                return;
            }
        } else {
            if (pos == 0) {
                t = s[i] + t;
            } else if (pos == sz(t) - 1) {
                t += s[i];
                pos++;
            } else {
                cout << "NO" << endl;
                return;
            }
        }
        used[s[i] - 'a'] = true;
    }
 
    forn(i, 26) if (!used[i])
        t += char(i + 'a');
    cout << "YES" << endl << t << endl;
}
 
int main() {
    int tc;
    cin >> tc;
 
    forn(i, tc) solve();
}

from math import log2
 
for t in range(int(input())):
    n, m = map(int, input().split())
    c = [0] * 61
    s = 0
    for x in map(int, input().split()):
        c[int(log2(x))] += 1
        s += x
 
    if s < n:
        print(-1)
        continue
 
    i, res = 0, 0
    while i < 60:
        if (1<<i)&n != 0:
            if c[i] > 0:
                c[i] -= 1
            else:
                while i < 60 and c[i] == 0:
                    i += 1
                    res += 1
                c[i] -= 1
                continue
        c[i + 1] += c[i] // 2
        i += 1
 
    print(res)

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
#define x first
#define y second
 
typedef long long li;
typedef pair<int, int> pt;
 
const int INF = int(1e9);
const li INF64 = li(1e18);
 
string s, t;
 
inline bool read() {
    if(!(cin >> s >> t))
        return false;
    for(auto &c : s)
        c -= 'a';
    for(auto &c : t)
        c -= 'a';
    return true;
}
 
vector< vector<int> > nxt;
 
bool calc(const string &a, const string &b) {
    vector< vector<int> > dp(sz(a) + 1, vector<int>(sz(b) + 1, INF));
    dp[0][0] = 0;
    fore(i, 0, sz(a) + 1) fore(j, 0, sz(b) + 1) {
        if(dp[i][j] > sz(s))
            continue;
 
        int len = dp[i][j];
        if(i < sz(a) && nxt[len][a[i]] < INF) {
            dp[i + 1][j] = min(dp[i + 1][j], nxt[len][a[i]] + 1);
        }
        if(j < sz(b) && nxt[len][b[j]] < INF) {
            dp[i][j + 1] = min(dp[i][j + 1], nxt[len][b[j]] + 1);
        }
    }
    return dp[sz(a)][sz(b)] < INF;
}
 
inline void solve() {
    nxt.assign(sz(s) + 1, vector<int>(26, INF));
    for(int i = sz(s) - 1; i >= 0; i--) {
        nxt[i] = nxt[i + 1];
        nxt[i][s[i]] = i;
    }
 
    for(int i = 0; i < sz(t); i++) {
        if(calc(t.substr(0, i), t.substr(i, sz(t)))) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}
 
int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
 
    int tc; cin >> tc;
 
    while(tc--) {
        read();
        solve();
 
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
#define forr(i, r, l) for (int i = int(r) - 1; i >= int(l); --i)
 
typedef pair<int, int> pt;
 
const int M = 310;
const int N = 2000 * 1000 + 13;
 
int n, m, q;
int a[M][M];
 
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
 
bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}
 
int p[M * M], rk[M * M];
 
int getp(int v) {
    return p[v] == v ? v : p[v] = getp(p[v]);
}
 
bool unite(int a, int b) {
    a = getp(a); b = getp(b);
    if (a == b) return false;
    if (rk[a] < rk[b]) swap(a, b);
    p[b] = a;
    rk[a] += rk[b];
    return true;
}
 
int dif[N];
vector<pt> add[N], del[N];
 
void recalc(const vector<pt>& ev, int coeff)  {
    forn(i, n) forn(j, m) a[i][j] = 0;
    forn(i, n * m) p[i] = i, rk[i] = 1;
 
    for (auto it : ev) {
        int cur = 1;
        int x = it.x / m, y = it.x % m;
        a[x][y] = 1;
 
        forn(k, 4) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (in(nx, ny) && a[nx][ny] == 1)
                cur -= unite(nx * m + ny, x * m + y);
        }
 
        dif[it.y] += cur * coeff;
    }
}
 
int main() {
    scanf("%d%d%d", &n, &m, &q);
    int clrs = 1;
    forn(i, q) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        --x; --y;
        if (a[x][y] == c) continue;
        clrs = c + 1;
        add[c].pb(mp(x * m + y, i));
        del[a[x][y]].pb(mp(x * m + y, i));
        a[x][y] = c;
    }
 
    forn(x, n) forn(y, m)
        del[a[x][y]].pb(mp(x * m + y, q));
 
    forn(i, clrs) reverse(all(del[i]));
 
    forn(i, clrs) recalc(add[i], +1);
    forn(i, clrs) recalc(del[i], -1);
 
    int cur = 1;
    forn(i, q) {
        cur += dif[i];
        printf("%d\n", cur);
    }
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 150043;
 
typedef pair<long long, long long> func;
 
func T[4 * N];
bool usedT[4 * N];
 
void clear(int v, int l, int r)
{
    if(!usedT[v]) return;
    usedT[v] = false;
    T[v] = make_pair(0ll, 0ll);
    if(l < r - 1)
    {
        int m = (l + r) / 2;
        clear(v * 2 + 1, l, m);
        clear(v * 2 + 2, m, r);
    }
}
 
long long eval(func f, int x)
{
    return f.first * x + f.second;
}
 
long long get(int v, int l, int r, int x)
{
    long long ans = eval(T[v], x);
    if(l < r - 1)
    {
        int m = (l + r) / 2;
        if(m > x)
            ans = max(ans, get(v * 2 + 1, l, m, x));
        else
            ans = max(ans, get(v * 2 + 2, m, r, x));
    }
    return ans;
}
 
void upd(int v, int l, int r, func f)
{
    usedT[v] = true;
    int m = (l + r) / 2;
    bool need_swap = eval(f, m) > eval(T[v], m);
    if(need_swap)
        swap(T[v], f);
    if(l == r - 1)
        return;
    if(eval(f, l) > eval(T[v], l))
        upd(v * 2 + 1, l, m, f);
    else
        upd(v * 2 + 2, m, r, f);
}
 
long long ans = 0;
 
void update_ans(vector<vector<func> > heads, vector<vector<func> > tails)
{
    int n = heads.size();
    for(int i = 0; i < n; i++)
    {
        for(auto x : heads[i])
            ans = max(ans, get(0, 0, N, x.first) + x.second);
        for(auto x : tails[i])
            upd(0, 0, N, x);
    }
    clear(0, 0, N);
}
 
int a[N];
vector<int> g[N];
int n;
bool used[N];
int siz[N];
 
void dfs1(int x, int p = -1)
{
    if(used[x]) return;
    siz[x] = 1;
    for(auto to : g[x])
    {                    
        if(!used[to] && to != p)
        {
            dfs1(to, x);
            siz[x] += siz[to];
        }
    }
}
 
pair<int, int> c;
int S = 0;
 
void find_centroid(int x, int p = -1)
{
    if(used[x]) return;
    int mx = 0;
    for(auto to : g[x])
    {
        if(!used[to] && to != p)
        {
            find_centroid(to, x);
            mx = max(mx, siz[to]);
        }
    }
    if(p != -1)
        mx = max(mx, S - siz[x]);
    c = min(c, make_pair(mx, x));
}
 
void dfs_heads(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
    if(used[v])
        return;
    cnt++;
    curadd += a[v];
    cursum += curadd;
    sink.push_back(make_pair(cnt, cursum));
    for(auto to : g[v])
        if(to != p)
            dfs_heads(to, v, cnt, cursum, curadd, sink);
}
 
void dfs_tails(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
    if(used[v])
        return;
    cnt++;
    curadd += a[v];
    cursum += a[v] * 1ll * cnt;
    sink.push_back(make_pair(curadd, cursum));
    for(auto to : g[v])
        if(to != p)
            dfs_tails(to, v, cnt, cursum, curadd, sink);
}
 
void centroid(int v)
{
    if(used[v]) return;
    dfs1(v);
    S = siz[v];
    c = make_pair(int(1e9), -1);
    find_centroid(v);
    int C = c.second;
    used[C] = 1;
    vector<vector<func> > heads, tails;
    for(auto to : g[C])
        if(!used[to])
        {
            heads.push_back(vector<func>());
            dfs_heads(to, C, 1, a[C], a[C], heads.back());
            tails.push_back(vector<func>());
            dfs_tails(to, C, 0, 0, 0, tails.back());
        }
    heads.push_back(vector<func>({{1, a[C]}}));
    tails.push_back(vector<func>({{0, 0}}));
    update_ans(heads, tails);
    reverse(heads.begin(), heads.end());
    reverse(tails.begin(), tails.end());
    update_ans(heads, tails);
    for(auto to : g[C])
        centroid(to);
}
 
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);    
    }
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    centroid(0);
    printf("%lld\n", ans);
}