QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#275562 | #5303. No Bug No Game | chitoge# | WA | 1ms | 3444kb | C++20 | 1.8kb | 2023-12-04 20:36:36 | 2023-12-04 20:36:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n , k;
cin >> n >> k;
vector<vector<int> > mat(n);
vector<ll> value(n);
int mx = 0;
ll sum = 0;
for(auto &it : mat) {
int x;
cin >> x;
mx += x;
it.resize(x);
for(auto &v : it) cin >> v , sum += v;
}
for(int i = 0 ; i < n ; ++i) {
ll s = 0;
for(auto it : mat[i]) s += it;
value[i] = s;
}
vector<ll> dp1(k + 1);
vector<ll> va(n + 3);
vector<int> pos(n + 3);
auto getpos = [&](vector<ll> &dp) {
if(dp[k] == 0) return 0;
int w = 0;
for(int i = k ; i >= 0 ; --i) {
if(i != 0) {
if(dp1[i] != dp1[i - 1]) {
w = i;
break;
}
}
}
return w;
};
for(int i = n - 1 ; i >= 0 ; --i) {
ll w = value[i];
int v = mat[i].size();
for(int j = k ; j >= v ; --j) {
dp1[j] = max(dp1[j] , dp1[j - v] + w);
}
va[i] = dp1[k];
pos[i] = getpos(dp1);
}
ll ans = dp1[k];
dp1.assign(k + 1 , 0ll);
for(int i = 0 ; i < n ; ++i) {
ll w = value[i];
int v = mat[i].size();
int p = getpos(dp1);
int x = (k - (p + pos[i + 1])) - v;
//cerr << i << ' ' << va[i + 1] << endl;
if(x < 0) {
//cerr << i << ' ' << x << ' ' << mat[i][abs(x) - 1] << endl;
ans = max(ans , dp1[k] + va[i + 1] + mat[i][abs(x) - 1]);
}
for(int j = k ; j >= v ; --j) {
dp1[j] = max(dp1[j] , dp1[j - v] + w);
}
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3444kb
input:
4 5 2 1 3 2 1 1 2 3 1 2 1 3
output:
12
result:
wrong answer 1st numbers differ - expected: '9', found: '12'