fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define nmax int(1e5+3)
  3. #define oo (int)(1e18)
  4. using namespace std;
  5. int n, m, a[nmax], c[nmax], S=(1<<10);
  6. int main(){
  7.     cin >> n >> m;
  8.     for (int i = 0; i < n; i++) cin >> a[i];
  9.     for (int j = 1; j <= m; j++){
  10.         int x, y; cin >> x >> y;
  11.         x--; y--;
  12.         if (1 <= y && y-x <= 10)c[y] |= (1<<(y-x-1));
  13.     }
  14.     vector<int> dp0(S, oo), dp1(S);
  15.     dp0[0] = 0;
  16.     for (int i = 0; i < n; i++){
  17.         fill(dp1.begin(), dp1.end(), oo);
  18.         for (int mask = 0; mask < S; mask++){
  19.             if (dp0[mask] == oo) continue;
  20.             if ((mask & c[i]) == c[i]){
  21.                 int nmask = ((mask << 1) & (S-1)) | 1;
  22.                 dp1[nmask]=min(dp1[nmask], dp0[mask] + a[i]);
  23.             }
  24.             int m = (mask << 1) & (S-1);
  25.             dp1[m]=min(dp1[m], dp0[mask]);
  26.         }
  27.         swap(dp1, dp0);
  28.     }
  29.     int res = oo;
  30.     for (int mask = 0; mask < S; mask++) res=min(res, dp0[mask]);
  31.     cout << (res < 0 ? -res : 0);
  32.     return 0;
  33. }
  34. /*
  35.     Solve by: Truong Tuan Kiet - Informatics K36. Solve in 10h45 - 30/6/2025
  36. */
  37.  
  38.  
  39.  
  40.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4JHIgV
language:
C++14 (gcc 8.3)
created:
15 hours 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!