Submission #40523

#	Time	Username	Problem	Language	Result	Execution time	Memory
40523		Pajaraja	Divide and conquer (IZhO14_divide)	C++14	100 / 100	61 ms	20548 KiB

divide

#include <bits/stdc++.h>
using namespace std;
long long x[100007],e[100007],p[100007],g[100007],maxl[100007],pg[100007];
int binarna(int l, int r,long long val)
{
	if(l==r) return l;
	int s=(l+r+1)/2;
	if(maxl[s]>=val) return binarna(s,r,val);
	return binarna(l,s-1,val);
}
int main()
{
	int n;
	long long sol=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&g[i],&e[i]);
	for(int i=1;i<=n;i++) p[i]=p[i-1]+e[i];
	for(int i=1;i<=n;i++) pg[i]=pg[i-1]+g[i];
    maxl[n+1]=-1000000000;
	for(int i=n;i>0;i--) maxl[i]=max(maxl[i+1],p[i]-x[i]);
	for(int i=1;i<=n;i++)
	{
		int t=binarna(1,n,p[i-1]-x[i]);
		sol=max(sol,pg[t]-pg[i-1]);
	}
	printf("%lld",sol);
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:16:56: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&g[i],&e[i]);
                                                        ^
divide.cpp:16:56: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
divide.cpp:16:56: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
divide.cpp:15:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
divide.cpp:16:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&g[i],&e[i]);
                                                         ^

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