oj.uz

Submission #170738

# Submission time Handle Problem Language Result Execution time Memory
170738 2019-12-26T08:52:11 Z juggernaut Divide and conquer (IZhO14_divide) C++14
100 / 100
 57 ms 8028 KB 
//Just try and the idea will come!
#include<bits/stdc++.h>
#define int long long int
using namespace std;
struct data{
    int x,g,d;
};
data a[100001];
int n,i,drive[100001],gold[100001],vec[100001],res,l,r,m;
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;
        vec[i]=drive[i]-a[i].x;
    }
    for(i=n-1;i>0;i--)vec[i]=max(vec[i],vec[i+1]);
    for(i=1;i<=n;i++){
        l=i;
        r=n;
        while(l<r){
            m=(l+r+1)>>1;
            if(vec[m]>=drive[i-1]-a[i].x)l=m;
            else r=m-1;
        }
        res=max(res,gold[r]-gold[i-1]);
    }
    printf("%lld",res);
}

Compilation message

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

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 380 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 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 380 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 13 ms 632 KB Output is correct
12 Correct 5 ms 504 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 6 ms 760 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 24 ms 2680 KB Output is correct
5 Correct 28 ms 3960 KB Output is correct
6 Correct 57 ms 8028 KB Output is correct
7 Correct 42 ms 6776 KB Output is correct
8 Correct 43 ms 6776 KB Output is correct
9 Correct 41 ms 6648 KB Output is correct
10 Correct 43 ms 6688 KB Output is correct
11 Correct 48 ms 7128 KB Output is correct
12 Correct 51 ms 7288 KB Output is correct