Pagini recente » Cod sursa (job #1845578) | Cod sursa (job #1048165) | Cod sursa (job #750088) | Cod sursa (job #1582332) | Cod sursa (job #731305)
Cod sursa(job #731305)
#include <fstream>
#include <algorithm>
#define nmax 100005
using namespace std;
int n, dp[nmax][3];
pair<int,int> v[nmax];
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
bool cmp(pair<int,int> a, pair<int,int> b){
if (a.second == b.second){
/*
int x = a.second - a.first;
int y = b.second - b.first;
*/
return a.first < b.first;
}
return a.second < b.second;
}
void citeste(){
f >> n;
for(int i=1; i<=n; i++){
int x,y;
f >> x >> y;
v[i]=(make_pair(y-x, y));
}
sort(v+1, v+n+1, cmp);
}
void rezolva(){
for(int i=1; i<=n; i++){
int val = v[i].first;//am durata concertului
int final = v[i].second;
int start = final - val;
dp[i][0] = val;
dp[i][1] = final;
//g << val << " " << start << "\n";
int Max = 0;
for(int j=1; j<i; j++){
if (start >= dp[j][1]){//daca pot continua un concert
Max = max(Max, dp[j][0]);
}
}
dp[i][0] = Max+val;
}
g << dp[n][0] << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}