fork download
copy 
  1.  
  2. /*
  3. @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#+*%+*##%+#@@@@@@@%@@@@@@%@
  4. @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%***+#@@@@@%@@@@@@@@@@@@
  5. @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#+#%@@@#@@@@@@@@@@@@@@@@@@
  6. @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  7. @#%@@@@#%@@@@@@@@@@@@@@@@@@@@%#%##%#@%+@@@@@@@@@@@@@#%@@*@@*@@@@@@@@@@@@@@@@%*#%%@@@@@@@@@@@@@@@@@@@@@@
  8. *%%%*#%%%+#@@@@@@@@@@@@@@@@@@+@@#+%@@+*@@@@@@@@@@@@@@%@**@#+@@@@@@@@%*%@@@#*#****#%%%#%@@@%@@@@@@@@@@@@
  9. *%@%#@@%*%@@@@%#@@@@@@@@@@@@@@@@*#@@#*%@@*#@%%#@@*%#%@%*@%**@%#%%####%#*#@@@@%#%%###@@%%@@@@@@@%@@@%@@@
  10. %@@@@@@@@@@%*##@%*@@@@@@@@@@@@@@+#@@+#@@%*%@%+##+@%%@@@@@@**%+@@#%%*###%@%@%**+*#@@#*%@%%@@%%@@@@@@@%@@
  11. @@@@@@%@@@%@%@#**@@@@@@@@@@@@@@%+%@%+%@%####%%%@%%@@@@#%@@*%@@%@@@@@@%#@%*@@%%@@%#%@@@****@%@@@@@%#%%@@
  12. @@@@@@@@@@@@%%@@@@@#*%@@@@@@@@@@%%#*+*##@@@@#***#@@@%###*+*@@@@@%#**##%@@@@@@@@@@@@@+*##%@%@@@%@@#@@**@
  13. @@@@@@@@@@@%%@@@@@@@@@@@@@@@@@@%=-=+=--+%@+--==--=#@#=-===-=*@%+-=+=--*@@@@@@@@@@@**+*#%##%@@@##@#@@#%#
  14. @@@@@@@@@@@@%####**%#%@@@@@@@@@#**#@%=-=#%=-=%@+-=#@*==#@*--+@+-=#@@###@@@@@@@@@@@@%*#****@@@%%#@+@@**%
  15. @@@@@@@@@@@@@@@@@@@@%*#@@@@@@@@@@@@#=-=*@%=-+%@+--*@@@@@*=-+@%=-----=+@@@@@@@%+@#%%@@@@%%@@@@##@@@@@#*#
  16. @@@@@%@@@@@@@@@%%##*++%@@@@@@@%@@%+--+%@@%=-=%@+--*@@@#=-=#@@%=--#@%=-*@%%@%#*#%%#***%%@@@@@@@@@@@@@@@@
  17. @@@@@@%%@@@@@@@@@%%%%%@@@@%%@@@@*=-=%@@@@%=-=%@+-=*@%+--+@@@@%=-=%@%=-*%*+#%@@@@@@@@%*#*%@@@@@@@@@@@@@%
  18. @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=--====+%@+=-----+%@*--=====#@#=-=*+-=%@@%@@@@@@@@@@@%%##@@@@@@@@@@@@@@
  19. @%@@@@%@@@@@%@@@%%%@@@@@@@@@@@@%#######%@@@@%##%@@@@#*######@@@@%#*%@@@#*#%%@##%%@@@@@%##@@@@@@@@@@@@@@
  20. @@@%%@@%%##%@@@#+%@@@@@@@@@@@@@@@@@##@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%#%@%#%@@@@@@@%#%@@@@@@@@@@@@@@@
  21. @@@@@@@@@%@%*@%#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#*#%@#%##%##%@@@@@@@@@@@@@@@@
  22. %%#@@@@@@%**@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%
  23. +#%#@##%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  24. @@@#%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@
  25. @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  26.  
  27.  
  28.  */
  29.  
  30. // LQDOJ: HoaiNam
  31. // CVPOJ: namtrank29CVP
  32. // Riot Username: HoaiNam#1337
  33. // Facebook: https://w...content-available-to-author-only...k.com/anh.nam.cha.muc/
  34. // Taskname:
  35.  
  36. // #pragma GCC optimize("O3")
  37. // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  38.  
  39. #include<bits/stdc++.h>
  40. #define int long long
  41. #define endl "\n"
  42. #define sz(x) (int)(x).size()
  43. #define all(x) (x).begin(),(x).end()
  44. #define f0(i,n) for(int i=0;i<n;i++)
  45. #define f1(i,n) for(int i=1;i<=n;i++)
  46. #define faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  47. #define file(name) freopen(name".inp","r",stdin);freopen(name".out","w",stdout);
  48. using namespace std;
  49.  
  50. const int maxn = 1e5 + 5;
  51. const int MOD = 1e9 + 7;
  52.  
  53. int n, f[maxn], a[maxn], B[maxn], A[maxn], dp[maxn];
  54.  
  55. void update(int pos, int val) {
  56.     for (int i = pos; i <= n; i += i & -i) {
  57.         dp[i] = max(dp[i], val);
  58.     }
  59. }
  60.  
  61. int get(int pos) {
  62.     int ans = -1e18;
  63.     for (int i = pos; i; i -= i & -i) {
  64.         ans = max(ans, dp[i]);
  65.     }
  66.     return ans;
  67. }
  68.  
  69. int sum(int l, int r) {
  70.     return get(r) - get(l - 1);
  71. }
  72.  
  73. map<int, int> zip;
  74. int m;
  75. void nenso() {
  76.     sort(a + 1, a + n + 1);
  77.     int iter = 1;
  78.     zip[a[1]] = 1;
  79.     for (int i = 2; i <= n; ++i) {
  80.         if (a[i] > a[i - 1]) {
  81.             iter++;
  82.             zip[a[i]] = iter;
  83.         }
  84.         else {
  85.             zip[a[i]] = iter;
  86.         }
  87.     }
  88.     m = iter;
  89. }
  90.  
  91. int32_t main() {
  92.     faster
  93.  
  94.     cin >> n;
  95.  
  96.     // f1(i, n) f[i] = -1e18;
  97.  
  98.     f1(i, n) {
  99.         cin >> A[i];
  100.         zip[A[i]] = 1;
  101.     }
  102.  
  103.     f1(i, n) {
  104.         a[i] = A[i];
  105.         B[i] = A[i];
  106.     }
  107.  
  108.     nenso();
  109.  
  110.     for (int i = 1; i <= n; ++i) {
  111.         A[i] = zip[A[i]];
  112.     }
  113.  
  114.     for (int i = 1; i <= n; ++i) {
  115.         dp[i] = -1e18;
  116.     }
  117.  
  118.     for (int i = 1; i <= n; ++i) {
  119.         update(A[i], B[i]);
  120.         update(A[i], get(A[i] -  1) + B[i]);
  121.  
  122.     }
  123.  
  124.     cout << get(m);
  125.  
  126.     return 0;
  127. }
  128.  
  129.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ogogDH
https://c...content-available-to-author-only...u.vn/problem/hsg12_tn_2024_v1_b2?fbclid=IwY2xjawPPN0hleHRuA2FlbQIxMQBzcnRjBmFwcF9pZAEwAAEe2Uo2pmWIyUHSla_1G88_sXO6sGx4It8eevuqMQPfkhkxyt5UCaxnD8RrzlE_aem_rMTWqE9djIaX4fkX0YKwVA
language:
C++14 (gcc 8.3)
created:
14 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!