oj.uz

Submission #173587

# Submission time Handle Problem Language Result Execution time Memory
173587 2020-01-04T16:45:54 Z juggernaut Bigger segments (IZhO19_segments) C++14
0 / 100
 3 ms 1144 KB 
//Just try and the idea will come
#include<bits/stdc++.h>
#define int long long int
#define fr first
#define sc second
using namespace std;
int pref[500001],i,n,l,r,m,sp[500001][20],logs[500001],j;
pair<int,int>dp[500001];
int get(int l,int r){
    int len=logs[r-l+1];
    return min(sp[l][len],sp[r-(1ll<<len)+1][len]);
}
main(){
    for(i=2;i<100001;i++)logs[i]=logs[i>>1]+1;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&pref[i]);
        pref[i]+=pref[i-1];
    }
    for(i=1;i<=n;i++){
        l=0,r=i-1;
        while(l<r){
            m=(l+r+1)>>1;
            if(pref[i]>=get(m,i-1))l=m;
            else r=m-1;
        }
        dp[i]={dp[l].fr+1,pref[i]-pref[l]};
        //update(1,0,n,i,dp[i].sc+pref[i]);
        j=1;
        sp[i][0]=dp[i].sc+pref[i];
        while(i-(1ll<<j)+1>0){
            sp[i-(1ll<<j)+1][j]=min(sp[i-(1ll<<j)+1][j],dp[i].sc+pref[i]);
            j++;
        }
    }
    printf("%lld",dp[n].fr);
}

Compilation message

segments.cpp:13:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
segments.cpp: In function 'int main()':
segments.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
segments.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&pref[i]);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -