oj.uz

Submission #173534

# Submission time Handle Problem Language Result Execution time Memory
173534 2020-01-04T14:07:29 Z mosiashvililuka Bigger segments (IZhO19_segments) C++14
0 / 100
 15 ms 12124 KB 
#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;
    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=mxs;
        }else{
            if(mxf==dp[b].first&&mxs<dp[b].second) dp[b].second=mxs;
        }
        c=lower_bound(f+1,f+a+1,dp[b].second+f[b])-f;
        if(c<=a){
            v[c].push_back(make_pair(dp[b].first+1,dp[b].second));
        }
        if(pas<dp[b].first) pas=dp[b].first;
    }
    cout<<pas;
    return 0;
}

Compilation message

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:14: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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12124 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 12 ms 12024 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 15 ms 12024 KB Output is correct
6 Incorrect 12 ms 12028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12124 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 12 ms 12024 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 15 ms 12024 KB Output is correct
6 Incorrect 12 ms 12028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12124 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 12 ms 12024 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 15 ms 12024 KB Output is correct
6 Incorrect 12 ms 12028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12124 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 12 ms 12024 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 15 ms 12024 KB Output is correct
6 Incorrect 12 ms 12028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12124 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct
3 Correct 12 ms 12024 KB Output is correct
4 Correct 12 ms 12024 KB Output is correct
5 Correct 15 ms 12024 KB Output is correct
6 Incorrect 12 ms 12028 KB Output isn't correct
7 Halted 0 ms 0 KB -