QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#934826 | #9614. 分治 | Str_ywr | 20 | 1ms | 3840kb | C++14 | 2.6kb | 2025-03-15 09:53:44 | 2025-03-15 09:53:49 |
Judging History
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%