Submission #681650

#	Time	Username	Problem	Language	Result	Execution time	Memory
681650		Karuk	Bigger segments (IZhO19_segments)	C++14	37 / 100	849 ms	144900 KiB

segments

#include<bits/stdc++.h>
using namespace std;
long long sum[3001][3001];
long long minsc[3001][3006];
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;
    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;
        }
    }
    if(begnum==ennum)return;
    if(mid!=begnum)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+5];
    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(1,i+1,0,i-1,i);
        for(int j=1;j<=i+1;j++) {
            if(minsc[i][j]!=MAX)ans=max(ans,j);
        }
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27