Cod sursa(job #1806596)

Utilizator stefanchistefan chiper stefanchi Data 15 noiembrie 2016 15:57:26
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <cstdio>
#define Nmax 100010
#include <deque>
using namespace std;
deque <int> deq;
pair<int,int> vec[Nmax];
int n,s,t;
long long cost;


int compare(int i)
{
    long long cost1 ,cost2;
    cost1 = vec[i].first;
    cost2 = vec[deq.back()].first + s * (i-deq.back());
    if(cost1 < cost2)
        return 1;
    else
        return 0;
}


void read()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%d %d %d",&n,&s,&t);
    for(int i = 1 ; i < t ; i++)
    {
        scanf("%d %d",&vec[i].first,&vec[i].second);
        while(!deq.empty() && compare(i) == 1)
            deq.pop_back();
        deq.push_back(i);
          cost += (vec[deq.front()].first + s*(i - deq.front()))*vec[i].second;
    }
    for(int i = t ; i <= n ; i++)
    {
        scanf("%d %d",&vec[i].first,&vec[i].second);
        if(!deq.empty() && deq.front() <= i - t)
            deq.pop_front();
        while(!deq.empty() && compare(i) == 1)
            deq.pop_back();
        deq.push_back(i);
        cost += (vec[deq.front()].first + s*(i - deq.front()))*vec[i].second;
    }
}




int main()
{
    read();
    printf("%lld",cost);
    return 0;
}