Cod sursa(job #3308697)

Utilizator Andrei_GAndreiG Andrei_G Data 27 august 2025 13:33:44
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include <vector>
#define int long long
using namespace std;

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

deque<int> dq;

int n, s, t, dp[100005];
pair<int, int> v[100005];

signed main(){
    cin>>n>>s>>t;
    for (int i = 1; i <= n; i++){
        cin>>v[i].first>>v[i].second;
        while (!dq.empty() && v[dq.back()].first - s * dq.back() > v[i].first - s * i){
            dq.pop_back();
        }
        while (!dq.empty() && dq.front() <= i - t - 1){
            dq.pop_front();
        }
        dq.push_back(i);
        dp[i] = dp[i - 1] + v[i].second * (v[dq.front()].first - s * dq.front() + s * i);
    }
    cout<<dp[n];
}