Cod sursa(job #1812959)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 22 noiembrie 2016 16:28:24
Problema Branza Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <cstdio>
#include <deque>

using namespace std;

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

int n, s, t;
long long costMinim, m[100005];
deque <int> 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);
}

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

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