Cod sursa(job #2733949)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 31 martie 2021 10:01:18
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
pair <int,int> a[100000];
deque <int> dq;
int main()
{
    int n, k, t;
    in>>n>>t>>k;
    long long s=0;
   // k++;
    for(int i=0;i<n;i++)
    {
        in>>a[i].first>>a[i].second;
        if(!dq.empty()&&dq.front()==i-k)
            dq.pop_front();
        while(!dq.empty()&&a[i].first<=a[dq.back()].first+t*(i-dq.back()))
            dq.pop_back();
        dq.push_back(i);
        s+=(a[dq.front()].first+t*(i-dq.front()))*a[i].second;
    }
    out<<s;
    return 0;
}