oj.uz

Submission #758357

# Submission time Handle Problem Language Result Execution time Memory
758357 2023-06-14T13:46:20 Z KN200711 Divide and conquer (IZhO14_divide) C++14
17 / 100
 1 ms 304 KB 
# 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();
		ans = max(ans, nw - as[P].se);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

divide.cpp: In function 'int main()':
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.0 / 17.0

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

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 296 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 296 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -