QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#674146 | #5303. No Bug No Game | MIS_T__ | WA | 48ms | 3852kb | C++23 | 1.2kb | 2024-10-25 14:14:13 | 2024-10-25 14:14:13 |
Judging History
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();
}
}
详细
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'