fork download
copy 
  1. #include<bits/stdc++.h>
  2. typedef long long ll;
  3. typedef unsigned long long ull;
  4. #define str string
  5. #define fi first
  6. #define se second
  7. #define all(x) (x).begin(),(x).end() 
  8. #define pb push_back
  9. #define pii pair<int,int>
  10. #define el "\n"
  11. #define foR(i,a,b) for(int i=a;i<=b;i++)
  12. #define FoR(i,b,a) for(int i=b;i>=a;i--)
  13. #define de(n,a) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<el;
  14.  
  15. using namespace std;
  16. const int N = 1e6;
  17. const str NAME = "Flowers";
  18.  
  19. struct mang
  20. {
  21.     int id , nen , bd  ;
  22.     ll val ;
  23. }a[N+2];
  24.  
  25.  
  26. void freop() {
  27.     freopen( (NAME + ".inp" ).c_str(), "r" , stdin );
  28.     freopen( (NAME + ".out" ).c_str(), "w" , stdout );
  29. }
  30.  
  31. int n ;
  32. ll res , bit[N+2] ;
  33. vector < int > v ;
  34. void nen(){
  35.     foR(i,1,n) v.push_back( a[i].bd ) ;
  36.     sort(all(v));
  37.     v.erase(unique(all(v)),v.end()) ;
  38.     foR(i,1,n) {
  39.         a[i].nen = lower_bound(all(v) , a[i].bd) - v.begin() + 1 ;
  40.     }
  41. }
  42.  
  43. void upd ( int  &x , ll &val ) {
  44.     while ( x <= n ) {
  45.         bit[x] = max ( bit[x] , val ) ;
  46.         x += x&-x ;
  47.     }
  48. }
  49. ll get ( int x ) {
  50.     ll s = 0 ;
  51.     while ( x > 0 ) {
  52.         s = max ( s , bit[x] );
  53.         x -= x&-x ;
  54.     }
  55.     return s ;
  56. }
  57.  
  58. int main(){
  59.     ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
  60.  
  61.     // freop() ;
  62.  
  63.     cin >> n ;
  64.     foR(i,1,n) cin >> a[i].bd;
  65.     foR(i,1,n) cin >> a[i].val ;
  66.  
  67.     nen() ;
  68.  
  69.     foR(i,1,n) {
  70.         ll k = get(a[i].nen-1) + a[i].val ; 
  71.         res = max ( res , k ) ;
  72.         upd ( a[i].nen , k ) ;
  73.     }
  74.     cout << res ;
  75.     return 0 ;
  76. }
  77.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ygmpT9
language:
C++ (gcc 8.3)
created:
2 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!