Submission #168012

#	Time	Username	Problem	Language	Result	Execution time	Memory
168012		GioChkhaidze	Divide and conquer (IZhO14_divide)	C++14	100 / 100	55 ms	5288 KiB

divide

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
ll n,x[N],g[N],d[N],M[N],ans;
main () {
	scanf("%lld",&n);
	
	for (int i=1; i<=n; i++) {
		scanf("%lld%lld%lld",&x[i],&g[i],&d[i]);
		g[i]+=g[i-1];
		d[i]+=d[i-1];
		M[i]=d[i]-x[i];
	}
	
	M[n+1]=-1e18;
	for (int i=n; i>=1; i--)
		M[i]=max(M[i],M[i+1]);
		
	for (int i=1; i<=n; i++) {
		ll c=d[i-1]-x[i],l=i,r=n,mid,res;
		
		while (l<=r) {
			mid=(l+r)/2;
			if (c<=M[mid]) { res=mid; l=mid+1; }
						else r=mid-1;
		}
		
		ans=max(ans,g[res]-g[i-1]);
	}
	
	printf("%lld\n",ans);
}

Compilation message (stderr)

divide.cpp:6:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
divide.cpp: In function 'int main()':
divide.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
divide.cpp:10:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&x[i],&g[i],&d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp:29:20: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ans=max(ans,g[res]-g[i-1]);
               ~~~~~^

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52