QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#651723#7532. Inspection (32 MB ML!)ucup-team3519#WA 1ms5716kbC++172.7kb2024-10-18 17:58:172024-10-18 17:58:18

Judging History

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

  • [2024-10-18 17:58:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5716kb
  • [2024-10-18 17:58:17]
  • 提交

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();
}

详细

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