fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define pii pair<int,int>
  5. #define pll pair<ll,ll>
  6. #define plll pair<ll,pll>
  7. #define tull tuple<ll,ll,ll>
  8. #define pb push_back
  9. #define f first
  10. #define endl "\n"
  11. #define se second
  12. #define piii pair<int,pii>
  13. #define id1 id<<1
  14. #define id2 (id<<1)+1
  15. #define MASK(i) (1<<i)
  16. #define TIME "\nTime elapsed : "<<(double)clock()/1000<<" ms"
  17. #define all(x) x.begin(),x.end()
  18. #define id(i,j) (i - 1) * m + j
  19. #define TASK "test"
  20. #define fast ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
  21. using namespace std;
  22. const ll mod = 1e9 + 7; //;998244353
  23. const ll base = 311;
  24. const ll INF = 1e18 + 7;
  25. const ll maxn = 1e6 + 5;
  26. const ll maxs = 1e7 + 1;
  27. const ll dx[] = {-1,0,0,1};
  28. const ll dy[] = {0,-1,1,0};
  29. const int dx8[] = {1, 0, -1, 0, 1, -1, -1, 1};
  30. const int dy8[] = {0, 1, 0, -1, 1, -1, 1, -1};
  31.  
  32. int k;
  33. string s;
  34. string dp[1001][1001];
  35. ll res = LLONG_MAX;
  36.  
  37. int main()
  38. {
  39.     fast
  40.  
  41.     cin >> k;
  42.  
  43.     cin >> s;
  44.  
  45.     ll n = s.size();
  46.  
  47.     s = ' ' + s;
  48.  
  49.     for(int i = 0; i <= n; ++i){
  50.         for(int j = 0; j <= k; ++j){
  51.             dp[i][j] = "99999999999999999999999999999999999999999999999999999999999999999999";
  52.         }
  53.     }
  54.  
  55.     string oo = dp[0][0];
  56.     dp[0][0] = "";
  57.  
  58.     for(int i = 0; i <= n - 1; ++i){
  59.         for(int cnt = 0; cnt <= k; ++cnt){
  60.             if(dp[i][cnt] != oo){
  61.                 if(cnt + 1 <= k){
  62.                     dp[i + 1][cnt + 1] = min(dp[i + 1][cnt + 1],dp[i][cnt] + s[i + 1]);
  63.                 }
  64.  
  65.                 dp[i + 1][cnt] = min(dp[i + 1][cnt],dp[i][cnt]);
  66.             }
  67.         }
  68.     }
  69.  
  70.     cout << dp[n][k];
  71.  
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 34960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CIbbBz
language:
C++14 (gcc 8.3)
created:
143 days ago
visibility:
secret

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!