oj.uz

Submission #40522

# Submission time Handle Problem Language Result Execution time Memory
40522 2018-02-03T18:56:38 Z Pajaraja Divide and conquer (IZhO14_divide) C++14
17 / 100
 30 ms 5940 KB 
#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("%d",sol);
}

Compilation message

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:26:17: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  printf("%d",sol);
                 ^
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.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 560 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 560 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 560 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 2 ms 688 KB Output is correct
10 Correct 2 ms 688 KB Output is correct
11 Correct 2 ms 688 KB Output is correct
12 Correct 2 ms 688 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 688 KB Output is correct
2 Correct 2 ms 688 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 2 ms 688 KB Output is correct
5 Incorrect 2 ms 704 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1004 KB Output is correct
2 Correct 5 ms 1384 KB Output is correct
3 Correct 6 ms 1612 KB Output is correct
4 Correct 30 ms 4544 KB Output is correct
5 Incorrect 30 ms 5940 KB Output isn't correct
6 Halted 0 ms 0 KB -