結果
問題 |
No.3306 Life is Easy?
|
ユーザー |
|
提出日時 | 2025-07-09 06:33:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 165 ms / 2,000 ms |
コード長 | 3,045 bytes |
コンパイル時間 | 2,538 ms |
コンパイル使用メモリ | 205,704 KB |
実行使用メモリ | 12,032 KB |
最終ジャッジ日時 | 2025-07-09 06:33:06 |
合計ジャッジ時間 | 4,949 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long INF = 3LL << 59; // https://judge.yosupo.jp/submission/201242 vector<int> hungarian(int n, const vector<vector<long long> > &a) { vector<int> p(n), q(n); for (int i = 0; i < n; i++) { p[i] = i; q[i] = i; } vector<long long> h(n); for (int i = 1; i < n; i++) { vector<long long> d(n, INF); vector<int> pre(n, -1); for (int j = 0; j < i; j++) { d[q[j]] = a[i][j] - a[q[j]][j] - h[q[j]]; pre[q[j]] = i; } vector<bool> used(n, false); for (int j = 0; j < i; j++) { long long mind = INF; int v = -1; for (int k = 0; k < i; k++) { if (!used[k] && mind > d[k]) { mind = d[k]; v = k; } } used[v] = true; for (int k = 0; k < i; k++) { long long nd = d[v] + a[v][k] - a[q[k]][k] - (h[q[k]] - h[v]); if (d[q[k]] > nd) { d[q[k]] = nd; pre[q[k]] = v; } } } long long best = a[i][i]; int pos = -1; for (int j = 0; j < i; j++) { if (best > d[j] + h[j] + a[j][i]) { best = d[j] + h[j] + a[j][i]; pos = j; } } for (int j = 0; j < i; j++) { h[j] += d[j]; } int nxt = i; while (pos != -1) { q[nxt] = pos; swap(nxt, p[pos]); pos = pre[pos]; } } return p; } int main(){ int n, m; cin >> n >> m; vector<vector<long long>> a(n, vector<long long>(m)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> a[i][j]; } } int d = n / 2; if(m == 1){ long long ans = 0; for(int i = 0; i < d; i++){ ans -= a[i][0]; ans += a[i + d + n % 2][0]; } cout << ans << endl; return 0; }else if(m == 2){ vector<vector<long long>> dp1(d + 1, vector<long long>(d + 1, INF)), dp2(d + 1, vector<long long>(d + 1, -INF)); dp1[0][0] = dp2[0][0] = 0; for(int i = 0; i < d; i++){ for(int j = 0; j <= i; j++){ dp1[i + 1][j] = min(dp1[i + 1][j], dp1[i][j] + a[i][0]); dp1[i + 1][j + 1] = min(dp1[i + 1][j + 1], dp1[i][j] + a[i][1]); } } for(int i = 0; i < d; i++){ for(int j = 0; j <= i; j++){ dp2[i + 1][j] = max(dp2[i + 1][j], dp2[i][j] + a[i + d + n % 2][0]); dp2[i + 1][j + 1] = max(dp2[i + 1][j + 1], dp2[i][j] + a[i + d + n % 2][1]); } } long long ans = 0; for(int i = 0; i <= d; i++){ ans = max(ans, dp2[d][i] - dp1[d][i]); } cout << ans << endl; return 0; } vector<vector<long long>> w(d, vector<long long>(d, 0)); for(int i = 0; i < d; i++){ for(int j = 0; j < d; j++){ long long val = 0; for(int k = 0; k < m; k++){ val = max(val, a[j + d + n % 2][k] - a[i][k]); } w[i][j] = val * -1; } } auto res = hungarian(d, w); long long ans = 0; for(int i = 0; i < d; i++){ ans += w[i][res[i]] * -1; } cout << ans << endl; }