Submission #1088656

#TimeUsernameProblemLanguageResultExecution timeMemory
1088656xnqsDivide and conquer (IZhO14_divide)C++17
48 / 100
1024 ms2392 KiB
#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] = a - diff_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 -= coords[j+1] - coords[j];
			if (diff>=0) {
				ans = std::max(ans,gold);
			}
		}
	}

	std::cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...