fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define bint __int128
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. struct SCC {
  10.     int n, tim, countSCC;
  11.     vector<bool> stacked;
  12.     vector<int> in, low, id, st;
  13.  
  14.     vector<vector<int>> adj, comp, DAG;
  15.  
  16.     void init(int _n, vector<vector<int>>& graph) {
  17.         n = _n;
  18.         tim = 1;
  19.         countSCC = 0;
  20.  
  21.         adj = graph;
  22.         in.assign(n + 1, 0);
  23.         low.assign(n + 1, 0);
  24.         id.assign(n + 1, 0);
  25.         stacked.assign(n + 1, false);
  26.         st.clear(), comp.clear(), DAG.clear();
  27.  
  28.         for (int v = 1; v <= n; ++v) {
  29.             if (not in[v]) {
  30.                 dfs(v);
  31.             }
  32.         }
  33.     }
  34.  
  35.     void dfs(int v) {
  36.         in[v] = low[v] = tim++;
  37.         st.push_back(v), stacked[v] = true;
  38.  
  39.         for (int u : adj[v]) {
  40.             if (not in[u]) {
  41.                 dfs(u);
  42.                 low[v] = min(low[v], low[u]);
  43.             } else if (stacked[u]) {
  44.                 low[v] = min(low[v], in[u]);
  45.             }
  46.         }
  47.  
  48.         if (low[v] == in[v]) {
  49.             comp.push_back({});
  50.             int u = -1;
  51.             while (u != v) {
  52.                 u = st.back();
  53.                 st.pop_back(), stacked[u] = false;
  54.                 id[u] = countSCC;
  55.                 comp.back().push_back(u);
  56.             }
  57.             ++countSCC;
  58.         }
  59.     }
  60. };
  61.  
  62. void getShitDone() {
  63.     int n, m, k;
  64.     cin >> n >> m >> k;
  65.  
  66.     vector<int> c(n + 1);
  67.     for (int i = 1; i <= n; ++i) cin >> c[i];
  68.     vector<int> d(n + 1);
  69.     for (int i = 1; i <= n; ++i) cin >> d[i];
  70.  
  71.     vector< vector<int> > adj(n + 1);
  72.     for (int i = 1; i + 1 <= n; ++i)
  73.         adj[i].push_back(i + 1);
  74.  
  75.     for (int i = 0, u, v; i < m; ++i) {
  76.         cin >> u >> v;
  77.         adj[u].push_back(v);
  78.     }
  79.  
  80.     SCC sol; sol.init(n, adj);
  81.  
  82.     int ans = 0;
  83.     priority_queue<int> pq;
  84.     for (int i = 1; i <= n; ++i) {
  85.         ans += c[i];
  86.  
  87.         while ( not pq.empty() and k < d[i] )
  88.             ++k, ans += pq.top(), pq.pop();
  89.  
  90.         if (k < d[i]) {
  91.             cout << 0;
  92.             return;
  93.         } k += d[i];
  94.  
  95.         if ( i + 1 <= n ) {
  96.             if ( sol.id[i] != sol.id[i + 1] ) {
  97.                 for (int x : sol.comp[ sol.id[i] ])
  98.                     --k, pq.push(-c[x]);
  99.             }
  100.         } else {
  101.             for (int x : sol.comp[ sol.id[i] ])
  102.                 --k, pq.push(-c[x]);
  103.             while ( k < 0 and not pq.empty() )
  104.                 ++k, ans += pq.top(), pq.pop();
  105.         }
  106.     }
  107.  
  108.     cout << ans;
  109. }
  110.  
  111. signed main() {
  112.     _3bkarm
  113.  
  114.     int ts = 1;
  115.     cin >> ts;
  116.     while (ts--) {
  117.         getShitDone();
  118.         if (ts != 0) cout << '\n';
  119.     }
  120.  
  121.     return 0;
  122. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7XI4xX
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!