Rezultati

Up. imeNalogaJezikRezultatČas oddaje
rektifikatorji-2018 Priprava naloge C++ 100/100OK 19. apr '18 @ 17:49

Test Točke Porabljen spomin Porabljen čas Status
#1 11/11 6,961 MiB 0,222 s OK
#2 11/11 6,961 MiB 0,240 s OK
#3 11/11 6,820 MiB 0,246 s OK
#4 11/11 6,961 MiB 0,252 s OK
#5 11/11 6,820 MiB 0,230 s OK
#6 11/11 6,820 MiB 0,218 s OK
#7 11/11 3,016 MiB 0,000 s OK
#8 11/11 6,953 MiB 0,116 s OK
#9 12/12 3,000 MiB 0,004 s OK

Ocenjevani program (Source.cpp):
#include <iostream>

using namespace std;

#define TIME 0
#define IMPORTANCE 1
#define ull long long

int main() {
	ull** events;
	ull n, k;
	cin >> k >> n;
	events = new ull*[n];
	ull totalTime = 0, totalImportance = 0, maxImportance = 0, currentImportance = 0;
	for (int i = 0; i < n; ++i) {
		events[i] = new ull[2];
		cin >> events[i][TIME] >> events[i][IMPORTANCE];
		totalTime += events[i][TIME];
		totalImportance += events[i][IMPORTANCE];
	}

	if (totalTime < k) {
		cout << "Tekma bo polom\n";
		return 0;
	} else if (totalTime == k) {
		cout << "0\n";
		return 0;
	}

	int left = 0, right = 0;
	ull distance = 0;
	currentImportance = totalImportance;

	while (distance < k) {
		distance += events[right][TIME];
		currentImportance -= events[right][IMPORTANCE];
		++right;
	}
	
	maxImportance = currentImportance;
	
	while (distance >= k) {
		distance -= events[left][TIME];
		currentImportance += events[left][IMPORTANCE];
		++left;
		while (distance < k && right < n) {
			distance += events[right][TIME];
			currentImportance -= events[right][IMPORTANCE];
			++right;
		}

		if (right == n && distance < k) break;

		if (currentImportance > maxImportance) maxImportance = currentImportance;
	}

	cout << maxImportance << endl;

	//system("pause");
	return 0;
}