oj.uz

Submission #1057419

# Submission time Handle Problem Language Result Execution time Memory
1057419 2024-08-13T18:59:17 Z oscar1f Kpart (eJOI21_kpart) C++17
100 / 100
 593 ms 948 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int TAILLE_MAX=1000+5,SOMME_MAX=100*1000+5;
int nbTest,nbVal;
int somCour[TAILLE_MAX],val[TAILLE_MAX],pb[TAILLE_MAX],premUti[SOMME_MAX];
vector<int> rep;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int obj;
    cin>>nbTest;
    for (int itest=0;itest<nbTest;itest++) {
        cin>>nbVal;
        for (int i=1;i<=nbVal;i++) {
            pb[i]=0;
        }
        for (int i=1;i<=nbVal;i++) {
            cin>>val[i];
            somCour[i]=somCour[i-1]+val[i];
        }
        premUti[0]=nbVal;
        for (int i=1;i<=somCour[nbVal]/2;i++) {
            premUti[i]=0;
        }
        for (int i=1;i<=nbVal;i++) {
            for (int j=somCour[nbVal]/2;j>=val[i];j--) {
                premUti[j]=max(premUti[j],min(premUti[j-val[i]],i));
            }
            for (int j=1;j<=i;j++) {
                obj=somCour[i]-somCour[j-1];
                if (obj%2==1 or premUti[obj/2]<j) {
                    pb[i-j+1]=1;
                }
            }
            /*for (int j=0;j<=somCour[nbVal];j++) {
                cout<<premUti[j]<<" ";
            }
            cout<<endl;*/
        }
        rep.clear();
        for (int i=1;i<=nbVal;i++) {
            if (pb[i]==0) {
                rep.push_back(i);
            }
        }
        cout<<rep.size()<<" ";
        for (int i:rep) {
            cout<<i<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 7 ms 532 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 348 KB Output is correct
2 Correct 102 ms 644 KB Output is correct
3 Correct 106 ms 668 KB Output is correct
4 Correct 177 ms 748 KB Output is correct
5 Correct 391 ms 872 KB Output is correct
6 Correct 593 ms 948 KB Output is correct
7 Correct 541 ms 860 KB Output is correct