Cod sursa(job #2864893)
| Utilizator | Data | 8 martie 2022 12:13:56 | |
|---|---|---|---|
| Problema | Heavy metal | Scor | 40 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.65 kb |
#include <fstream>
#include <algorithm>
using namespace std;
pair<int, int> s[100010];
int d[100010];
int n, maxim;
int main () {
ifstream fin ("heavymetal.in");
ofstream fout("heavymetal.out");
fin>>n;
for (int i=1;i<=n;i++){
fin>>s[i].second>>s[i].first;
}
sort(s+1, s+n+1);
for (int i=1;i<=n;i++){
d[i]=s[i].first-s[i].second;
for (int j=i-1;j>=1;j--){
if (s[i].second>=s[j].first){
d[i]=max(d[i], d[j]+s[i].first-s[i].second);
}
}
if (d[i]>maxim){
maxim=d[i];
}
}
fout<<maxim;
return 0;
}
