oj.uz

Submission #173011

# Submission time Handle Problem Language Result Execution time Memory
173011 2020-01-03T04:19:04 Z tourist Divide and conquer (IZhO14_divide) C++14
100 / 100
 66 ms 8228 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 pll pair < ll, ll >
#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, suf[N];
ll g[N], en[N];
vector < pll > 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) {
	pll temp = {-(v[id].first - 0LL - 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] + 0LL, 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:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
divide.cpp:31: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 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 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
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 Correct 3 ms 380 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 5 ms 888 KB Output is correct
12 Correct 5 ms 888 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 7 ms 1116 KB Output is correct
4 Correct 28 ms 4112 KB Output is correct
5 Correct 32 ms 4364 KB Output is correct
6 Correct 66 ms 8228 KB Output is correct
7 Correct 51 ms 7204 KB Output is correct
8 Correct 52 ms 7276 KB Output is correct
9 Correct 50 ms 7040 KB Output is correct
10 Correct 51 ms 7024 KB Output is correct
11 Correct 57 ms 7556 KB Output is correct
12 Correct 59 ms 7832 KB Output is correct