QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#315020 | #7532. Inspection (32 MB ML!) | 8BQube | WA | 5ms | 8408kb | C++20 | 3.9kb | 2024-01-26 18:57:12 | 2024-01-26 18:57:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back
constexpr int kN = 10010;
constexpr ll kInf = 1e18;
constexpr int kPool = 101;
ll pool[kPool][101][101]; // [][k1][k2];
struct {
int m, k1, k2;
} pi_pool[kPool][101][101];
vector<pii> ans;
void solve(const ll *s, const int n, const int l1, const int l2, int k1, int k2, int pre_n) {
if (n == 0) return;
if (k1 + k2 == 0) return;
// cerr << "call " << n << ' ' << k1 << ' ' << k2 << endl;
if (k1 == 1 && k2 == 0) {
assert(l1 <= n);
int opt = l1;
for (int i = l1; i <= n; ++i) {
if (s[i] - s[i - l1] > s[opt] - s[opt - l1]) {
opt = i;
}
}
ans.emplace_back(pre_n + opt - l1, pre_n + opt);
return;
}
if (k1 == 0 && k2 == 1) {
assert(l2 <= n);
int opt = l2;
for (int i = l2; i <= n; ++i) {
if (s[i] - s[i - l2] > s[opt] - s[opt - l2]) {
opt = i;
}
}
ans.emplace_back(pre_n + opt - l2, pre_n + opt);
return;
}
for (int i = 0; i <= k1; ++i) {
for (int j = 0; j <= k2; ++j) {
pool[0][i][j] = -kInf;
pi_pool[0][i][j].m = -1; // invalid
}
}
pool[0][0][0] = 0;
const int k_divide = (n + k1 + k2) / 2;
for (int m = 1; m <= n; ++m) {
auto dp = pool[m % kPool], dp_prev = pool[(m + kPool - 1) % kPool];
auto pi = pi_pool[m % kPool], pi_prev = pi_pool[(m + kPool - 1) % kPool];
for (int i = 0; i <= k1; ++i) {
for (int j = 0; j <= k2; ++j) {
dp[i][j] = dp_prev[i][j];
pi[i][j] = pi_prev[i][j];
}
}
if (m >= l1) {
auto dp_src = pool[(m - l1) % kPool];
auto pi_src = pi_pool[(m - l1) % kPool];
const ll w = s[m] - s[m - l1];
for (int i = 1; i <= k1; ++i) {
for (int j = 0; j <= k2; ++j) {
ll v = dp_src[i - 1][j] + w;
if (v > dp[i][j]) {
dp[i][j] = v;
pi[i][j] = pi_src[i - 1][j];
}
}
}
}
if (m >= l2) {
auto dp_src = pool[(m - l2) % kPool];
auto pi_src = pi_pool[(m - l2) % kPool];
const ll w = s[m] - s[m - l2];
for (int i = 0; i <= k1; ++i) {
for (int j = 1; j <= k2; ++j) {
ll v = dp_src[i][j - 1] + w;
if (v > dp[i][j]) {
dp[i][j] = v;
pi[i][j] = pi_src[i][j - 1];
}
}
}
}
for (int i = 0; i <= k1; ++i) {
for (int j = 0; j <= k2; ++j) {
if (abs(k_divide - (m + i + j)) > 1) continue;
pi[i][j].m = m;
pi[i][j].k1 = i;
pi[i][j].k2 = j;
}
}
}
auto pi = pi_pool[n % kPool][k1][k2];
/*
cerr << "div at " << pi.m;
cerr << " k1 = " << pi.k1 << '/' << k1 - pi.k1 << ' ';
cerr << " k2 = " << pi.k2 << '/' << k2 - pi.k2 << ' ';
cerr << endl;
*/
solve(s, pi.m, l1, l2, pi.k1, pi.k2, pre_n);
solve(s + pi.m, n - pi.m, l1, l2, k1 - pi.k1, k2 - pi.k2, pre_n + pi.m);
}
int a[kN];
ll s[kN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, k1, l1, k2, l2;
cin >> n >> k1 >> l1 >> k2 >> l2;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
solve(s, n, l1, l2, k1, k2, 0);
ll c = 0;
for (auto &p : ans) c = c + s[p.second] - s[p.first];
cout << c << '\n';
for (auto &p : ans) cout << p.first << ' ' << p.second << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3936kb
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 4 6 6 8 9 12 14 17 18 20
result:
ok Sum = 22
Test #2:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
25 1 5 1 10 30 8 87 61 66 75 86 3 14 23 56 36 60 23 32 65 49 61 11 50 98 91 36 12 85
output:
933 2 7 15 25
result:
ok Sum = 933
Test #3:
score: 0
Accepted
time: 1ms
memory: 4384kb
input:
50 3 3 3 5 19 54 97 19 24 82 0 57 88 32 95 62 60 52 75 21 73 38 11 29 98 8 39 76 94 90 63 81 48 55 64 34 28 27 72 73 70 28 75 76 84 14 15 29 82 46 36 55 47 83
output:
1659 1 6 10 15 23 28 34 37 38 41 47 50
result:
ok Sum = 1659
Test #4:
score: 0
Accepted
time: 0ms
memory: 8408kb
input:
100 20 1 25 2 980 361 796 376 660 459 30 116 265 564 904 831 111 427 376 848 291 126 983 411 272 596 53 757 459 340 901 182 263 595 548 471 699 450 117 63 383 17 45 967 406 858 72 212 356 598 757 70 658 310 424 100 772 505 767 239 368 793 557 574 103 175 213 313 366 24 444 690 599 106 881 224 737 46...
output:
40914 0 2 2 4 4 6 8 10 10 12 13 15 15 17 18 20 20 22 23 25 25 27 28 30 30 32 32 34 36 37 39 41 41 42 44 46 46 47 48 50 50 51 52 54 54 55 56 58 58 60 63 65 66 68 68 69 70 71 72 74 77 79 79 81 82 83 83 84 84 85 86 87 87 88 88 89 90 91 91 92 92 93 93 94 94 95 97 98 99 100
result:
ok Sum = 40914
Test #5:
score: -100
Wrong Answer
time: 5ms
memory: 5928kb
input:
1000 7 7 10 10 1098 8117 3620 2772 168 7954 2367 2555 47 6780 3543 6578 3279 429 4574 1131 7204 247 4804 7522 6613 7478 137 9519 6242 672 7201 7048 2841 643 1026 5669 7345 665 4017 5513 7648 3792 552 1340 1353 9905 9339 10000 9312 2808 6614 6770 1668 263 5684 6018 3876 6349 4838 1611 7457 4651 9362 ...
output:
140206625780685 -15 -8 41 48 71 81 137 144 224 234 237 244 416 426 447 457 495 502 533 540 564 574 726 733 780 790 790 800 800 810 853 863 885 895
result:
wrong answer Integer parameter [name=L0] equals to -15, violates the range [0, 1000]