Cod sursa(job #1929668)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 17 martie 2017 21:47:16
Problema Zombie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>

const int kMaxDim = 1000005;

int vec[kMaxDim], dp[kMaxDim];

int main() {
	std::ifstream inputFile("zombie.in");
	std::ofstream outputFile("zombie.out");

	int len, n, cost;
	inputFile >> len >> n >> cost;

	for (int i = 1; i <= n; ++i)
		inputFile >> vec[i];

	int index = 1;
	dp[0] = 0;

	for (int i = 1; i <= n; ++i) {
		while (vec[i] - vec[index] + 1 > len)
			++index;

		dp[i] = std::min(dp[i - 1] + 1, dp[index - 1] + cost);
	}

	outputFile << dp[n] << '\n';

	inputFile.close();
	outputFile.close();

	return 0;
}

//Trust me, I'm the Doctor!