# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
308186 | 2020-09-30T08:41:34 Z | shrek12357 | Divide and conquer (IZhO14_divide) | C++14 | 0 ms | 0 KB |
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <map> #include <set> #include <climits> #include <cmath> #include <fstream> #include <queue> #include <stack> using namespace std; #define ll long long const int MAXN = 1e5+5; #define INF 100000000 int main() { cin.tie(0); ios_base::sync_with_stdio(0); int n; cin >> n; ll best = 0; ll pos[MAXN]; ll gold[MAXN]; gold[0] = 0; ll energy[MAXN]; energy[0] = 0; for (int i = 0; i < n; i++) { ll x, g, d; cin >> x >> g >> d; pos.push_back(x); gold[i + 1] = gold[i] + g; energy[i + 1] = energy[i] + d; best = max(best, g); } for (int i = 1; i <= n; i++) { for (int j = n; j >= i + 1; j--) { if (pos[j - 1] - pos[i - 1] <= energy[j] - energy[i - 1]) { best = max(best, gold[j] - gold[i - 1]); break; } } } cout << best << endl; }