Cod sursa(job #3356179)

Utilizator rares89_Dumitriu Rares rares89_ Data 30 mai 2026 00:05:20
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");

long long n, s, t, total;
long long c[100005], p[100005];
int dq[100005];
int st = 1, dr = 0;

int main() {
    fin >> n >> s >> t;
    for (int i = 1; i <= n; ++i) {
        fin >> c[i] >> p[i];
        
        // branza expirata
        while (st <= dr && dq[st] < i - t) {
            st++;
        }
        
        // mentinem dq monoton
        while (st <= dr && c[dq[dr]] - dq[dr] * s >= c[i] - i * s) {
            dr--;
        }
        
        dq[++dr] = i;
        
        total += p[i] * (c[dq[st]] + (i - dq[st]) * s);
    }
    
    fout << total << "\n";
    fin.close();
    return 0;
}