fork download
copy 
  1. //ojou kawayo no.1
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define tsk "bedao_r05_factory"
  5. #define pb push_back
  6. #define pf push_front
  7. #define fi first
  8. #define se second
  9. #define Ningen_sama signed
  10. #define tachi main()
  11. #define __builtin_popcount __builtin_popcountll
  12. #define el cout<<'\n'
  13. #define all(a) a.begin(),a.end()
  14. #define invAll(a) a.rbegin(),a.rend()
  15. #define sz(a) ((int)a.size())
  16. #define BIT(x, k) (1ll&((x) >> (k)))
  17. #define mem(a,x) memset(a,x,sizeof(a))
  18. #define debug(x) cout << #x << " = " << x << '\n'
  19. #define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
  20. #define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
  21. #define FORD(i, l, r) for(int i = (l); i >= (r); --i)
  22. #define REP(i, n) for(int i = 0; i < (n); ++i)
  23. //#define int long long
  24.  
  25. template<class T> bool maximize(T& u, T v){if(u >= v) return false;return u = v, true;}
  26. template<class T> bool minimize(T& u, T v){if(u <= v) return false;return u = v, true;}
  27.  
  28. using pii = pair<int, int>;
  29. using ll = long long;
  30. using vi = vector<int>;
  31. using vpii = vector<pair<int, int>>;
  32.  
  33. #define inf32 0x3f3f3f3f
  34. #define inf64 0x3f3f3f3f3f3f3f3f
  35. const int maxn = 1e6+5;
  36. const int N = 5e3 + 5;
  37. const int base = 31;
  38. const ll mod = 1e9 + 7;
  39. const ll need = 67108863;
  40. const int vc = 2e9 + 1;
  41. const ll INF18 = 4557430888798830399;
  42. const ll LOG = 20;
  43. const double eps = 1e-9;
  44. const int BLOCK = 447;
  45. const int dx[4] = {1, 0, -1, 0};
  46. const int dy[4] = {0, -1, 0, 1};
  47.  
  48. mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
  49. #define rand rd
  50. inline long long Rand(long long L, long long R) {
  51.     if(L>R) return 0;
  52.     return L + rd() % (R - L + 1);
  53. }
  54.  
  55. inline ll add(ll x, ll y){x+=y;if(x>=mod) x-=mod;if(x<0) x+=mod;return x;}
  56. inline ll mult(ll x, ll y){return 1LL * x * y % mod;}
  57.  
  58. int n, k;
  59. int a[maxn];
  60. int dp[13][(1 << 12)];
  61.  
  62. int calc(int mask){
  63.     int res = 0;
  64.     FOR(i, 0, n - 1){
  65.         if(BIT(mask, i)){
  66.             res += a[i + 1];
  67.         }
  68.     }
  69.     return res;
  70. }
  71.  
  72. inline void init(){
  73.  
  74. }
  75.  
  76. inline void input(){
  77.     cin >> n >> k;
  78.     FOR(i, 1, n) cin >> a[i];
  79. }
  80.  
  81. inline void solve(){
  82.     mem(dp, 0x3f);
  83.     dp[0][0] = 0;
  84.     FOR(i, 1, k){
  85.         FOR(mask, 0, (1 << n) - 1){
  86.             for(int submask = mask; submask; submask = (submask - 1) & mask){
  87.                 dp[i][mask] = min(dp[i][mask], max(dp[i - 1][submask ^ mask], calc(submask)));
  88.             }
  89.         }
  90.     }
  91.  
  92.     cout << dp[k][(1 << n) - 1];
  93. }
  94.  
  95. Ningen_sama tachi{
  96.     //konnakiri~~
  97.     if(fopen(tsk".inp","r")){
  98.         freopen(tsk".inp","r",stdin);
  99.         freopen(tsk".out","w",stdout);
  100.     }
  101.     ios_base::sync_with_stdio(false);
  102.     cin.tie(0); cout.tie(0);
  103.  
  104.     int Yodayo = 1;
  105.  
  106.     //cin >> Yodayo;
  107.     //init();
  108.  
  109.     while(Yodayo--){
  110.         input();
  111.         solve();
  112.     }
  113.  
  114.     //execute;
  115. }
  116. //otsunakiri~~
  117.  
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kFkS4t
language:
C++14 (gcc 8.3)
created:
16 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!