QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#315020#7532. Inspection (32 MB ML!)8BQubeWA 5ms8408kbC++203.9kb2024-01-26 18:57:122024-01-26 18:57:14

Judging History

你现在查看的是最新测评结果

  • [2024-01-26 18:57:14]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:8408kb
  • [2024-01-26 18:57:12]
  • 提交

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]