oj.uz

Submission #173008

# Submission time Handle Problem Language Result Execution time Memory
173008 2020-01-03T04:11:07 Z tourist Divide and conquer (IZhO14_divide) C++14
17 / 100
 7 ms 1016 KB 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define ll long long
#define sz(x) (int)x.size()
#define pii pair < int, int >
#define endl "\n"
#define METH ios::sync_with_stdio(0); cin.tie(0);
#define BEGIN cout << "BEGIN" << endl;
#define END cout << "END" << endl;

const int N = 1e5 + 9;
const int mod = 1e9 + 7;										/// ANOTHER HASH MOD: 228228227
const int prime = 29;											/// ANOTHER HASH PRIME: 997
const int INF = ((long long) 0xCAFEBABE - 1e9 - 4e8);

int n, g[N], en[N], suf[N];
vector < pii > eq;
vector < pair < int, pii > > v;

inline void read() {
	scanf("%d", &n);
	v.push_back({0, {0, 0}});
	for (int i = 1; i <= n; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		v.push_back({a, {b, c}});
		en[i] = en[i - 1] + c;
		eq.push_back({en[i] - a, i});
		g[i] = g[i - 1] + b;
	}
}

ll calc(int id) {
	pii temp = {-(v[id].first - en[id - 1]), 0};
	int index = lower_bound(eq.begin(), eq.end(), temp) - eq.begin();
	return g[suf[index]] - g[id - 1];
}

inline void solve() {
	ll ans = 0;
	sort(eq.begin(), eq.end());

	for (int i = n - 1; i >= 0; i--) {
		suf[i] = max(suf[i + 1], eq[i].second);
	}

	for (int i = 1; i <= n; i++) {
		ans = max(ans, calc(i));
	}

	cout << ans << endl;
}

int main() {
	int t;
	t = 1;

	while (t--) {
		read();
		solve();
	}
}

Compilation message

divide.cpp: In function 'void read()':
divide.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
divide.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 368 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 3 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 6 ms 916 KB Output is correct
3 Incorrect 7 ms 1016 KB Output isn't correct
4 Halted 0 ms 0 KB -