Submission #344542

#	Time	Username	Problem	Language	Result	Execution time	Memory
344542		maskoff	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1086 ms	2796 KiB

divide

#include <bits/stdc++.h>
 
#define file ""
 
#define all(x) x.begin(), x.end()
 
#define sc second
#define fr first
 
#define pb push_back
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;
 
const int N = 1e5 + 5;
 
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};

struct line {
 	int x;
 	int d;
 	int g;
};
vector<line> a(N);
ll dp[N];
     
int main() {  
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) 
	 	cin >> a[i].x >> a[i].g >> a[i].d;

	for (int i = 1; i <= n; i++) {
		ll sum_d = 0;
		ll sum_g = 0;
		ll len;
	 	for (int j = i; j >= 1; j--) {
	 	 	sum_g += a[j].g;
	 	 	sum_d += a[j].d;
	 	 	len = a[i].x - a[j].x;
	 	 	if (sum_d >= len) { 
	 	 		//cerr << j << " " << i << endl;
	 	 		dp[i] = max(dp[i], sum_g);
	 	 	}
	 	}
	}
	cout << *max_element(dp + 1, dp + 1 + n);
  return 0;                   
}  

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