fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll              long long
  3. #define el              cout << '\n'
  4. #define f(i, a, b)      for(long long i = a; i <= b; ++i)
  5. #define fv(i, a, b)     for(long long i = a; i >= b; i--)
  6. #define ft              first
  7. #define sd              second
  8. #define pll             pair<long long,long long>
  9. #define vll             vector<long long>
  10. #define ep              emplace_back
  11. #define pb              push_back
  12. using namespace std;
  13. const ll oo = 1e18+123, N = 2e5+5, MOD = 1e9+7;
  14.  
  15. void Initialization();
  16.  
  17. ll test, n, m, ans, k, c[N], deg[N], topo[N], dp[N][31];
  18. vector<vll> E;
  19.  
  20. void solve() {
  21.     queue<pll> q;
  22.     f(i, 1, n) {
  23.         dp[i][1] = c[i]; q.push({i, 0}); q.push({i, 1});
  24.     }
  25.     while(!q.empty()) {
  26.         int u = q.front().ft, i = q.front().sd; q.pop();
  27.         for(int v : E[u]) {
  28.             if(dp[v][i + 1] < dp[u][i] + c[v]) {
  29.                 dp[v][i + 1] = dp[u][i] + c[v];
  30.                 q.push({v, i + 1});
  31.             } 
  32.             if(dp[v][i] < dp[u][i]) {
  33.                 dp[v][i] = dp[u][i];
  34.                 q.push({v, i});
  35.             } 
  36.  
  37.         } 
  38.     }
  39.     f(u, 1, n) f(z, 1, k) ans = max(ans, dp[u][z]);
  40.     cout << ans;
  41. }
  42.  
  43. void topo_sort() {
  44.     queue<ll> q;
  45.     f(i, 1, n) if(!deg[i]) q.push(i);
  46.  
  47.     vll vis(n + 1, 0);
  48.     ll cnt = 0;
  49.     while(!q.empty()) {
  50.         ll u = q.front(); q.pop();  
  51.         if(vis[u]) continue; vis[u] = 1;
  52.         topo[++cnt] = u;
  53.         for(ll v : E[u]) {
  54.             deg[v]--;
  55.             if(deg[v] == 0) q.push(v);
  56.         }
  57.     }
  58. }
  59.  
  60. void sub1() {
  61.     sort(c + 1, c + n + 1);
  62.     fv(i, n, n - k + 1) ans += c[i];
  63.     cout << ans; 
  64. }
  65.  
  66. void sub23() {
  67.     topo_sort();
  68.  
  69.     f(i, 1, n) {
  70.         ll u = topo[i];
  71.         dp[u][1] = max(c[u], dp[u][1]);
  72.         for(int v : E[u]) 
  73.             f(z, 1, k) 
  74.                 dp[v][z] = max(
  75.                     dp[v][z], 
  76.                     max(dp[u][z - 1] + c[v], dp[u][z])
  77.                 ); 
  78.     }
  79.  
  80.     f(u, 1, n) f(z, 1, k) ans = max(ans, dp[u][z]);
  81.     cout << ans;
  82. }
  83.  
  84. ll low[N], num[N], tp[N], Time, cc;
  85. bool dele[N];
  86. stack<ll> st;
  87. vector<vll> ma(1);
  88.  
  89. void tarjan (ll u) {
  90.     low[u] = num[u] = ++Time;
  91.     st.push(u);
  92.  
  93.     for(ll v : E[u]) {
  94.         if(dele[v]) continue;
  95.         if(num[v]) low[u] = min(low[u], num[v]);
  96.         else {
  97.             tarjan(v);
  98.             low[u] = min(low[u], low[v]);
  99.         }
  100.     }
  101.  
  102.     if(num[u] == low[u]) {
  103.         cc++;
  104.         ll v = 0;
  105.         vll dmp;
  106.  
  107.         while(v != u) {
  108.             v= st.top(); st.pop();
  109.             dmp.pb(c[v]);
  110.             tp[v] = cc;
  111.             dele[v] = 1;
  112.         }
  113.         sort(dmp.begin(), dmp.end(), greater<ll>());
  114.         ma.pb({0});
  115.         ll sum = 0;
  116.         for(ll x : dmp) {
  117.             sum += x; ma[cc].pb(sum);
  118.         }
  119.         // cout << cc << '.', el;
  120.         // for(ll x : dmp) cout << x << ' '; el;
  121.         // for(ll x : ma[cc]) cout << x << ' '; el;
  122.     }
  123. }
  124.  
  125. ll degd[N];
  126. vector<vll> Ed, Er;
  127.  
  128. void sub4() {
  129.     f(u, 1, n) if(num[u] == 0) tarjan(u);
  130.     Ed.resize(cc + 1);
  131.     Er.resize(cc + 1);
  132.     f(u, 1, n) 
  133.         for(ll v : E[u]) if(tp[u] != tp[v]) {
  134.             Er[tp[v]].pb(tp[u]);
  135.             Ed[tp[u]].pb(tp[v]); degd[tp[v]] ++;
  136.         }
  137.  
  138.     queue<ll> q;
  139.     f(i, 1, cc) if(!degd[i]) q.push(i);
  140.  
  141.     ll cnt = 0;
  142.     // f(i, 1, cc) cout << i << ' '; el;
  143.     // f(i, 1, cc) cout << degd[i] << ' '; el;
  144.     // f(i, 1, cc) {
  145.     //     cout << i << ":";
  146.     //     for(ll v : Er[i]) cout << v << ' '; el;
  147.     // }
  148.     while(!q.empty()) {
  149.         ll u = q.front(); q.pop();  
  150.  
  151.         topo[++cnt] = u;
  152.         for(ll v : Ed[u]) {
  153.             degd[v]--;
  154.             if(degd[v] == 0) q.push(v);
  155.         }
  156.     }
  157.  
  158.  
  159.     f(o, 1, cc) {
  160.         ll u = topo[o];
  161.         f(i, 1, ma.size() - 1) dp[u][i] = ma[u][i];
  162.  
  163.         f(z, 1, k) {
  164.             for(ll v : Er[u]) {
  165.                 f(j, 0, min(z, (ll) (ma[u].size() - 1))) 
  166.                     dp[u][z] = max(
  167.                         dp[u][z], 
  168.                         dp[v][z - j] + ma[u][j]
  169.                     );
  170.             }
  171.         }
  172.     }
  173.  
  174.     // cout << cc, el;
  175.  
  176.     // f(i, 1, cc) cout << topo[i] << ' '; el;
  177.  
  178.  
  179.     // f(i, 1, n) cout << i << ' '; el;
  180.     // f(i, 1, n) cout << tp[i] << ' '; el;
  181.  
  182.     // f(u, 1, cc) {
  183.     //     f(z, 1, k) {
  184.     //         cout << dp[u][z] << ' ';
  185.     //     } el;
  186.     // }
  187.  
  188.     f(u, 1, cc) f(z, 1, k) ans = max(ans, dp[u][z]);
  189.     cout << ans;
  190.  
  191. }
  192.  
  193. int main()
  194. {
  195.     Initialization();
  196.  
  197.     cin >> n >> m >> k;
  198.     E.resize(n + 1);
  199.     f(i, 1, n) cin >> c[i];
  200.  
  201.     ll u, v;
  202.     f(i, 1, m) {
  203.         cin >> u >> v;
  204.         E[u].pb(v); deg[v] ++;
  205.     }
  206.  
  207.     //if(n < 20) sub1();
  208.     // solve(); return 0;
  209.     sub4();
  210.  
  211.  
  212.  
  213.     return 0;
  214. }
  215.  
  216. void Initialization() {
  217.     #define thukem "produce"
  218.     if(fopen(thukem".inp", "r")) {
  219.         freopen(thukem".inp","r",stdin);
  220.         freopen(thukem".out","w",stdout);
  221.     }
  222.     ios_base::sync_with_stdio(false);
  223.     cin.tie(0); cout.tie(0);
  224. }
Success #stdin #stdout 0s 5664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hSMOpC
language:
C++14 (gcc 8.3)
created:
12 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!