Cod sursa(job #1417838)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 11 aprilie 2015 11:07:07
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#define DIM 100010
#define f first
#define s second
using namespace std;

ifstream fin ("branza.in" );
ofstream fout("branza.out");

int N, M, i, j, K, ok, minim;
int deque[DIM], C, T, p, u;
long long sum;
pair <int, int> V[DIM];

void SetUp(){
     fin >> N >> C >> T;
     for(i = 1; i <= N; i ++)
          fin >> V[i].f >> V[i].s;
     return;
}

void Deque(){
     p = 1; u = 1;
     deque[p] = 1;
     sum += V[1].f * V[1].s;
     for(i = 2; i <= N; i ++){
          while(p <= u && V[i].f < V[deque[u]].f + (i - deque[u]) * C)
               u --;
          u ++;
          deque[u] = i;
          if(i - deque[p] == T)
               p ++;
          sum += (V[deque[p]].f + (i - deque[p]) * C) * 1LL * V[i].s;
     }
     fout << sum;
     return;
}

int main(){
     SetUp();
     Deque();
     return 0;
}