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 |
|
|
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 |