QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#651723 | #7532. Inspection (32 MB ML!) | ucup-team3519# | WA | 1ms | 5716kb | C++17 | 2.7kb | 2024-10-18 17:58:17 | 2024-10-18 17:58:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define V vector
#define pb push_back
typedef long long LL;
typedef pair<int, int> pi;
#define fi first
#define se second
const int N = 6e6;// 100000000 / 19 + 100
int fr[N];
LL dp[101][101][101];
int id(int i, int j, int k) {
return k + j * 101 + i * (101 * 101);
}
int p3[19];
int get(int i) {
//3^18 - 3^0
//i / 19
int blk = i / 19;
int res = i % 19;
int val = fr[blk] / p3[res] % 3;
return val;
}
void modify(int i, int d) {
int blk = i / 19;
int res = i % 19;
int val = fr[blk] / p3[res] % 3;
assert(val == 0);
fr[blk] += d * p3[res];
}
int prev(int i, int dis) {
return ((i - dis) % 101 + 101) % 101;
}
void solve() {
int n, k1, l1, k2, l2; cin >> n >> k1 >> l1 >> k2 >> l2;
V<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
V<LL> sum(n + 1);
for(int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + a[i];
}
for(int j = 0; j <= k1; j++) {
for(int k = 0; k <= k2; k++) {
dp[0][j][k] = -1e18;
}
}
dp[0][0][0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= k1; j++) {
for(int k = 0; k <= k2; k++) {
LL dp_val = -1e18;
int fr_val = 0;
if(j && i >= l1) {
LL cur_dp_val = dp[prev(i, l1)][j - 1][k] + sum[i] - sum[i - l1];
if(cur_dp_val > dp_val) dp_val = cur_dp_val, fr_val = 1;
}
if(k && i >= l2) {
LL cur_dp_val = dp[prev(i, l2)][j][k - 1] + sum[i] - sum[i - l2];
if(cur_dp_val > dp_val) dp_val = cur_dp_val, fr_val = 2;
}
LL cur_dp_val = dp[prev(i, 1)][j][k];
if(cur_dp_val > dp_val) dp_val = cur_dp_val, fr_val = 0;
dp[i % 101][j][k] = dp_val;
modify(id(i, j, k), fr_val);
}
}
}
cout << dp[n % 101][k1][k2] << endl;
int x = n, y = k1, z = k2;
V<pi> ans;
while(x) {
int cur_type = get(id(x, y, z));
if(cur_type == 0) {
x--;
} else if(cur_type == 1) {
ans.pb({x - k1, x});
x -= k1;
y--;
} else {
ans.pb({x - k2, x});
x -= k2;
z--;
}
}
sort(ans.begin(), ans.end());
for(auto [l, r] : ans) cout << l << " " << r << endl;
assert(x == 0 && y == 0 && z == 0);
}
int main() {
assert(id(10001, 101, 101) / 19 < N);
p3[0] = 1;
for(int i = 1; i <= 18; i++) p3[i] = p3[i - 1] * 3;
ios::sync_with_stdio(0), cin.tie(0);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5716kb
input:
20 2 3 3 2 2 0 2 0 1 2 1 2 1 2 2 2 1 1 2 2 2 1 2 2
output:
22 7 10 10 12 12 15 15 17 17 20
result:
wrong answer The number of intervals of length 3 should be 2, but extra interval found