oj.uz

Submission #167954

# Submission time Handle Problem Language Result Execution time Memory
167954 2019-12-11T03:18:06 Z juggernaut Divide and conquer (IZhO14_divide) C++14
100 / 100
 57 ms 6776 KB 
#include<bits/stdc++.h>
#define int long long int
using namespace std;
struct data{
    int x,g,d;
};
data a[100001];
int n,i,l,r,gold[100001],drive[100001],mx[100002],m,ans;
main(){
    scanf("%lld",&n);
    for(i=1;i<=n;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].g,&a[i].d),gold[i]=gold[i-1]+a[i].g,drive[i]=drive[i-1]+a[i].d,mx[i]=drive[i]-a[i].x;
    for(i=n-1;i>0;i--)mx[i]=max(mx[i+1],mx[i]);
    for(i=1;i<=n;i++){
        l=i,r=n;
        while(l<r){
            m=(l+r+1)>>1;
            if(mx[m]>=drive[i-1]-a[i].x)l=m;
            else r=m-1;
        }
        ans=max(ans,gold[l]-gold[i-1]);
    }
    printf("%lld",ans);
}

Compilation message

divide.cpp:9:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
divide.cpp: In function 'int main()':
divide.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
divide.cpp:11:119: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].g,&a[i].d),gold[i]=gold[i-1]+a[i].g,drive[i]=drive[i-1]+a[i].d,mx[i]=drive[i]-a[i].x;
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 4 ms 760 KB Output is correct
12 Correct 4 ms 632 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 6 ms 1020 KB Output is correct
4 Correct 24 ms 3676 KB Output is correct
5 Correct 28 ms 3976 KB Output is correct
6 Correct 57 ms 6520 KB Output is correct
7 Correct 42 ms 6468 KB Output is correct
8 Correct 43 ms 6520 KB Output is correct
9 Correct 41 ms 6520 KB Output is correct
10 Correct 43 ms 6648 KB Output is correct
11 Correct 48 ms 6776 KB Output is correct
12 Correct 51 ms 6776 KB Output is correct