Cod sursa(job #2872562)

Utilizator cezar.balutaCezar Baluta cezar.baluta Data 17 martie 2022 13:34:47
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;

struct muchie{
    int y,cost;
};

const int N = 1e5 + 2;
vector <muchie> v[2*N];
vector<long long> cost_lift;
vector<long long>cladire_lim_dreapta;
long long dp[2*N];
bitset<2*N>inq;

struct criteriu{
    bool operator()(int a, int b){
        return dp[a]>dp[b];
    }
};

priority_queue<int, vector<int>,criteriu>q;

bool intersecteaza(long long a, long long b, long long c, long long d){
    return ((a<=c && c<=b) || (a<=d && d<=b) || (c<=a && a<=d) || (c<=b && b<=d)) ;
}

void dijkstra(){
    long long x = 0;
    q.push(x);
    inq[x] = true;
    while(!q.empty()){
       // cout<<q.size()<<'\n';
        x = q.top();
        q.pop();
        inq[x] = false;
        for(auto y:v[x]){
         //  cout<<x<<' '<<y.y<<' '<<y.cost<<'\n';
            if((dp[y.y]>dp[x] + (long long)y.cost )|| dp[y.y] == 0){
                dp[y.y] = dp[x] +  (long long)y.cost;
                if(!inq[y.y]){
                    q.push(y.y);
                    inq[y.y] = true;
                }
            }
        }
    }
}

int main() {
    ifstream in("superhedgy.in");
    ofstream out("superhedgy.out");
    muchie add;
    long long n,m,l,h;
    long long h_anterior = 0,h_ultim_sus, h_ultim_jos;
    in>>n;
    long long c;
    cost_lift.push_back(0);
    cladire_lim_dreapta.push_back(0);
    for(int i=1;i<=n;i++){
        in>>l>>h>>c;
        cost_lift.push_back(c);
        h_ultim_sus = h;
        cladire_lim_dreapta.push_back(0);
        cladire_lim_dreapta[i] = cladire_lim_dreapta[i-1] + l;
        add.y = i;
        add.cost =max( h-h_anterior,h_anterior-h);
        v[i-1].push_back(add);
        h_anterior = h;
    }
    h_anterior = 0;
    long long cladire = 1;
    long long st_cladire = 1;
    long long dr_cladire = cladire_lim_dreapta[1];
    long long st_cladire_jos = 1;
    long long dr_cladire_jos = 1;
    in>>m;

    cladire_lim_dreapta.push_back(0);
    cladire_lim_dreapta.push_back(0);
    cladire_lim_dreapta.push_back(0);

    //cout<<cladire_lim_dreapta[n+1];
    for(int i=2;i<=m+1;i++){
        in>>l>>h>>c;
        h_ultim_jos = h;
        cladire_lim_dreapta.push_back(0);
        cladire_lim_dreapta[i+n] = cladire_lim_dreapta[i+n-1] + l;
        st_cladire_jos =  cladire_lim_dreapta[i+n-1]+1;
        dr_cladire_jos = cladire_lim_dreapta[i+n];
        while(intersecteaza(st_cladire_jos, dr_cladire_jos,st_cladire,dr_cladire) && cladire<=n){
          //  cout<<cladire<<' '<<i+n<<'\n';
            add.y = cladire;
            add.cost = cost_lift[cladire] + c;
      //      cout<<cost_lift[cladire] + c<<'\n';
            v[i+n].push_back(add);
            add.y = i+n;
            v[cladire].push_back(add);
            cladire++;
            st_cladire = cladire_lim_dreapta[cladire-1]+1;
            dr_cladire = cladire_lim_dreapta[cladire];
           // cout<<cladire<<' '<<st_cladire<<' '<<dr_cladire<<'\n';
        }
        if(st_cladire-1>dr_cladire_jos)
            cladire--;
        st_cladire = cladire_lim_dreapta[cladire-1]+1;
        dr_cladire = cladire_lim_dreapta[cladire];
        add.y = i+n;
        add.cost =max( h-h_anterior,h_anterior-h);
        if(i==2){
            v[0].push_back(add);
        }
        else
            v[i+n-1].push_back(add);
        h_anterior = h;
    }
    add.y = n+m+3;
    add.cost = h_ultim_sus;
    v[n].push_back(add);
    add.cost = h_ultim_jos;
    v[n+m+1].push_back(add);
    long long rez = cladire_lim_dreapta[n];
    cladire_lim_dreapta.clear();
    cost_lift.clear();
    dijkstra();
    out<<dp[n+m+3] +rez;
    return 0;
}