Cod sursa(job #1814712)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 24 noiembrie 2016 13:49:01
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <cstdio>
#include <deque>

using namespace std;

struct branza
{
    long c, p;
}sapt[100005];

long n, s, t;
long long costMinim;
deque <long> q;

void citire()
{
    scanf("%d%d%d", &n, &s, &t);
    for(int i=1; i<=n; ++i)
        scanf("%d%d", &sapt[i].c, &sapt[i].p);
}

int ok(int j, int i)
{
    if(((i-j)*s+sapt[j].c)*sapt[i].p<sapt[i].c*sapt[i].p)
       return 0;
    return 1;
}

void rezolvare()
{
    q.push_back(1);
    costMinim=sapt[1].c*sapt[1].p;
    for(int i=2; i<=n; ++i)
    {
        while(!q.empty()&& ok(q.back(),i)==1)
            q.pop_back();
        q.push_back(i);
        while(!q.empty()&&(i-q.front()>t))
          q.pop_front();
        int j=q.front();
        costMinim+=((i-j)*s+sapt[j].c)*sapt[i].p;
    }
}

int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);
    citire();
    rezolvare();
    printf("%lld", costMinim);
    return 0;
}