fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll  = long long;
  4. const int MAXN = 1e3;
  5. ll a[MAXN+1];
  6. ll w[MAXN+1];
  7. ll dp[MAXN+1];
  8. int main(){
  9.     ios::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11.     freopen("QUA.INP" , "r" , stdin);
  12.     freopen("QUA.OUT" , "w" , stdout);
  13.     ll n;
  14.     cin >> n;
  15.     for( int i = 1 ; i<= n ; i++ ){
  16.             cin >> a[i] >> w[i];
  17.             dp[i] = w[i];
  18.     }
  19.     for( int i = 1 ; i<= n ; i++ ) {
  20.         dp[0] = 0;
  21.         for( int j = 1 ; j<i ; j++ ){
  22.             if( a[j] < a[i] ) {
  23.                 dp[i] = max( dp[i] , dp[j]+w[i]);
  24.             }
  25.         }
  26.     }
  27.     ll kq = 0;
  28.     for(int i = 1; i <= n; i++)
  29.         kq = max(kq, dp[i]);
  30.  
  31.     cout << kq;
  32.     return 0;
  33. }
  34.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
5 
5 15
3 5
4 7
5 1
2 8
stdout
copy 
15
https://ideone.com/FnRAeF
language:
C++ (gcc 8.3)
created:
5 days 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!