Cod sursa(job #2434004)

Utilizator memecoinMeme Coin memecoin Data 30 iunie 2019 12:14:41
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>

using namespace std;

#ifdef DEBUG
string name = "data";
#else
string name = "branza";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

struct Ele {
    uint64_t v;
    uint64_t i;
};

uint64_t n,s,t;

int main() {
    
    deque<Ele> d;
    
    fin >> n >> s >> t;
    
    uint64_t c,p;
    
    int64_t res = 0;
    
    for (uint64_t i = 0; i < n; ++i) {
        fin >> c >> p;
        
        if (d.size() > 0 && (i - d.front().i) >= t) {
            d.pop_front();
        }
        
        while (d.size() > 0 && c <= ((i - d.front().i) * s + d.front().v)) {
            d.pop_back();
        }
        
        d.push_back({c, i});
        
        res += ((i - d.front().i) * s + d.front().v) * p;
    }
    
    fout << res;
    
    return 0;
}