QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#674146#5303. No Bug No GameMIS_T__WA 48ms3852kbC++231.2kb2024-10-25 14:14:132024-10-25 14:14:13

Judging History

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

  • [2024-10-25 14:14:13]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:3852kb
  • [2024-10-25 14:14:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    int n,k;
    cin >> n >> k;
    vector w(n,vector<int>(1));
    i64 ans = 0;
    for ( int i = 0 ; i < n ; i++ ) {
        cin >> w[i][0];
        ans += w[i][0];
        for ( int j = 0 ; j < w[i][0] ; j++ ) {
            int x;
            cin >> x;
            w[i].emplace_back(x);
        }
    }
    vector dp(2,vector<i64>(2*k+2));
    // 0, k, k+1, 2k+1;
    int cur = 0;
    for ( int i = 0 ; i < n ; i++ ) {
        cur ^= 1;
        for ( int j = 1 ; j <= w[i][0] ; j++ ) {
            for ( int z = k ; z >= 0 ; z-- ) {
                if ( z < j ) break;
                if ( j != w[i][0] ) {
                    dp[cur][k+1+z] = max(dp[cur^1][z-j]+w[i][j],dp[cur][k+1+z]);
                } else {
                    dp[cur][z] = max(dp[cur^1][z-j],dp[cur][z]);
                }
            }
        }
        for ( int j = 0 ; j < 2*k+2 ; j++ ) {
            dp[cur^1][j] = 0;
        }
    }
    i64 mx = 0;
    for ( int j = 0 ; j < 2*k+2 ; j++ ) {
        mx = max(mx,dp[cur][j]);
    }
    cout << ans+mx << '\n';
}
int main() {
    int T = 1;
    // cin >> T;
    while ( T-- ) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 5
2 1 3
2 1 1
2 3 1
2 1 3

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: -100
Wrong Answer
time: 48ms
memory: 3852kb

input:

3000 3000
10 70562 30723 79371 82224 63977 3362 26909 96449 48163 66159
4 18007 33590 80674 91139
4 10304 31694 70745 50656
10 63090 17226 13187 73881 38137 15237 55750 82751 75854 39658
8 95640 66120 87735 36388 44046 92415 6952 94772
9 60565 27904 98726 87052 35768 25453 14563 34273 92501
10 66332...

output:

86752

result:

wrong answer 1st numbers differ - expected: '68279788', found: '86752'