Cod sursa(job #1806585)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 15 noiembrie 2016 15:42:12
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
#include <deque>

using namespace std;

long long n, s, t;
long long a[100000], b[100000];
deque<long long> Q;

void citire()
{
    scanf("%lld %lld %lld", &n, &s, &t);

    for(long long i = 0; i < n; i++)
    {
        scanf("%lld %lld", &a[i], &b[i]);
    }
}

void solve()
{
    long long suma = a[0] * b[0];

    Q.push_back(0);

    for(long long i = 1; i < n; i++)
    {
        while(!Q.empty() && (i - Q.back()) * s + a[Q.back()] > a[i])
        {
            Q.pop_back();
        }

        Q.push_back(i);

        if(i - Q.front() > t)
        {
            Q.pop_front();
        }

        long long tmp = Q.front();
        suma += (a[Q.front()] + (i - Q.front()) * s) * b[i];
    }

//    for(long long i = 1; i < t; i++)
//    {
//        suma += a[Q.front()] * b[Q.front()];
//        if(Q.front() != n - 1)
//        {
//            Q.pop_front();
//        }
//    }

    printf("%lld", suma);
}

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

    citire();
    solve();

    return 0;
}