Submission #681637

#TimeUsernameProblemLanguageResultExecution timeMemory
681637KarukBigger segments (IZhO19_segments)C++14
0 / 100
1 ms468 KiB
#include<bits/stdc++.h> using namespace std; long long sum[3001][3001]; long long minsc[3001][3004]; const long long MAX=1e17; void bin(int begnum,int ennum,int begfrom,int endfrom,int cur) { if(begnum>ennum)return; int mid=(begnum+ennum)/2; int ind; int indmax=endfrom; bool flag=0; for(ind=begfrom;ind<=endfrom;ind++) { if(sum[ind+1][cur]>=minsc[ind][mid-1] && sum[ind+1][cur]<minsc[cur][mid]) { minsc[cur][mid]=sum[ind+1][cur]; indmax=ind; flag=1; } } if(begnum==ennum)return; bin(begnum,mid,begfrom,indmax,cur); bin(mid+1,ennum,indmax,endfrom,cur); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n;cin>>n; long long a[n]; for(int i=0;i<n;i++)cin>>a[i]; for(int i=0;i<n;i++) { long long su=0; for(int j=i;j<n;j++) { su+=a[j]; sum[i][j]=su; } } for(int i=0;i<n;i++) { for(int j=0;j<=n;j++) { minsc[i][j]=MAX; } } int ans=1; for(int i=0;i<n;i++) { minsc[i][1]=sum[0][i]; if(i==0)continue; bin(2,i+1,0,i-1,i); for(int j=1;j<=i;j++) { if(minsc[i][j]!=MAX)ans=max(ans,j); } } cout<<ans; return 0; }

Compilation message (stderr)

segments.cpp: In function 'void bin(int, int, int, int, int)':
segments.cpp:11:10: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
   11 |     bool flag=0;
      |          ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...