Submission #20827

#	Time	Username	Problem	Language	Result	Execution time	Memory
20827		kdh9949	Divide and conquer (IZhO14_divide)	C++14	100 / 100	73 ms	4824 KiB

divide

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

int n, x[100010], sz;
ll g[100010], e[100010], ans;
vector<int> v;

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d%lld%lld", x + i, g + i, e + i);
		g[i] += g[i - 1];
		e[i] += e[i - 1];
	}
	for(int i = n, s, en; i >= 1; i--){
		while(sz > 1 && 1L * (e[i - 1] - e[v[sz - 1]]) / (x[i] - x[v[sz - 1]]) <
						1L * (e[v[sz - 1]] - e[v[sz - 2]]) / (x[v[sz - 1]] - x[v[sz - 2]])){ v.pop_back(); sz--; }
		v.push_back(i); sz++;
		s = 0; en = sz - 1;
		while(s <= en){
			int m = (s + en) / 2;
			if(e[v[m] - (v[m] == i)] - e[i - 1] >= x[v[m]] - x[i]) en = m - 1;
			else s = m + 1;
		}
		ans = max(ans, g[v[s]] - g[i - 1]);
		v.pop_back(); sz--;
		while(sz > 1 && 1L * (e[i] - e[v[sz - 1]]) / (x[i] - x[v[sz - 1]]) <
						1L * (e[v[sz - 1]] - e[v[sz - 2]]) / (x[v[sz - 1]] - x[v[sz - 2]])){ v.pop_back(); sz--; }
		v.push_back(i); sz++;
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:10:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
divide.cpp:12:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld%lld", x + i, g + i, e + i);
                                           ^

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