Cod sursă (job #733196)

#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int Nmax = 200005;

int v[Nmax], aux[Nmax];
vector<pair<int, int>> p[Nmax];
priority_queue<pair<int, int>> q;

int main(){
    ifstream fin("stampile.in");
    ofstream fout("stampile.out");

    int n, m, a, b, t, cate;
    pair<int, int> pr;

    fin >> n >> m;

    for(int i = 0; i < n; i++){
        fin >> v[i];
    }

    for(int i = 0; i < m; i++){
        fin >> a >> b >> t;
        a--; b--;
        p[a].push_back({b, t});

    }

    cate = 0;
    for(int i = 0; i < n; i++){
        for(pair<int, int> g : p[i]){
            q.push(g);
        }

        v[i] -= aux[i];
        while(v[i] > 0 && !q.empty()){
            pr = q.top();
            q.pop();

            if(pr.second <= v[i]){
                v[i] -= pr.second;
                aux[i] += pr.second;
                aux[pr.first + 1] -= pr.second;
                cate += pr.second;
            }
            else{
                pr.second -= v[i];
                aux[i] += v[i];
                aux[pr.first + 1] -= v[i];
                cate += v[i];
                v[i] = 0;

                q.push(pr);
            }
        }

        aux[i + 1] += aux[i];

        if(q.empty() && v[i] > 0){
            fout << -1;
            return 0;
        }
    }

    fout << cate;

    return 0;
}