Submission #681645

#	Time	Username	Problem	Language	Result	Execution time	Memory
681645		Karuk	Bigger segments (IZhO19_segments)	C++14	37 / 100	920 ms	145340 KiB

segments

    #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(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;
    }

Compilation message (stderr)

segments.cpp: In function 'void bin(int, int, int, int, int)':
segments.cpp:11:14: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
   11 |         bool flag=0;
      |              ^~~~

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