Cod sursa(job #2074406)

Utilizator marcudanfDaniel Marcu marcudanf Data 24 noiembrie 2017 16:12:40
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

vector <pair <int, int> >t;

pair<int, int> v[100005];

int main()
{
    int n,Max=0,n1;
    fin>>n;
    n1=n;
    while(n1--){
        int a,b;
        fin>>a>>b;
        if(b>Max)
            Max=b;
        t.push_back(make_pair(b,a));
    }
    sort(t.begin(),t.end());
    v[0].first=t[0].first;
    v[0].second=t[0].first-t[0].second;
    //cout<<v[0].second<<endl;
    for(int i=1;i<n;i++){
        if(t[i].second<v[i-1].first){
            int j=i-1;
            for(;;j--)
                if(v[j].first<=t[i].first)
                    break;
            j--;
            cout<<"v[j]="<<v[j].second<<endl;
            if(v[j].second+t[i].first-t[i].second>v[i-1].second){
                v[i].second=v[j].second+t[i].first-t[i].second;
                v[i].first=t[i].first;//cout<<'0'<<endl;
            }else{
                v[i]=v[i-1];//cout<<'1'<<endl;
            }
        }else{
            v[i].first=t[i].first;//cout<<'2'<<endl;
            v[i].second=v[i-1].second+(t[i].first-t[i].second);
        }
    }
    fout<<v[n-1].second<<'\n';
    return 0;
}