oj.uz

Submission #90510

# Submission time Handle Problem Language Result Execution time Memory
90510 2018-12-22T04:43:41 Z daniel_02 Divide and conquer (IZhO14_divide) C++14
100 / 100
 58 ms 24508 KB 
#include <bits/stdc++.h>

#define fr first
#define pb push_back
#define sc second
#define ll long long

using namespace std;

const int N = 1e5 + 7;;
const ll inf = 1e18 + 7;

pair<int, pair<int, int>> a[N];
ll pre[N], prg[N], ans;
ll t[N * 4];

void upd(int v, int tl, int tr, int pos)
{	
	if (tl == tr)
	{
		t[v] = pre[pos - 1] - a[pos].fr;
	}
	else
	{
		int mid = (tl + tr) >> 1;
		
		if (mid >= pos)
			upd(v + v, tl, mid, pos);
		else
			upd(v + v + 1, mid + 1, tr, pos);
			
		t[v] = min(t[v + v], t[v + v + 1]);
	}
}
int get(int v, int tl, int tr, int pos)
{
	if (tl == tr)
	{
		return tl;
	}
	else
	{
		int mid = (tl + tr) >> 1;
		
		if (t[v + v] <= pre[pos] - a[pos].fr)
			return get(v + v, tl, mid, pos);
		else
			return get(v + v + 1, mid + 1, tr, pos);
	}
}
main()
{
	int n;
	
	cin >> n;
	
	for (int i = 0; i < N * 4; i++)
		t[i] = inf;
	
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d%d", &a[i].fr, &a[i].sc.fr, &a[i].sc.sc);
		pre[i] = pre[i - 1] + a[i].sc.sc;
		prg[i] = prg[i - 1] + a[i].sc.fr;
	}
	
	for (int i = 1; i <= n; i++)
	{
		upd(1, 1, n, i);
		ans = max(ans, prg[i] - prg[get(1, 1, n, i) - 1]);
	}
	cout << ans;
}

Compilation message

divide.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
divide.cpp: In function 'int main()':
divide.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a[i].fr, &a[i].sc.fr, &a[i].sc.sc);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 3 ms 3584 KB Output is correct
3 Correct 3 ms 3584 KB Output is correct
4 Correct 3 ms 3584 KB Output is correct
5 Correct 4 ms 3584 KB Output is correct
6 Correct 6 ms 3584 KB Output is correct
7 Correct 4 ms 3584 KB Output is correct
8 Correct 4 ms 3612 KB Output is correct
9 Correct 4 ms 3616 KB Output is correct
10 Correct 4 ms 3784 KB Output is correct
11 Correct 3 ms 3784 KB Output is correct
12 Correct 4 ms 3784 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3784 KB Output is correct
2 Correct 4 ms 3784 KB Output is correct
3 Correct 5 ms 3784 KB Output is correct
4 Correct 4 ms 3784 KB Output is correct
5 Correct 5 ms 3784 KB Output is correct
6 Correct 5 ms 3940 KB Output is correct
7 Correct 5 ms 3940 KB Output is correct
8 Correct 5 ms 3940 KB Output is correct
9 Correct 5 ms 4016 KB Output is correct
10 Correct 5 ms 4044 KB Output is correct
11 Correct 7 ms 4208 KB Output is correct
12 Correct 7 ms 4320 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4436 KB Output is correct
2 Correct 8 ms 4628 KB Output is correct
3 Correct 8 ms 4880 KB Output is correct
4 Correct 27 ms 6996 KB Output is correct
5 Correct 31 ms 8372 KB Output is correct
6 Correct 58 ms 12716 KB Output is correct
7 Correct 47 ms 14452 KB Output is correct
8 Correct 47 ms 16384 KB Output is correct
9 Correct 45 ms 18180 KB Output is correct
10 Correct 48 ms 19908 KB Output is correct
11 Correct 55 ms 22280 KB Output is correct
12 Correct 55 ms 24508 KB Output is correct