Submission #1088683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088683		xnqs	Divide and conquer (IZhO14_divide)	C++17	48 / 100	1020 ms	4180 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_coords1[100005];
int diff_coords2[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_coords1[i-1] = coords[i] - coords[i-1];
		arr1[i] = c;
		arr2[i] = b;
	}

	for (int i = x-1; i >= 1; i--) {
		diff_coords2[i] = coords[i+1] - coords[i];
	}

	int64_t ans = 0;
	for (int i = 1; i <= x; i++) {
		ans = std::max(ans, (int64_t)arr2[i]);
	}

	int64_t base_gold = arr2[1];
	int64_t base_diff = arr1[1];
	for (int i = 2; i <= x; i++) {
		base_gold += arr2[i];
		base_diff += arr1[i];
		base_diff -= diff_coords1[i-1];

		if (base_diff>=0) {
			ans = std::max(ans, base_gold);
			continue;
		}

		int64_t gold = base_gold;
		int64_t diff = base_diff;

		for (int j = 1; j < i; j++) {
			gold -= arr2[j];
			diff -= arr1[j];
			diff += diff_coords1[j];

			if (diff>=0) {
				ans = std::max(ans,gold);
				break;
			}
		}
	}

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

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