Cod sursa(job #1502324)

Utilizator mirupetPetcan Miruna mirupet Data 14 octombrie 2015 16:16:05
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<cstdio>
#include<deque>
#define DIM 100001
using namespace std;

int N, S, T, X, Y;
int sol, i;

deque <int> val, pos;

int main()
    {
        freopen("branza.in","r",stdin);
        freopen("branza.out","w",stdout);

        scanf("%d%d%d", &N, &S, &T);

        for (i = 1; i <= N; i++)
            {
                scanf("%d%d", &X, &Y);
                while (!pos.empty() && i - pos.front() > T)
                {
                    val.pop_front();
                    pos.pop_front();
                }

                while (!val.empty() && X <= val.back() + (i - pos.front()) * S)
                {
                    val.pop_back();
                    pos.pop_back();
                }

                val.push_back(X);
                pos.push_back(i);

                sol += (val.front() + (i - pos.front()) * S) * Y;

                //printf("%d\n", sol);
            }

        printf("%d\n", sol);
    }