Submission #763413

#	Time	Username	Problem	Language	Result	Execution time	Memory
763413		KN200711	Divide and conquer (IZhO14_divide)	C++14	100 / 100	27 ms	5952 KiB

divide

# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;

int main() {
	int N;
	scanf("%d", &N);
	
	vector<int> x(N), y(N), z(N);
	for(int i=0;i<N;i++) scanf("%d %d %d", &x[i], &y[i], &z[i]);
	
	ll pref = 0ll;
	vector< pair<ll, ll> > as;
	as.clear();
	
	ll ans = 0ll, nw = 0ll;
	for(int i=0;i<N;i++) {
		if(as.size() == 0 || -as.back().fi > pref - 1ll * x[i]) as.push_back(make_pair(-pref + 1ll * x[i], nw));
		nw += y[i];
		pref += z[i];
		
		ll ck = pref - x[i];
	//	cout<<ck<<endl;
		int P = lower_bound(as.begin(), as.end(), make_pair(-ck, 0ll)) - as.begin();
		if(P == as.size()) continue;
		ans = max(ans, nw - as[P].se);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:27:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   if(P == as.size()) continue;
      |      ~~^~~~~~~~~~~~
divide.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
divide.cpp:12:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  for(int i=0;i<N;i++) scanf("%d %d %d", &x[i], &y[i], &z[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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