oj.uz

Submission #520551

# Submission time Handle Problem Language Result Execution time Memory
520551 2022-01-30T08:55:11 Z krit3379 Divide and conquer (IZhO14_divide) C++17
17 / 100
 1 ms 332 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 100005

long long x[N],g[N],p[N],l,r,mid,ans;

int main(){
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lld %lld %lld",&x[i],&g[i],&p[i]);
        g[i]+=g[i-1];
        p[i]+=p[i-1];
    }
    for(i=1;i<=n;i++){
        l=1,r=i;
        while(l<=r){
            mid=(l+r)/2;
            if(p[i]-p[mid-1]>=x[i]-x[mid])ans=max(ans,g[i]-g[mid-1]),r=mid-1;
            else l=mid+1;
        }
        l=i,r=n;
        while(l<=r){
            mid=(l+r)/2;
            if(p[mid]-p[i-1]>=x[mid]-x[i])ans=max(ans,g[mid]-g[i-1]),l=mid+1;
            else r=mid-1;
        }
    }
    printf("%lld",ans);
    return 0;
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
divide.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         scanf("%lld %lld %lld",&x[i],&g[i],&p[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 292 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 292 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Incorrect 1 ms 332 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 292 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Incorrect 1 ms 332 KB Output isn't correct
16 Halted 0 ms 0 KB -