oj.uz

Submission #91050

# Submission time Handle Problem Language Result Execution time Memory
91050 2018-12-26T04:10:15 Z YottaByte Divide and conquer (IZhO14_divide) C++14
48 / 100
 1000 ms 3348 KB 
#include <stdio.h>
using namespace std;

const int N = 1e5 + 1;

#define ll long long
#define int long long
#define ok puts("OK");
int n, x[N], g[N], e[N];

inline bool check(ll mid)
{
	int l = 1, r = 1;
	
	ll genergy = e[l];
	ll lenergy = 0;
	ll ggold = g[l];
	for(int i = 1; i <= n; i++)
	{
		ggold = 0;
		lenergy = 0;
		genergy = 0;
		for(int j = i; j <= n; j++)
		{
			lenergy = x[j] - x[i];
			ggold += g[j];
			genergy += e[j];
			if(genergy >= lenergy && ggold >= mid) return true;
		}
	}
	return false;
}

main()
{
	ll maxg = 0;
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++)
		scanf("%lld %lld %lld", &x[i], &g[i], &e[i]), maxg += g[i];
	
	ll l = 0, r = maxg + 1;
	while(r - l > 1)
	{
		ll mid = l + r >> 1ll;
		if(check(mid)) l = mid;
		else r = mid;
		//puts("");
	}
	
	printf("%lld", l);
}
/*
4
0 5 1
1 7 2
4 4 1
7 15 1

2
0 4 1
3 5 1

4
0 5 1
1 2 0
2 2 0
3 7 7
*/

	//while(l <= r)
	//{
		//lenergy = x[r] - x[l];
		////printf("Gold: %lld NeedG: %lld EnergyL: %lld EnergyG: %lld L: %d R: %d",
		              ////ggold,       mid,        lenergy,      genergy,  l,    r);
		////puts("");
		//if(lenergy <= genergy && ggold >= mid)
			//return true;
		
		//if(l == n && r == n)
			//return false;
		//if(lenergy <= genergy && r < n)
		//{
			//r++;
			//ggold += g[r];
			//genergy += e[r];
		//}
		//else
		//{
			//ggold -= g[l];
			//genergy -= e[l];
			//l++;
		//}
	//}

Compilation message

divide.cpp: In function 'bool check(long long int)':
divide.cpp:13:13: warning: unused variable 'r' [-Wunused-variable]
  int l = 1, r = 1;
             ^
divide.cpp: At global scope:
divide.cpp:34:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
divide.cpp: In function 'int main()':
divide.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid = l + r >> 1ll;
            ~~^~~
divide.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
divide.cpp:39:47: 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], &e[i]), maxg += g[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 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 484 KB Output is correct
8 Correct 2 ms 484 KB Output is correct
9 Correct 2 ms 584 KB Output is correct
10 Correct 5 ms 584 KB Output is correct
11 Correct 2 ms 584 KB Output is correct
12 Correct 2 ms 584 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 584 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 3 ms 584 KB Output is correct
4 Correct 5 ms 584 KB Output is correct
5 Correct 9 ms 596 KB Output is correct
6 Correct 2 ms 752 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 2 ms 752 KB Output is correct
9 Correct 13 ms 752 KB Output is correct
10 Correct 39 ms 756 KB Output is correct
11 Correct 329 ms 924 KB Output is correct
12 Correct 417 ms 1032 KB Output is correct

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1032 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 5 ms 1144 KB Output is correct
4 Correct 19 ms 2168 KB Output is correct
5 Correct 24 ms 2180 KB Output is correct
6 Correct 46 ms 3348 KB Output is correct
7 Correct 34 ms 3348 KB Output is correct
8 Correct 35 ms 3348 KB Output is correct
9 Correct 33 ms 3348 KB Output is correct
10 Execution timed out 1071 ms 3348 KB Time limit exceeded
11 Halted 0 ms 0 KB -