fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll INF = (ll)9e18;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n, m;
  11.     if (!(cin >> n >> m)) return 0;
  12.     vector<ll> a(n+1);
  13.     for (int i = 1; i <= n; ++i) cin >> a[i];
  14.     vector<int> L(m), R(m);
  15.     for (int i = 0; i < m; ++i) cin >> L[i] >> R[i];
  16.  
  17.     // prefix sum
  18.     vector<ll> P(n+1, 0);
  19.     for (int i = 1; i <= n; ++i) P[i] = P[i-1] + a[i];
  20.  
  21.     // bestVal[r][i] = minimal sum of a[i..j] for j in [i, R[r]]
  22.     // bestEnd[r][i] = index j giving that minimum. valid only for i in [L[r], R[r]]
  23.     vector<vector<ll>> bestVal(m, vector<ll>(n+2, INF));
  24.     vector<vector<int>> bestEnd(m, vector<int>(n+2, -1));
  25.  
  26.     for (int r = 0; r < m; ++r) {
  27.         int l = L[r], rr = R[r];
  28.         // compute suffix minimum of P[j] over j in [l..rr]
  29.         ll curMin = INF;
  30.         int curIdx = -1;
  31.         for (int j = rr; j >= l; --j) {
  32.             if (P[j] <= curMin) {
  33.                 curMin = P[j];
  34.                 curIdx = j;
  35.             }
  36.             // for start = j, minimal P[j'] for j' >= j is curMin at curIdx
  37.             // sum(a[j..curIdx]) = curMin - P[j-1]
  38.             bestVal[r][j] = curMin - P[j-1];
  39.             bestEnd[r][j] = curIdx;
  40.         }
  41.     }
  42.  
  43.     int MSK = 1 << m;
  44.     // dp[pos][mask] : minimal total when we've processed positions < pos, and used rounds = mask
  45.     // pos ranges 1..n+1
  46.     vector<vector<ll>> dp(n+2, vector<ll>(MSK, INF));
  47.     dp[1][0] = 0;
  48.  
  49.     for (int pos = 1; pos <= n; ++pos) {
  50.         for (int mask = 0; mask < MSK; ++mask) {
  51.             ll cur = dp[pos][mask];
  52.             if (cur == INF) continue;
  53.             // option 1: skip pos (no segment starts at pos)
  54.             if (dp[pos+1][mask] > cur) dp[pos+1][mask] = cur;
  55.  
  56.             // option 2: try to start a segment at pos assigned to some unused round r
  57.             for (int r = 0; r < m; ++r) {
  58.                 if (mask & (1 << r)) continue; // already used
  59.                 if (pos < L[r] || pos > R[r]) continue; // cannot start here
  60.                 ll val = bestVal[r][pos];
  61.                 int endp = bestEnd[r][pos];
  62.                 if (endp == -1) continue; // shouldn't happen but safe-guard
  63.                 int nmask = mask | (1 << r);
  64.                 int nextPos = endp + 1;
  65.                 if (dp[nextPos][nmask] > cur + val) dp[nextPos][nmask] = cur + val;
  66.             }
  67.         }
  68.     }
  69.  
  70.     // also allow reaching n+1 by skipping from n+1? Already dp updated until n+1.
  71.     ll ans = INF;
  72.     for (int mask = 0; mask < MSK; ++mask) {
  73.         ans = min(ans, dp[n+1][mask]);
  74.     }
  75.  
  76.     // print minimal S
  77.     cout << ans << '\n';
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/xjGtdT
language:
C++ (gcc 8.3)
created:
4 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!