QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#934826#9614. 分治Str_ywr20 1ms3840kbC++142.6kb2025-03-15 09:53:442025-03-15 09:53:49

Judging History

This is the latest submission verdict.

  • [2025-03-15 09:53:49]
  • Judged
  • Verdict: 20
  • Time: 1ms
  • Memory: 3840kb
  • [2025-03-15 09:53:44]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    } return x * f;
}
const int N = 3e5 + 10, mod = 998244353; const ll inf = 1e18; 
int n; typedef pair<ll,ll> pll;
vector<vector<ll>> f[105]; int id[N], tot;
void ck(ll &x, ll y) {
    if (y > x) x = y;
}
int dfs(int x) {
    if (id[x]) return id[x];
    id[x] = ++tot; int nw = tot; f[nw].resize(x + 1);
    for (int i = 0; i <= x; i++) f[nw][i].resize(i + 2, -inf);
    assert(tot < 100);
    if (x == 1) {
        // f[nw][0] = {0,0}; f[nw][1] = {1,1};
        f[nw][0][0] = 0; f[nw][1][0] = 0; f[nw][1][1] = 1;
        return nw;  
    }
    int ln = (x + 1) >> 1, rn = x >> 1;
    int lc = dfs((x + 1) >> 1); int rc = dfs(x >> 1); 
    vector<vector<ll>> g; g.resize(x + 1);
    for (int i = 0; i <= x; i++) g[i].resize(i + 2, -inf);
    for (int x = 0; x <= ln; x++) {
        ll mx = -inf;
        for (auto v : f[lc][x]) mx = max(mx, v);
        for (int y = 0; y <= rn; y++) { 
            for (int i = 0; i <= y + 1; i++) {
                ck(g[x+y][i], mx + f[rc][y][i]);
            }
        }
    }
    for (int y = 0; y <= rn; y++) {
        ll mx = -inf;
        for (auto v : f[rc][y]) mx = max(mx, v);
        for (int x = 0; x <= ln; x++) { 
            for (int i = 0; i <= x + 1; i++) {
                ck(g[x+y][i], mx + f[lc][x][i]);
            }
        }
    }
    for (int a = 0; a <= x; a++) {
        for (int b = 0; b <= a + 1; b++){
            for (int k = 0; k <= min(a, b); k++) {
                ck(f[nw][a][b], g[a-k][b-k] + b);
            }
        }
    }
    // f[nw][0] = {0,0};
    // for (int i = 0; i <= x; i++) {
    //     for (int j = 0; j <= min(i, ln); j++) {
    //         for (int k = 0; k <= rn && k + j <= i; k++) {
    //             ll mx = max(f[lc][j].second, f[rc][k].second) + i - j - k;
    //             ck(f[nw][i], {f[lc][j].first + f[rc][k].first + mx, mx});
    //         }   
    //     }
    // } assert(f[nw][0].first == 0 && f[nw][0].second == 0);
    return nw;
}
int main() {
    string s; cin >> s;
    for (int i = 0; i < s.size(); i++) {
        n = (n << 1) | (s[i] - '0');
    }
    int rt = dfs(n);
    ll ans = -inf;
    for (int i = 0; i <= n; i++) ck(ans, f[rt][n][i]);
    ans = (ans % mod + mod) % mod;
    cout << ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 3712kb

input:

110

output:

15

result:

ok 1 number(s): "15"

Test #2:

score: 10
Accepted
time: 1ms
memory: 3712kb

input:

101

output:

12

result:

ok 1 number(s): "12"

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #3:

score: 10
Accepted
time: 0ms
memory: 3840kb

input:

111110

output:

198

result:

ok 1 number(s): "198"

Test #4:

score: 10
Accepted
time: 0ms
memory: 3840kb

input:

1001001

output:

253

result:

ok 1 number(s): "253"

Subtask #3:

score: 0
Memory Limit Exceeded

Dependency #2:

100%
Accepted

Test #5:

score: 0
Memory Limit Exceeded

input:

10100011000100111

output:


result:


Subtask #4:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 3584kb

input:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

output:

282173455

result:

wrong answer 1st numbers differ - expected: '412796008', found: '282173455'

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #5:

0%

Subtask #8:

score: 0
Skipped

Dependency #6:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%