Submission #1107548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107548		vjudge1	Kpart (eJOI21_kpart)	C++17	0 / 100	1 ms	592 KiB

Main

#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+5;
const int inf=1e9;
const int mod=1e9+7;
const int N1=1e5+25;
vector<int>v;
vector<int>v1;
struct edge{
    int v,time;
};
int dp[N1];
int n,m;
int dp1[N];
signed main(){
 //   freopen("input.txt", "r", stdin);
   // freopen("output.txt", "w", stdout);
    boost;
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        v.push_back(0);
        v1.push_back(0);
        int cnt1=0;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            cnt1+=x;
            v.push_back(x);
            v1.push_back(cnt1);
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=N-1;j>v[i];j--){
                dp[j]=max(dp[j],dp[j-v[i]]);
            }
            dp[v[i]]=i;
            for(int j=2;j<=i;j++){
                int cnt=v1[i]-v1[i-j];
                if(dp[cnt/2]<=i-j||cnt%2==1){
                    dp1[j]=1;
                }
            }
        }
        cnt=0;
        for(int i=2;i<=n;i++){
            if(dp1[i]==0){
                cnt++;
            }
        }
        cout<<cnt<<" ";
        for(int i=2;i<=n;i++){
            if(dp1[i]==0){
                cout<<i<<" ";
            }
            dp1[i]=0;
        }
        for(int i=0;i<=N;i++){
            dp[i]=0;
        }
        cout<<"\n";
        v.clear();
        v1.clear();
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:63:18: warning: iteration 100025 invokes undefined behavior [-Waggressive-loop-optimizations]
   63 |             dp[i]=0;
      |             ~~~~~^~
Main.cpp:62:22: note: within this loop
   62 |         for(int i=0;i<=N;i++){
      |                     ~^~~
Main.cpp:63:18: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [400100, 800023] is out of the bounds [0, 400100] of object 'dp' with type 'int [100025]' [-Warray-bounds]
   63 |             dp[i]=0;
      |             ~~~~~^~
Main.cpp:14:5: note: 'dp' declared here
   14 | int dp[N1];
      |     ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70