Cod sursa(job #1835163)

Utilizator Coroian_DavidCoroian David Coroian_David Data 26 decembrie 2016 14:35:56
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>

#include <climits>

using namespace std;

FILE *f, *g;

unsigned long long d[100001], st = 1, dr = 0;

unsigned long long n, s, t;

unsigned long long c[100001];
unsigned long long v[100001];

void stanga(unsigned long long i)
{
    if(i - t == d[st])
        st ++;
}

void dreapta(unsigned long long i)
{
    while(st <= dr && v[i] <= v[d[dr]] + (i - d[dr]) * s)
        dr --;

    d[++ dr] = i;
}

unsigned long long sum;

void readFile()
{
    f = fopen("branza.in", "r");

    fscanf(f, "%llu%llu%llu", &n, &s, &t);

    unsigned long long i;

    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%llu%llu", &v[i], &c[i]);

        if(i > t)
            stanga(i);

        dreapta(i);

        sum += (v[d[st]] + (i - d[st]) * s) * c[i];
    }
}

void printFile()
{
    g = fopen("branza.out", "w");

    fprintf(g, "%llu\n", sum);

    fclose(g);
}

int main()
{
    readFile();

    printFile();

    return 0;
}