fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fi first
  5. #define se second
  6. #define MP make_pair
  7. #define PB push_back
  8. #define ll long long
  9. #define pii pair<int, int>
  10. #define SZ(a) int(a.size())
  11. #define ALL(a) a.begin(), a.end()
  12. #define MS(a, v) memset(a, v, sizeof a)
  13. #define REP(i, n) for(int i = 0; i < n; ++ i)
  14. #define FOR(i, a, b) for(int i = (a); i <= (b); ++ i)
  15. #define FOD(i, a, b) for(int i = (a); i >= (b); -- i)
  16. #define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".out", "w", stdout)
  17.  
  18. template<class X, class Y>
  19.         bool maximize(X & x, const Y & y){
  20.                 if(x < y){
  21.                         x = y;
  22.                         return true;
  23.                 }
  24.                 else return false;
  25.         }
  26.  
  27. template<class X, class Y>
  28.         bool minimize(X & x, const Y & y){
  29.                 if(x > y){
  30.                         x = y;
  31.                         return true;
  32.                 }
  33.                 else return false;
  34.         }
  35.  
  36. const int MAXN = 100005;
  37. const int MOD = 1e9 + 7;
  38. const ll INF = 1e18;
  39.  
  40. int n, m, c[MAXN], b[MAXN];
  41. vector <int> g[MAXN];
  42.  
  43. void solve(void){
  44.         cin >> n >> m;
  45.         FOR(i, 1, n) cin >> c[i];
  46.         FOR(i, 1, m){
  47.                 int u, v; cin >> u >> v;
  48.                 g[v].PB(u);
  49.         }
  50.  
  51.         FOR(i, 1, n){
  52.                 for(int v : g[i])
  53.                         b[i] |= 1 << (i - 1 - v);
  54.         }
  55.  
  56.         vector <ll> dp, f;
  57.         dp.assign(1025, 0);
  58.         f.assign(1025, 4e18);
  59.  
  60.         ll res = 0;
  61.  
  62.         FOR(i, 1, n){
  63.                 REP(mask, 1024){
  64.                         minimize(res, dp[mask]);
  65.                         minimize(f[(mask << 1 & 1023)], dp[mask]);
  66.                         if((mask | b[i]) == mask)
  67.                                 minimize(f[(mask << 1 & 1023 ^ 1)], dp[mask] + c[i]);
  68.                 }
  69.                 dp = f;
  70.                 REP(mask, 1024)
  71.                         f[mask] = 4e18;
  72.         }
  73.         REP(mask, 1024)
  74.                 minimize(res, dp[mask]);
  75.         cout << -res;
  76. }
  77.  
  78. int main(void){
  79.  
  80.         ios_base :: sync_with_stdio(0);
  81.         cin.tie(0); cout.tie(0);
  82.  
  83.         #define TaZinh "test"
  84.  
  85.         if(fopen(TaZinh".inp", "r"))
  86.                 TSun(TaZinh);
  87.  
  88.         int Sun = 1;
  89. //        cin >> Sun;
  90.         REP(love, Sun) solve();
  91.  
  92.         return 0;
  93. }
  94.  
Success #stdin #stdout 0.01s 6232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/g4qrBT
language:
C++ (gcc 8.3)
created:
6 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!