Submission #47027114


Source Code Expand

/*
Author : Hocky Yudhiono
Sab 28 Okt 2023 07:25:23
*/

#include "bits/stdc++.h"
using namespace std;

typedef long long LL;
typedef long long ll;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<LL, LL> PLL;
typedef pair<LL, LL> pll;
typedef long double ld;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define popf pop_front
#define pf push_front
#define popb pop_back
#define pb push_back
#define fi first
#define se second

const double EPS = 1e-9;
const int INFMEM = 63;

// Do dir^1 to get reverse direction
const int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
const char dch[4] = {'R', 'L', 'D', 'U'};

// Do (dir + 2)%4 to get reverse direction
// const int dx[8] = {-1,0,1,0,-1,1,1,-1};
// const int dy[8] = {0,1,0,-1,1,1,-1,-1};
// const char dch[4] = {'U','R','D','L'};
const double PI = 3.141592653589793;

inline void fasterios() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
}
#define endl '\n'
const int MOD = 1000000007;
// const int MOD = 998244353;

const int V = 100;
LL profit[V + 5];

struct PushRelabel {
  struct Edge {
    int dest, back;
    ll f, c;
  };
  vector<vector<Edge>> g;
  vector<ll> ec;
  vector<Edge*> cur;
  vector<vi> hs; vi H;
  PushRelabel(int n) : g(n), ec(n), cur(n), hs(2 * n), H(n) {}

  void addEdge(int s, int t, ll cap, ll rcap = 0) {
    // cout << s << " " << t << " " << cap << endl;
    if (s == t) return;
    g[s].push_back({t, sz(g[t]), 0, cap});
    g[t].push_back({s, sz(g[s]) - 1, 0, rcap});
  }

  void addFlow(Edge& e, ll f) {
    Edge &back = g[e.dest][e.back];
    if (!ec[e.dest] && f) hs[H[e.dest]].push_back(e.dest);
    e.f += f; e.c -= f; ec[e.dest] += f;
    back.f -= f; back.c += f; ec[back.dest] -= f;
  }
  ll calc(int s, int t) {
    int v = sz(g); H[s] = v; ec[t] = 1;
    vi co(2 * v); co[0] = v - 1;
    rep(i, 0, v) cur[i] = g[i].data();
    for (Edge& e : g[s]) addFlow(e, e.c);

    for (int hi = 0;;) {
      while (hs[hi].empty()) if (!hi--) return -ec[s];
      int u = hs[hi].back(); hs[hi].pop_back();
      while (ec[u] > 0)  // discharge u
        if (cur[u] == g[u].data() + sz(g[u])) {
          H[u] = 1e9;
          for (Edge& e : g[u]) if (e.c && H[u] > H[e.dest] + 1)
              H[u] = H[e.dest] + 1, cur[u] = &e;
          if (++co[H[u]], !--co[hi] && hi < v)
            rep(i, 0, v) if (hi < H[i] && H[i] < v)
              --co[H[i]], H[i] = v + 1;
          hi = H[u];
        } else if (cur[u]->c && H[u] == H[cur[u]->dest] + 1)
          addFlow(*cur[u], min(ec[u], cur[u]->c));
        else ++cur[u];
    }
  }
  bool leftOfMinCut(int a) { return H[a] >= sz(g); }
};

LL getSkillIndex(LL skill, LL level) {
  if(level == 0) return 0;
  return (skill - 1) * 5 + level;
}

LL getAchievementIndex(LL pos) {
  return 250 + pos;
}

int main() {
  fasterios();
  LL n, m; cin >> n >> m;
  vector <LL> c(n + 5);
  for (int i = 1; i <= n; i++) cin >> c[i];
  // 5 level aja
  // 1 2 3 4 5 => 6 7 8 9 10 // (skill - 1) * 5 + level
  vector <LL> val(m + 5);
  for (int i = 1; i <= m; i++) cin >> val[i];
  // Achievement itu 250 + 5 1 .. M,

  PushRelabel solve(305);
  // Construct the dag
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      // Level of skill j to unlock i is at least L[i][j]
      int tmp; cin >> tmp;
      solve.addEdge(getSkillIndex(j, tmp), getAchievementIndex(i), INT_MAX);
    }
  }
  LL ans = 0;
  LL ed = 301;
  for (int i = 1; i <= n; i++) {
    for(int j = 2;j <= 5;j++) {
      solve.addEdge(getSkillIndex(i, j - 1), getSkillIndex(i, j), INT_MAX);
      solve.addEdge(0, getSkillIndex(i, j), c[i]);
    }
  }
  
  for(int i = 1;i <= m;i++){
    ans += val[i];
    solve.addEdge(getAchievementIndex(i), ed, val[i]);
  }
  // cout << ans << endl;
  cout << ans - solve.calc(0, 301) << endl;
  // for (int i = 1; i <= n; i++) {
  //   int a, b; cin >> a >> b;
  //   isi[i] = a - b; int m; cin >> m;
  //   while (m--) { int v; cin >> v; edges.pb({i, v}); }
  // }
  // for (int i = 1; i <= n; i++) {
  //   int curcost = abs(isi[i]);
  //   if (isi[i] == curcost) ans += curcost, solve.add_edge(0, i, curcost);
  //   else solve.add_edge(i, n + 1, curcost);
  // }
  // trav(edge, edges) solve.add_edge(edge.se, edge.fi, INF);
  // cout << ans - solve.maxflow(0, n + 1) << endl;

}

Submission Info

Submission Time
Task G - Unlock Achievement
User hocky
Language C++ 20 (gcc 12.2)
Score 625
Code Size 4670 Byte
Status AC
Exec Time 2 ms
Memory 3772 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 625 / 625
Status
AC × 3
AC × 63
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All fumble_01.txt, fumble_02.txt, fumble_03.txt, fumble_04.txt, fumble_05.txt, killer_01.txt, killer_02.txt, killer_03.txt, killer_04.txt, killer_05.txt, killer_06.txt, killer_07.txt, killer_08.txt, killer_09.txt, killer_10.txt, killer_11.txt, killer_12.txt, killer_13.txt, killer_14.txt, killer_15.txt, nightmare_01.txt, nightmare_02.txt, nightmare_03.txt, nightmare_04.txt, nightmare_05.txt, nightmare_06.txt, nightmare_07.txt, nightmare_08.txt, nightmare_09.txt, nightmare_10.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
fumble_01.txt AC 1 ms 3440 KiB
fumble_02.txt AC 1 ms 3516 KiB
fumble_03.txt AC 1 ms 3592 KiB
fumble_04.txt AC 1 ms 3588 KiB
fumble_05.txt AC 1 ms 3508 KiB
killer_01.txt AC 1 ms 3648 KiB
killer_02.txt AC 1 ms 3716 KiB
killer_03.txt AC 1 ms 3560 KiB
killer_04.txt AC 1 ms 3540 KiB
killer_05.txt AC 1 ms 3528 KiB
killer_06.txt AC 1 ms 3568 KiB
killer_07.txt AC 1 ms 3592 KiB
killer_08.txt AC 1 ms 3584 KiB
killer_09.txt AC 1 ms 3612 KiB
killer_10.txt AC 1 ms 3580 KiB
killer_11.txt AC 1 ms 3564 KiB
killer_12.txt AC 2 ms 3680 KiB
killer_13.txt AC 1 ms 3560 KiB
killer_14.txt AC 1 ms 3536 KiB
killer_15.txt AC 1 ms 3612 KiB
nightmare_01.txt AC 1 ms 3572 KiB
nightmare_02.txt AC 1 ms 3600 KiB
nightmare_03.txt AC 1 ms 3732 KiB
nightmare_04.txt AC 1 ms 3448 KiB
nightmare_05.txt AC 1 ms 3508 KiB
nightmare_06.txt AC 1 ms 3564 KiB
nightmare_07.txt AC 1 ms 3720 KiB
nightmare_08.txt AC 1 ms 3524 KiB
nightmare_09.txt AC 1 ms 3528 KiB
nightmare_10.txt AC 1 ms 3592 KiB
random_01.txt AC 1 ms 3772 KiB
random_02.txt AC 1 ms 3676 KiB
random_03.txt AC 1 ms 3644 KiB
random_04.txt AC 1 ms 3700 KiB
random_05.txt AC 1 ms 3716 KiB
random_06.txt AC 1 ms 3768 KiB
random_07.txt AC 1 ms 3636 KiB
random_08.txt AC 1 ms 3580 KiB
random_09.txt AC 2 ms 3712 KiB
random_10.txt AC 1 ms 3672 KiB
random_11.txt AC 1 ms 3580 KiB
random_12.txt AC 1 ms 3540 KiB
random_13.txt AC 2 ms 3660 KiB
random_14.txt AC 1 ms 3360 KiB
random_15.txt AC 1 ms 3604 KiB
random_16.txt AC 1 ms 3556 KiB
random_17.txt AC 1 ms 3624 KiB
random_18.txt AC 1 ms 3544 KiB
random_19.txt AC 1 ms 3536 KiB
random_20.txt AC 1 ms 3428 KiB
random_21.txt AC 1 ms 3680 KiB
random_22.txt AC 1 ms 3580 KiB
random_23.txt AC 2 ms 3632 KiB
random_24.txt AC 1 ms 3588 KiB
random_25.txt AC 1 ms 3656 KiB
random_26.txt AC 1 ms 3628 KiB
random_27.txt AC 1 ms 3532 KiB
random_28.txt AC 1 ms 3604 KiB
random_29.txt AC 1 ms 3708 KiB
random_30.txt AC 1 ms 3424 KiB
sample_01.txt AC 1 ms 3352 KiB
sample_02.txt AC 1 ms 3408 KiB
sample_03.txt AC 1 ms 3460 KiB