oj.uz

Submission #38481

# Submission time Handle Problem Language Result Execution time Memory
38481 2018-01-04T09:56:25 Z 14kg Divide and conquer (IZhO14_divide) C++11
100 / 100
 66 ms 5408 KB 
#include <stdio.h>
#include <algorithm>
#define N 100001
#define INF 999999999999999999
#define LL long long
#define max2(x,y) (x>y?x:y)

using namespace std;
struct DNC {
	int w, g, e;
} in[N];
int n, list_len;
LL out;
pair<LL, LL> d[N];
pair<LL, int> list[N];

int search(long long num) {
	pair<LL, int> temp = { num,0 };
	pair<LL, int> *w = upper_bound(list + 1, list + list_len + 1, temp);

	return w->second;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) 
		scanf("%d %d %d", &in[i].w, &in[i].g, &in[i].e);

	for (int i = 1; i <= n; i++)
		d[i] = { d[i - 1].first - (LL)(in[i].w - in[i - 1].w) + (LL)in[i].e,
			d[i - 1].second + (LL)in[i].g };

	list[0] = { -INF,0 };
	for (int i = n; i >= 1; i--)
		if (d[i].first > list[list_len].first)
			list[++list_len] = { d[i].first,i };

	for (int i = 1; i <= n; i++) {
		int w = search(d[i].first - (LL)in[i].e);
		out = max2(out, d[w].second - d[i - 1].second);
	}
	printf("%lld", out);
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:24:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
divide.cpp:26:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &in[i].w, &in[i].g, &in[i].e);
                                                  ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5408 KB Output is correct
2 Correct 0 ms 5408 KB Output is correct
3 Correct 0 ms 5408 KB Output is correct
4 Correct 0 ms 5408 KB Output is correct
5 Correct 0 ms 5408 KB Output is correct
6 Correct 0 ms 5408 KB Output is correct
7 Correct 0 ms 5408 KB Output is correct
8 Correct 0 ms 5408 KB Output is correct
9 Correct 0 ms 5408 KB Output is correct
10 Correct 0 ms 5408 KB Output is correct
11 Correct 0 ms 5408 KB Output is correct
12 Correct 0 ms 5408 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5408 KB Output is correct
2 Correct 0 ms 5408 KB Output is correct
3 Correct 0 ms 5408 KB Output is correct
4 Correct 0 ms 5408 KB Output is correct
5 Correct 0 ms 5408 KB Output is correct
6 Correct 0 ms 5408 KB Output is correct
7 Correct 0 ms 5408 KB Output is correct
8 Correct 0 ms 5408 KB Output is correct
9 Correct 0 ms 5408 KB Output is correct
10 Correct 0 ms 5408 KB Output is correct
11 Correct 3 ms 5408 KB Output is correct
12 Correct 3 ms 5408 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5408 KB Output is correct
2 Correct 0 ms 5408 KB Output is correct
3 Correct 3 ms 5408 KB Output is correct
4 Correct 16 ms 5408 KB Output is correct
5 Correct 33 ms 5408 KB Output is correct
6 Correct 59 ms 5408 KB Output is correct
7 Correct 46 ms 5408 KB Output is correct
8 Correct 59 ms 5408 KB Output is correct
9 Correct 36 ms 5408 KB Output is correct
10 Correct 49 ms 5408 KB Output is correct
11 Correct 66 ms 5408 KB Output is correct
12 Correct 56 ms 5408 KB Output is correct