Submission #173537

#	Time	Username	Problem	Language	Result	Execution time	Memory
173537		mosiashvililuka	Bigger segments (IZhO19_segments)	C++14	100 / 100	495 ms	44072 KiB

segments

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,f[500009],i,j,mxf,mxs,pas;
pair <long long, long long> dp[500009];
vector <pair <long long, long long> > v[500009];
int main(){
    scanf("%I64d\n",&a);
    for(i=1; i<=a; i++) scanf("%I64d",&f[i]);
    for(i=1; i<=a; i++) f[i]+=f[i-1];
    scanf("\n");
    mxs=1000000000000000000LL;
    f[a+1]=mxs;
    mxs=0;
    for(b=1; b<=a; b++){
        for(i=0; i<v[b].size(); i++){
            if(mxf<v[b][i].first){
                mxf=v[b][i].first;mxs=v[b][i].second;
            }else{
                if(mxf==v[b][i].first&&mxs<v[b][i].second){
                    mxs=v[b][i].second;
                }
            }
        }
        dp[b].first=1;dp[b].second=f[b];
        if(mxf>dp[b].first){
            dp[b].first=mxf;
            dp[b].second=f[b]-mxs;
        }else{
            if(mxf==dp[b].first&&f[b]-mxs<dp[b].second) dp[b].second=f[b]-mxs;
        }
        c=lower_bound(f+1,f+a+1,dp[b].second+f[b])-f;
        if(c<=a){
//            cout<<b<<" "<<c<<" "<<dp[b].first<<" "<<f[c]<<endl;
            v[c].push_back(make_pair(dp[b].first+1,f[b]));
        }
        if(pas<dp[b].first) pas=dp[b].first;
    }
    cout<<pas;
    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:7:23: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%I64d\n",&a);
                     ~~^
segments.cpp:8:44: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     for(i=1; i<=a; i++) scanf("%I64d",&f[i]);
                                       ~~~~~^
segments.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0; i<v[b].size(); i++){
                  ~^~~~~~~~~~~~
segments.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%I64d\n",&a);
     ~~~~~^~~~~~~~~~~~~~
segments.cpp:8:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=a; i++) scanf("%I64d",&f[i]);
                         ~~~~~^~~~~~~~~~~~~~~
segments.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("\n");
     ~~~~~^~~~~~

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