Submission #520551

#	Time	Username	Problem	Language	Result	Execution time	Memory
520551		krit3379	Divide and conquer (IZhO14_divide)	C++17	17 / 100	1 ms	332 KiB

divide

#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 (stderr)

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 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52