Submission #21835

#	Time	Username	Problem	Language	Result	Execution time	Memory
21835		ulna	Divide and conquer (IZhO14_divide)	C++11	100 / 100	96 ms	10572 KiB

divide

#include <bits/stdc++.h>
using namespace std;

// why am I so weak

int n;
long long x[100055], g[100055], d[100055];

typedef pair<long long, int> P;

#define ft first
#define sd second

int main() {
	// sigma(ei ... ej) >= x[j] - x[i]
	// e[j] - e[i - 1] >= x[j] - x[i]
	// x[i] - e[i - 1] >= x[j] - e[j]
	
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%lld %lld %lld", &x[i], &g[i], &d[i]);

		if (i) {
			g[i] += g[i - 1];
			d[i] += d[i - 1];
		}
	}

	set<P> s;
	long long res = g[0];

	s.insert(P(x[0], 0));

	for (int i = 0; i < n; i++) {
		res = max(res, g[i] - g[i - 1]);

		{
			auto ite = s.lower_bound(P(x[i] - d[i], -1));

			if (ite != s.end()) {
				res = max(res, g[i] - (ite->sd == 0 ? 0ll : g[ite->sd - 1]));
			}
		}

		if (x[i] - d[i - 1] > s.rbegin()->ft) {
			s.insert(P(x[i] - d[i - 1], i));
		}
	}

	printf("%lld\n", res);
	
	return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:19:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
divide.cpp:22: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], &d[i]);
                                               ^

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