QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #703721 | #1078. Job Postings | TheZone | AC ✓ | 505ms | 4040kb | C++20 | 6.4kb | 2024-11-02 18:19:15 | 2024-11-02 18:19:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class X, class Y> X cmx(X &a, Y b) { a = max<X>(a, b); }
#define ary(k) array<int, k>
pair<int, vi> hungarian(const vector<vi> &a) {
if (a.empty()) return {0, {}};
int n = sz(a) + 1, m = sz(a[0]) + 1;
vi u(n), v(m), p(m), ans(n-1);
rep(i,1,n) {
p[0] = i;
int j0 = 0;
vi dist(m, INT_MAX), pre(m, -1);
vector<bool> done(m+1);
do {
done[j0] = true;
int i0 = p[j0], j1, delta = INT_MAX;
rep(j,1,m) if (!done[j]) {
auto cur = a[i0 - 1][j-1] - u[i0] - v[j];
if (cur < dist[j]) dist[j] = cur, pre[j] = j0;
if (dist[j] < delta) delta = dist[j], j1 = j;
}
rep(j, 0, m) {
if (done[j]) u[p[j]] += delta, v[j] -= delta;
else dist[j] -= delta;
}
j0 = j1;
} while (p[j0]);
while (j0) {
int j1 = pre[j0];
p[j0] = p[j1], j0 = j1;
}
}
rep(j,1,m) if (p[j]) ans[p[j] - 1] = j - 1;
return {-v[0], ans};
}
int pocz[1002], kon[1002];
signed main() {
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
while (true) {
int n, m;
cin >> m >> n;
if (n == 0 && m == 0)
break;
int aktu = 0;
for (int i = 0; i < m; i++) {
int p;
cin >> p;
pocz[i] = aktu;
kon[i] = aktu+p-1;
aktu += p;
}
vector<vi> cost(n, vi(aktu, 100000));
for (int i = 0; i < n; i++) {
int y;
cin >> y;
for (int j = 0; j < 4; j++) {
int c;
cin >> c;
for (int ii = pocz[c]; ii <= kon[c]; ii++) {
cost[i][ii] = -(y*4-j);
}
}
}
int res = hungarian(cost).FS;
cout << -res << "\n";
}
}
/*#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class X, class Y> X cmx(X &a, Y b) { a = max<X>(a, b); }
#define ary(k) array<int, k>
pair<int, vi> hungarian(const vector<vi> &a) {
if (a.empty()) return {0, {}};
int n = sz(a) + 1, m = sz(a[0]) + 1;
vi u(n), v(m), p(m), ans(n-1);
rep(i,1,n) {
p[0] = i;
int j0 = 0;
vi dist(m, INT_MAX), pre(m, -1);
vector<bool> done(m+1);
do {
done[j0] = true;
int i0 = p[j0], j1, delta = INT_MAX;
rep(j,1,m) if (!done[j]) {
auto cur = a[i0 - 1][j-1] - u[i0] - v[j];
if (cur < dist[j]) dist[j] = cur, pre[j] = j0;
if (dist[j] < delta) delta = dist[j], j1 = j;
}
rep(j, 0, m) {
if (done[j]) u[p[j]] += delta, v[j] -= delta;
else dist[j] -= delta;
}
j0 = j1;
} while (p[j0]);
while (j0) {
int j1 = pre[j0];
p[j0] = p[j1], j0 = j1;
}
}
rep(j,1,m) if (p[j]) ans[p[j] - 1] = j - 1;
return {-v[0], ans};
}
int pocz[1002], kon[1002];
signed main() {
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
while (true) {
int n, m;
cin >> m >> n;
if (n == 0 && m == 0)
break;
int aktu = 0;
for (int i = 0; i < m; i++) {
int p;
cin >> p;
pocz[i] = aktu;
kon[i] = aktu+p-1;
aktu += p;
}
vector<vi> cost(n, vi(aktu, 100000));
for (int i = 0; i < n; i++) {
int y;
cin >> y;
for (int j = 0; j < 4; j++) {
int c;
cin >> c;
for (int ii = pocz[c]; ii <= kon[c]; ii++) {
cost[i][ii] = -(y*4-j);
}
}
}
int res = hungarian(cost).FS;
cout << -res << "\n";
}
}#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class X, class Y> X cmx(X &a, Y b) { a = max<X>(a, b); }
#define ary(k) array<int, k>
pair<int, vi> hungarian(const vector<vi> &a) {
if (a.empty()) return {0, {}};
int n = sz(a) + 1, m = sz(a[0]) + 1;
vi u(n), v(m), p(m), ans(n-1);
rep(i,1,n) {
p[0] = i;
int j0 = 0;
vi dist(m, INT_MAX), pre(m, -1);
vector<bool> done(m+1);
do {
done[j0] = true;
int i0 = p[j0], j1, delta = INT_MAX;
rep(j,1,m) if (!done[j]) {
auto cur = a[i0 - 1][j-1] - u[i0] - v[j];
if (cur < dist[j]) dist[j] = cur, pre[j] = j0;
if (dist[j] < delta) delta = dist[j], j1 = j;
}
rep(j, 0, m) {
cin >> m >> n;
if (n == 0 && m == 0)
break;
int aktu = 0;
for (int i = 0; i < m; i++) {
int p;
cin >> p;
pocz[i] = aktu;
kon[i] = aktu+p-1;
aktu += p;
}
vector<vi> cost(n, vi(aktu, 100000));
for (int i = 0; i < n; i++) {
int y;
cin >> y;
for (int j = 0; j < 4; j++) {
int c;
cin >> c;
for (int ii = pocz[c]; ii <= kon[c]; ii++) {
cost[i][ii] = -(y*4-j);
}
}
}
int res = hungarian(cost).FS;
cout << -res << "\n";
}
}k
k
k
k
k
k
k
k
k
l
k
k
j*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 505ms
memory: 4040kb
input:
4 4 1 1 1 1 1 0 1 2 3 2 0 1 2 3 3 0 1 2 3 3 0 1 2 3 4 4 4 4 4 4 1 0 1 2 3 2 0 1 2 3 3 0 1 2 3 3 0 1 2 3 4 4 1 1 1 1 3 0 1 2 3 3 3 0 1 2 3 2 3 0 1 3 1 2 3 0 4 5 1 1 1 10 3 1 2 3 0 3 2 3 0 1 3 3 0 1 2 3 0 1 2 3 3 1 2 3 0 70 70 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...
output:
30 36 48 58 840 208 536 24 236 272 404 460 540 112 244 336 136 104 536 572 464 400 392 56 104 360 236 320 476 584 88 224 388 460 352 272 108 216 632 596 572 368 12 20 516 88 108 12 452 152 236 108 284 224 420 236 48 164 220 416 384 500 252 548 160 20 136 304 64 452 172 264 568 488 584 400 80 40 332 ...
result:
ok 5009 lines