fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct Camac{
  4.     int l,p;
  5. };
  6. bool acompare(Camac a,Camac b) { return a.p < b.p; }
  7. int res(){
  8.     int d[10000],r[10000];
  9.     Camac c[10000];
  10.     int n;
  11.     cin>>n;
  12.     for(int i=0;i<n;i++)
  13.         cin>>c[i].l>>c[i].p;
  14.     sort(c,c+n,acompare);
  15.     for(int i=0;i<n;i++){
  16.         r[i]=1;
  17.         d[i]=c[i].p;
  18.         for(int j=0;j<i;j++)
  19.             if(d[j]<=c[i].p){
  20.                 if(r[j]+1>r[i]){
  21.                     r[i]=r[j]+1;
  22.                     d[i]=max(c[i].p,d[j]+c[i].l);
  23.                 }
  24.                 if(r[j]==r[i]){
  25.                     int k=d[j]+c[i].l;
  26.                     if(d[i]>k)
  27.                         d[i]=k;
  28.                 }
  29.             }
  30.     }
  31.     int m=r[0];
  32.     for(int i=1;i<n;i++)
  33.         if(r[i]>m)
  34.             m=r[i];
  35.     return m;
  36. }
  37. int main(){
  38.     cout<<res();
  39.     return 0;
  40. }
Success #stdin #stdout 0s 15272KB
comments (?)
stdin
copy 
7
5 9
2 17
6 10
3 11
2 16
4 13
5 6
stdout
copy 
5
https://ideone.com/9EAcPX
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!