Cod sursa(job #2052482)

Utilizator copanelTudor Roman copanel Data 30 octombrie 2017 17:39:52
Problema Branza Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.59 kb
/* (╭ರ_⊙) */
#include <stdio.h>

int v[100000], d[100000];

int main() {
	FILE *fin, *fout;
	int n, s, t, i, cnt;
	int st, dr;
	long long sum;

	fin = fopen("branza.in", "r");
	fscanf(fin, "%d%d%d", &n, &s, &t);
	t++;

	st = 0;
	dr = -1;
	sum = 0LL;
	for (i = 0; i < n; i++) {
		fscanf(fin, "%d%d", &v[i], &cnt);
		if (st <= dr && d[st] == i - t)
			st++;
		while (st <= dr && v[d[dr]] + (i - d[dr]) * s >= v[i])
			dr--;
		d[++dr] = i;
		sum += (long long)cnt * (v[d[st]] + (i - d[st]) * s);
	}
	fclose(fin);

	fout = fopen("branza.out", "w");
	fprintf(fout, "%lld", sum);
	fclose(fout);

	return 0;
}