fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define fi first
  4. #define se second
  5. using namespace std;
  6. const int maxn = 1003;
  7. const int inf = 1e9;
  8. const int rmax = 100003;
  9. /*     Nguyen Tien Dung - Tran Hung Dao High School for the gifted     */
  10. /*                      𝙉𝒈𝙪𝒚𝙚𝒏 𝑵𝙜𝒐𝙘 𝙏𝒊𝙚𝒖 𝑼𝙮𝒆𝙣 <3                     */ 
  11.  
  12. int r[maxn], h[maxn], dp[maxn];
  13. int n;
  14.  
  15. void dynamic_programming(void){
  16.     for(int i = 1; i <= n; i++) dp[i] = h[i];
  17.     dp[1] = h[1];
  18.     for(int i = 2; i <= n; i++){
  19.         for(int j = 1; j < i; j++){
  20.             if (r[j] >= r[i]){
  21.                 dp[i] = max(dp[i], dp[j] + h[i]);
  22.             }
  23.         }
  24.     }
  25. }
  26.  
  27. int main(){
  28.     ios_base::sync_with_stdio(false);
  29.     cin.tie(NULL); cout.tie(NULL);
  30.     // 𝙒𝒓𝙞𝒕𝙩𝒆𝙣 𝙗𝒚 𝑻𝙞𝒆𝙣 𝘿𝒖𝙣𝒈
  31.  
  32.     cin >> n;
  33.     for(int i = 1; i <= n; i++) cin >> r[i] >> h[i];
  34.  
  35.     dynamic_programming();
  36.     int ans = 0;
  37.     for(int i = 1; i <= n; i++){
  38.         ans = max(ans, dp[i]);
  39.     }
  40.     cout << ans;
  41. }
  42.  
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tn1f4l
language:
C++14 (gcc 8.3)
created:
5 hours 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!