oj.uz

Submission #1088664

# Submission time Handle Problem Language Result Execution time Memory
1088664 2024-09-14T18:28:46 Z xnqs Divide and conquer (IZhO14_divide) C++17
0 / 100
 1 ms 504 KB 
#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] = 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];

		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[i];
			diff -= arr1[j];
			diff += diff_coords1[j+1];

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

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -