QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562269 | #7532. Inspection (32 MB ML!) | ucup-team052# | WA | 1ms | 7972kb | C++23 | 5.1kb | 2024-09-13 16:16:16 | 2024-09-13 16:16:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
const int N = 105, B = 101;
vector <pii> res;
ll dp[N][N][N], dp2[N][N][N];
ll s[10005], ans;
int n, k1, l1, k2, l2;
void solve(int l, int r, int k1, int k2) {
// fprintf(stderr, "l = %d, r = %d, k1 = %d, k2 = %d\n", l, r, k1, k2);
if (r - l + 1 <= B) {
for (int i = 0; i <= k1; i++) {
for (int j = 0; j <= k2; j++) dp[0][i][j] = 0;
}
for (int i = l, cur = 1; i <= r; i++, cur++) {
int len = i - l + 1;
assert(cur == len);
for (int i1 = 0; i1 <= k1; i1++) {
for (int i2 = 0; i2 <= k2; i2++) {
dp[cur][i1][i2] = dp[cur - 1][i1][i2];
if (i1 && cur >= l1) dp[cur][i1][i2] = max(dp[cur][i1][i2], dp[cur - l1][i1 - 1][i2] + s[i] - s[i - l1]);
if (i2 && cur >= l2) dp[cur][i1][i2] = max(dp[cur][i1][i2], dp[cur - l2][i1][i2 - 1] + s[i] - s[i - l2]);
}
}
}
int i = r, cur = r - l + 1, i1 = k1, i2 = k2;
while (i1 || i2) {
if (dp[cur][i1][i2] == dp[cur - 1][i1][i2]) --i, --cur;
else if (i1 && cur >= l1 && dp[cur][i1][i2] == dp[cur - l1][i1 - 1][i2] + s[i] - s[i - l1]) {
res.emplace_back(i - l1, i);
i -= l1; cur -= l1; --i1;
} else {
// fprintf(stderr, "i = %d, cur = %d, i - l2 = %d, i1 = %d, i2 = %d\n", i, cur, i - l2, i1, i2);
res.emplace_back(i - l2, i);
i -= l2; cur -= l2; --i2;
}
}
return;
}
for (int _ = 0; _ < B; _++) {
for (int i = 0; i <= k1; i++) {
/*
for (int j = 0; j <= k2; j++) {
dp[0][i][j] = dp2[0][i][j] = 0;
}
*/
memset(dp[_][i], 0, (k2 + 1) * 8);
memset(dp2[_][i], 0, (k2 + 1) * 8);
}
}
int mid = (l + r) >> 1;
int cur = 1, cur1, cur2;
for (int i = l; i <= mid; i++, cur = (cur + 1) % B) {
int pre0 = cur - 1, pre1 = cur - l1, pre2 = cur - l2;
if (pre0 < 0) pre0 += B;
if (pre1 < 0) pre1 += B;
if (pre2 < 0) pre2 += B;
int len = i - l + 1;
for (int i1 = 0; i1 <= k1; i1++) {
for (int i2 = 0; i2 <= k2; i2++) {
dp[cur][i1][i2] = dp[pre0][i1][i2];
if (i1 && len >= l1) dp[cur][i1][i2] = max(dp[cur][i1][i2], dp[pre1][i1 - 1][i2] + s[i] - s[i - l1]);
if (i2 && len >= l2) dp[cur][i1][i2] = max(dp[cur][i1][i2], dp[pre2][i1][i2 - 1] + s[i] - s[i - l2]);
}
}
}
cur = (cur + B - 1) % B;
cur1 = cur; cur = 1;
for (int i = r; i >= mid + 1; i--, cur = (cur + 1) % B) {
int pre0 = cur - 1, pre1 = cur - l1, pre2 = cur - l2;
if (pre0 < 0) pre0 += B;
if (pre1 < 0) pre1 += B;
if (pre2 < 0) pre2 += B;
int len = r - i + 1;
// fprintf(stderr, "cur = %d, pre0 = %d, pre1 = %d, pre2 = %d\n", cur, pre0, pre1, pre2);
for (int i1 = 0; i1 <= k1; i1++) {
for (int i2 = 0; i2 <= k2; i2++) {
dp2[cur][i1][i2] = dp2[pre0][i1][i2];
if (i1 && len >= l1) dp2[cur][i1][i2] = max(dp2[cur][i1][i2], dp2[pre1][i1 - 1][i2] + s[i + l1 - 1] - s[i - 1]);
if (i2 && len >= l2) dp2[cur][i1][i2] = max(dp2[cur][i1][i2], dp2[pre2][i1][i2 - 1] + s[i + l2 - 1] - s[i - 1]);
}
}
}
cur = (cur + B - 1) % B;
cur2 = cur;
ll maxn = -1;
int L = -1, R = -1, lk1 = -1, lk2 = -1, flag = -1;
for (int i1 = 0; i1 <= k1; i1++) {
for (int i2 = 0; i2 <= k2; i2++) {
ll tmp = dp[cur1][i1][i2] + dp2[cur2][k1 - i1][k2 - i2];
if (tmp > maxn) {
maxn = tmp;
lk1 = i1; lk2 = i2;
flag = 0;
}
}
}
for (int i = 1; i <= max(l1, l2) - 1; i++) {
if (i > mid - l + 1) continue;
int pos0 = cur1 - i;
int pos1 = cur2 - (l1 - i);
int pos2 = cur2 - (l2 - i);
if (pos0 < 0) pos0 += B;
if (pos1 < 0) pos1 += B;
if (pos2 < 0) pos2 += B;
int lenr = r - mid;
for (int i1 = 0; i1 <= k1; i1++) {
for (int i2 = 0; i2 <= k2; i2++) {
if (lenr >= l1 - i && i1) {
ll tmp = dp[pos0][i1 - 1][i2] + dp2[pos1][k1 - i1][k2 - i2] + s[mid + l1 - i] - s[mid - i];
if (tmp > maxn) {
maxn = tmp;
L = mid - i; R = mid + l1 - i;
lk1 = i1 - 1; lk2 = i2; flag = 1;
}
}
if (lenr >= l2 - i && i2) {
ll tmp = dp[pos0][i1][i2 - 1] + dp2[pos2][k1 - i1][k2 - i2] + s[mid + l2 - i] - s[mid - i];
// if (tmp == 23) fprintf(stderr, "i = %d, i1 = %d, i2 = %d, %lld %lld %lld\n", i, i1, i2, dp[pos0][i1][i2 - 1], dp2[pos2][k1 - i1][k2 - i2], s[mid + l2 - i] - s[mid - i]);
if (tmp > maxn) {
maxn = tmp;
L = mid - i; R = mid + l2 - i;
lk1 = i1; lk2 = i2 - 1; flag = 2;
}
}
}
}
}
// fprintf(stderr, "maxn = %lld\n", maxn);
assert(flag != -1);
if (flag == 0) {
solve(l, mid, lk1, lk2);
solve(mid + 1, r, k1 - lk1, k2 - lk2);
} else if (flag == 1) {
res.emplace_back(L, R);
solve(l, L, lk1, lk2);
solve(R + 1, r, k1 - lk1 - 1, k2 - lk2);
} else {
res.emplace_back(L, R);
solve(l, L, lk1, lk2);
solve(R + 1, r, k1 - lk1, k2 - lk2 - 1);
}
}
int main() {
cin >> n >> k1 >> l1 >> k2 >> l2;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] += s[i - 1];
}
solve(1, n, k1, k2);
for (auto i : res) ans += s[i.second] - s[i.first];
printf("%lld\n", ans);
printf("%d\n", (int)res.size());
sort(res.begin(), res.end());
for (auto i : res) printf("%d %d\n", i.first, i.second);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7972kb
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 5 4 6 6 8 9 12 14 17 18 20
result:
wrong answer End of interval should be greater than its beginning