Submission #767265

#	Time	Username	Problem	Language	Result	Execution time	Memory
767265		rainboy	Divide and conquer (IZhO14_divide)	C11	100 / 100	33 ms	5824 KiB

divide

#include <stdio.h>

#define N	100000

long long max(long long a, long long b) { return a > b ? a : b; }

int main() {
	static int xx[N], ii[N];
	static long long yy[N], zz[N], uu[N];
	int n, cnt, i, j;
	long long v, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%lld%lld", &xx[i], &yy[i], &zz[i]);
	for (i = 1; i < n; i++)
		yy[i] += yy[i - 1], zz[i] += zz[i - 1];
	cnt = 0;
	for (i = 0; i < n; i++) {
		uu[i] = (long long) xx[i] - (i == 0 ? 0 : zz[i - 1]);
		if (cnt == 0 || uu[ii[cnt - 1]] < uu[i])
			ii[cnt++] = i;
	}
	ans = 0;
	for (j = n - 1; j >= 0; j--) {
		v = xx[j] - zz[j];
		while (cnt && uu[i = ii[cnt - 1]] >= v) {
			ans = max(ans, yy[j] - (i == 0 ? 0 : yy[i - 1]));
			cnt--;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

divide.c: In function 'main':
divide.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
divide.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d%lld%lld", &xx[i], &yy[i], &zz[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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