Submission #503405

#	Time	Username	Problem	Language	Result	Execution time	Memory
503405		mosiashvililuka	Bigger segments (IZhO19_segments)	C++14	100 / 100	437 ms	44284 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;
                }
            }*/
            if(mxs<v[b][i].second){
                mxf=v[b][i].first;mxs=v[b][i].second;
            }else{
                if(mxs==v[b][i].second&&mxf<v[b][i].first){
                    mxf=v[b][i].first;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;
        }*/
        if(f[b]-mxs<dp[b].second){
        	dp[b].first=mxf;
            dp[b].second=f[b]-mxs;
		}else{
			if(f[b]-mxs==dp[b].second&&mxf>dp[b].first){
				dp[b].first=mxf;
            	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:16: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
    7 |     scanf("%I64d\n",&a);
      |            ~~~~^    ~~
      |                |    |
      |                int* long long int*
      |            %I64lld
segments.cpp:8:36: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
    8 |     for(i=1; i<=a; i++) scanf("%I64d",&f[i]);
      |                                ~~~~^  ~~~~~
      |                                    |  |
      |                                    |  long long int*
      |                                    int*
      |                                %I64lld
segments.cpp:15:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         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]
    7 |     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]
    8 |     for(i=1; i<=a; i++) scanf("%I64d",&f[i]);
      |                         ~~~~~^~~~~~~~~~~~~~~

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