Submission #1057419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057419		oscar1f	Kpart (eJOI21_kpart)	C++17	100 / 100	593 ms	948 KiB

Main

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70