fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn = 100;
  5. int n, x, a[maxn+5][maxn+5];
  6. ll dp[maxn+5]; //diem khi dung i ngay
  7. void read() {
  8.     cin >> n >> x;
  9.     for (int i = 1; i<=n; ++i) {
  10.         for (int j = 1; j<=x; ++j) cin >> a[i][j];
  11.     }
  12. }
  13. void dequy(vector <int> v, int & res) {
  14.     if (v.size() == n) {
  15.         int days = 0;
  16.         for (int val : v) days += val;
  17.         int cur = 0;
  18.         if (days <= x) {
  19.             for (int i = 0; i<n; ++i) {
  20.                 cur += a[i+1][v[i]];
  21.             }
  22.             res = max(res, cur);
  23.         }
  24.         return;
  25.     }
  26.     for (int i = 0; i<=x; ++i) {
  27.         v.push_back(i);
  28.         dequy(v, res);
  29.         v.pop_back();
  30.     }
  31. }
  32. void sub1() {
  33.     vector <int> v;
  34.     int res = 0;
  35.     dequy(v, res);
  36.     cout << res;
  37. }
  38. void sub2() {
  39.     int res = 0;
  40.     for (int i = 1; i<=n; ++i) {
  41.         res = max(res, a[i][1]);
  42.     }
  43.     cout << res;
  44. }
  45. void sub3() {
  46.     for (int i = 1; i<=n; ++i) {
  47.         ll new_dp[maxn+5];
  48.         for (int j = 0; j<=x; ++j) new_dp[j] = 0;
  49.  
  50.         for (int g = 0; g<=x; ++g) {
  51.             for (int h = 0; h<=g; ++h) {
  52.                 new_dp[g] = max(new_dp[g], 1LL * dp[g-h] + a[i][h]);
  53.             }
  54.         }
  55.  
  56.         for (int j = 0; j<=x; ++j) dp[j] = new_dp[j];
  57.     }
  58.     ll res = 0;
  59.     for (int i = 0; i<=x; ++i) res = max(res, dp[i]);
  60.     cout << res;
  61. }
  62. void solve() {
  63.     if (n <= 4 && x <= 4) sub1();
  64.     else if (x == 1) sub2();
  65.     else sub3();
  66. }
  67. int main() {
  68.     ios_base::sync_with_stdio(false);
  69.     cin.tie(0); cout.tie(0);
  70.     read();
  71.     solve();
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eIOozL
language:
C++ (gcc 8.3)
created:
3 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!