QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#275562#5303. No Bug No Gamechitoge#WA 1ms3444kbC++201.8kb2023-12-04 20:36:362023-12-04 20:36:37

Judging History

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

  • [2023-12-04 20:36:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3444kb
  • [2023-12-04 20:36:36]
  • 提交

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'