Cod sursa(job #2434017)

Utilizator memecoinMeme Coin memecoin Data 30 iunie 2019 12:33:14
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 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;
        
        while (!d.empty() && (i - d.front().i) > t) {
            d.pop_front();
        }
        
        while (!d.empty() && c < ((i - d.back().i) * s + d.back().v)) {
            d.pop_back();
        }
        
        d.push_back({c, i});
        
        res += ((i - d.front().i) * s + d.front().v) * p;
    }
    
    fout << res;
    
    return 0;
}