Submission #1088658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088658		xnqs	Divide and conquer (IZhO14_divide)	C++17	48 / 100	1070 ms	2140 KiB

divide

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <cstring>

int x;
int diff_coords[100005];
int coords[100005];
int arr1[100005];
int arr2[100005];

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x;
	for (int i = 1; i <= x; i++) {
		int a, b, c;
		std::cin >> a >> b >> c;
		coords[i] = a;
		diff_coords[i] = coords[i] - coords[i-1];
		arr1[i] = c;
		arr2[i] = b;
	}

	int64_t ans = 0;
	for (int i = 1; i <= x; i++) {
		int64_t gold = arr2[i];
		int64_t diff = arr1[i];
		ans = std::max(ans,gold);
		for (int j = i-1; j >= 1; j--) {
			gold += arr2[j];
			diff += arr1[j];
			diff -= diff_coords[j+1];
			if (diff>=0) {
				ans = std::max(ans,gold);
			}
		}
	}

	std::cout << ans << "\n";
}

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