Cod sursa(job #2907137)

Utilizator TODEToderita Mihai TODE Data 28 mai 2022 21:19:18
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <deque>
#include <utility>
using namespace std;

ifstream cin("branza.in");
ofstream cout("branza.out");

const int N = 1e5 + 1;
pair<int , int> v[N];
deque<int> dq;
long long sum;
int main(){
    int n , s , t;
    cin>>n>>s>>t;
    t++; // nr zile pana se strica
    for(int i = 1 ; i <= n ; i++){
        cin>>v[i].first>>v[i].second;
        while(!dq.empty() && dq.front() < i - t) // s-a stricat
            dq.pop_front();
        while(!dq.empty() && v[dq.back()].first + (i - dq.back()) * s > v[i].first)
            dq.pop_back();
        dq.push_back(i);
        sum += ((v[dq.front()].first + s*(i - dq.front())) * v[i].second);
        //cout<<v[dq.front()].first<<' '<<i - dq.front()<<' '<<v[i].second<<'\n';
    }
    cout<<sum;
}