QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#240659#4931. Comic BingeNYCU_gAwr_gurA#WA 1ms4600kbC++202.0kb2023-11-05 17:22:042023-11-05 17:22:05

Judging History

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

  • [2023-11-05 17:22:05]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4600kb
  • [2023-11-05 17:22:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define fast
#else
#define fast cin.tie(0)->sync_with_stdio(0)
#define cerr if(1);else cerr
#define endl '\n'
#endif
#define _ <<' '<<
#define ALL(v) v.begin(),v.end()
#define ft first
#define sd second

using ll = long long;
using ld = long double;
using pii = pair<int,int>;

constexpr int MAXN = 1000;
constexpr int MAXB = 10;
constexpr int MAXT = MAXB * MAXN;

void chmax(auto& a, auto b) {
    if (a < b) a = b;
}

signed main() {
    fast;

    int n;
    cin >> n;
    vector<int> A(n+1), B(n+1);
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int i = 0; i < n; i++) cin >> B[i];

    int T = accumulate(ALL(B), 0);
    vector<vector<int>> dp(n+1, vector<int>(T+1,-1));
    vector<vector<int>> page(n+1, vector<int>(T+1,0));
    vector<vector<bool>> can(n+1, vector<bool>(T+1,false));
    can[0][0] = true;

    for (int i = 0; i < n; i++) {
        for (int t = 0; t < T; t++) if (can[i][t]) {
            int tt = t + B[i];
            for (int ii = i+1; ii <= i+2 and ii <= n; ii++) {
                int rt = B[i] - page[i][t];
                int j = dp[i][t];
                while (rt >= 0 and j+1 < ii)
                    rt -= A[++j];
                can[ii][tt] = true;
                dp[ii][tt] = j;
                page[ii][tt] = max(-rt, 0);
            }
        }
    }

    for (int i = 0; i <= n; i++) {
        cerr _ "i =" _ i _ endl;
        for (int t = 0; t <= T; t++)
            cerr << can[i][t] << " \n"[t==T];
        for (int t = 0; t <= T; t++)
            cerr << dp[i][t] << " \n"[t==T];
        for (int t = 0; t <= T; t++)
            cerr << page[i][t] << " \n"[t==T];
    }

    vector<int> sA(n+1);
    sA[n] = 0;
    for (int i = n; i > 0; i--)
        sA[i-1] = sA[i] + A[i-1];

    int ans = 1e9;
    for (int t = 0; t <= T; t++) if (can[n][t]) {
        int x = t + page[n][t] + sA[dp[n][t]];
        ans = min(ans, x);
        cerr _ t _ x _ page[n][t] _ dp[n][t] _ sA[dp[n][t]+1] _ endl;
    }
    cout << ans << endl;

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3608kb

input:

6
3 1 1 1 1 2
1 5 3 3 7 4

output:

13

result:

ok single line: '13'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

2
2 1
1 1

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

1
1
1

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 4600kb

input:

161
146 662 336 441 626 77 362 697 911 248 879 40 435 60 518 62 475 908 185 740 435 899 188 673 716 529 524 305 321 998 4 363 598 471 650 379 6 980 971 175 664 328 294 681 201 64 926 608 310 478 404 284 634 239 891 515 433 368 929 457 593 338 432 971 593 134 355 97 658 344 653 592 822 660 403 398 38...

output:

80914

result:

wrong answer 1st lines differ - expected: '80587', found: '80914'