Cod sursa(job #1495049)

Utilizator cella.florescuCella Florescu cella.florescu Data 2 octombrie 2015 14:15:14
Problema Branza Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <stdio.h>
#include <stdlib.h>

struct branza {
  int cost, timp;
} v[100000];

int main()
{
    FILE *fin, *fout;
    int n, s, t, i, b, e, c, p;
    long long tot;
    fin=fopen("branza.in", "r");
    fscanf(fin, "%d%d%d", &n, &s, &t);
    b=e=0; tot=0LL; v[0].timp=i;
    for(i=0; i<n; i++){
      fscanf(fin, "%d%d", &c, &p);
      while(i-v[b].timp>t)
        ++b;
      while(e>b && 1LL*(i-v[e-1].timp)*s+v[e-1].cost>=c)
        --e;
      v[e].timp=i; v[e++].cost=c;
      tot+=1LL*p*((i-v[b].timp)*s+v[b].cost);
    }
    fclose(fin);
    fout=fopen("branza.out", "w");
    fprintf(fout, "%lld\n", tot);
    fclose(fout);
    return 0;
}