fork download
copy 
  1. /*
  2.     Cred : SunnyYeahBoi
  3.     It's my last chance (⌐■_■)
  4.     Problem :
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12. #define double long double
  13. #define endl "\n"
  14. #define NAME "a"
  15. const int inf = 1e18;
  16. const int MOD = 1e9 + 7;
  17. const int N = 5e5 + 5;
  18.  
  19. void FileInput(){
  20.     if(fopen(NAME".inp" , "r") == NULL)
  21.         freopen(NAME".inp" , "w" , stdout);
  22.     freopen(NAME".inp" , "r" , stdin);
  23.     freopen(NAME".out" , "w" , stdout);
  24. }
  25. int n , W;
  26. int a[N];
  27.  
  28. namespace subtask4{
  29.     const int MAXN = 500 + 5;
  30.  
  31.     int dp[MAXN][MAXN]; // trọng số nhỏ nhất của LIS độ dài j xét tới vị trí i
  32.  
  33.     void solve(){
  34.         for(int i = 0 ; i <= n ; i++)
  35.             for(int j = 0 ; j <= n ; j++)
  36.                 dp[i][j] = inf;
  37.         dp[0][0] = 0;
  38.  
  39.         int res = 0;
  40.         for(int i = 1 ; i <= n ; i++){
  41.             for(int j = 1 ; j <= n ; j++){
  42.                 for(int k = 0 ; k < i ; k++){
  43.                     if(a[k] < a[i] || k == 0)
  44.                         dp[i][j] = min(dp[i][j] , dp[k][j - 1] + a[i]);
  45.                 }
  46.                 if(dp[i][j] <= W) res = max(res , j);
  47.             }
  48.         }
  49.  
  50.         cout << res << endl;
  51.     }
  52. }
  53.  
  54. namespace subtask5{
  55.     const int MAXN = 5e5 + 5;
  56.  
  57.     void solve(){
  58.         vector<int> st;
  59.         for(int i = 1 ; i <= n ; i++){
  60.             if(st.empty() || st.back() < a[i]){
  61.                 st.push_back(a[i]);
  62.                 continue;
  63.             }
  64.  
  65.             int id = lower_bound(st.begin() , st.end() , a[i]) - st.begin();
  66.             st[id] = a[i];
  67.         }
  68.         cout << st.size() << endl;
  69.     }
  70. }
  71.  
  72. void solve(){
  73.     cin >> n >> W;
  74.     for(int i = 1 ; i <= n ; i++)
  75.         cin >> a[i];
  76.  
  77.     if(n <= 500)
  78.         subtask4::solve();
  79.     else subtask5::solve();
  80. }
  81.  
  82. int32_t main(){
  83.     //FileInput();
  84.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  85.     int t = 1;
  86.     // cin >> t;
  87.     while(t--)
  88.         solve();
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/EWORWE
language:
C++14 (gcc 8.3)
created:
21 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!