fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long 
  4. #define el cout << '\n'
  5. #define bit(mask, i) (((mask) >> (i)) & 1)
  6. #define BIT(n) ((1ll) << (n))
  7.  
  8. using namespace std;
  9.  
  10. const int maxn = 5e4;
  11. const int maxm = 5;
  12. const ll INF = 1e18;
  13.  
  14. int n, m, cnt[maxn + 10][maxm + 5];
  15. ll S = 0, dp[maxn + 10][maxm + 5][BIT(maxm) + 5], a[maxn + 10];
  16.  
  17. int main()
  18. {
  19.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  20.     if (fopen("REPGAME.INP", "r"))
  21.     {
  22.         freopen("REPGAME.INP", "r", stdin);
  23.         freopen("REPGAME.OUT", "w", stdout);
  24.     }
  25.  
  26.     cin >> n >> m;
  27.     for (int i = 1; i <= n; i++)
  28.     {
  29.         cin >> a[i];
  30.         S += a[i];
  31.     }
  32.     for (int i = 0; i < m; i++)
  33.     {
  34.         int l, r;
  35.         cin >> l >> r;
  36.         cnt[l][i]++;
  37.         cnt[r + 1][i]--;
  38.     }
  39.     for (int i = 1; i <= n; i++)
  40.         for (int j = 0; j < m; j++)
  41.             cnt[i][j] += cnt[i - 1][j];
  42.     for (int i = 0; i <= n; i++)
  43.         for (int j = 0; j <= m; j++)
  44.             for (int mask = 0; mask < BIT(m); mask++)
  45.                 dp[i][j][mask] = -INF;
  46.     dp[0][m][0] = 0;
  47.     for (int i = 0; i < n; i++)
  48.         for (int j = 0; j <= m; j++)
  49.             for (int mask = 0; mask < BIT(m); mask++)
  50.             {
  51.                 if (dp[i][j][mask] == -INF)
  52.                     continue;
  53.                 // cout << i << ' ' << j << ' ' << mask << ' ' << dp[i][j][mask], el;
  54.                 for (int new_j = 0; new_j < m; new_j++)
  55.                 {
  56.                     if (!bit(mask, new_j) && cnt[i + 1][new_j])
  57.                     {
  58.                         if (j == m) // open new_j
  59.                             dp[i + 1][new_j][mask] = max(dp[i + 1][new_j][mask], dp[i][j][mask] + (m - new_j) * a[i + 1]);
  60.                         else // close j va open new_j
  61.                             dp[i + 1][new_j][mask | BIT(j)] = max(dp[i + 1][new_j][mask | BIT(j)], dp[i][j][mask] + (m - new_j) * a[i + 1]);
  62.                     }
  63.                 }
  64.                 if (j == m) // noi tiep doan trong
  65.                     dp[i + 1][j][mask] = max(dp[i + 1][j][mask], dp[i][j][mask]);
  66.                 if (cnt[i + 1][j]) // noi tiep j
  67.                     dp[i + 1][j][mask] = max(dp[i + 1][j][mask], dp[i][j][mask] + (m - j) * a[i + 1]);
  68.                 // dong doan j
  69.                 dp[i + 1][m][mask | BIT(j)] = max(dp[i + 1][m][mask | BIT(j)], dp[i][j][mask]);
  70.             }
  71.     ll ans = 0;
  72.     for (int j = 0; j <= m; j++)
  73.         for (int mask = 0; mask < BIT(m); mask++)
  74.             ans = max(ans, dp[n][j][mask]);
  75.     cout << S * m - ans;
  76. }
  77.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/g8Dlt6
language:
C++14 (gcc 8.3)
created:
1 day 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!