結果
問題 | No.1341 真ん中を入れ替えて門松列 |
ユーザー | tatyam |
提出日時 | 2021-01-16 03:48:52 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,912 bytes |
コンパイル時間 | 3,019 ms |
コンパイル使用メモリ | 224,256 KB |
実行使用メモリ | 12,032 KB |
最終ジャッジ日時 | 2024-05-05 04:27:45 |
合計ジャッジ時間 | 9,665 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,624 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 25 ms
5,376 KB |
testcase_07 | TLE | - |
testcase_08 | AC | 7 ms
5,888 KB |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
ソースコード
#include <bits/stdc++.h> using namespace std; template< typename flow_t, typename cost_t > struct PrimalDual { const cost_t INF; struct edge { int to; flow_t cap; cost_t cost; int rev; bool isrev; }; vector< vector< edge > > graph; vector< cost_t > potential, min_cost; vector< int > prevv, preve; PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {} void add_edge(int from, int to, flow_t cap, cost_t cost) { graph[from].emplace_back((edge) {to, cap, cost, (int) graph[to].size(), false}); graph[to].emplace_back((edge) {from, 0, -cost, (int) graph[from].size() - 1, true}); } cost_t min_cost_flow(int s, int t, flow_t f) { int V = (int) graph.size(); cost_t ret = 0; using Pi = pair< cost_t, int >; priority_queue< Pi, vector< Pi >, greater< Pi > > que; potential.assign(V, 0); preve.assign(V, -1); prevv.assign(V, -1); while(f > 0) { min_cost.assign(V, INF); que.emplace(0, s); min_cost[s] = 0; while(!que.empty()) { Pi p = que.top(); que.pop(); if(min_cost[p.second] < p.first) continue; for(int i = 0; i < graph[p.second].size(); i++) { edge &e = graph[p.second][i]; cost_t nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to]; if(e.cap > 0 && min_cost[e.to] > nextCost) { min_cost[e.to] = nextCost; prevv[e.to] = p.second, preve[e.to] = i; que.emplace(min_cost[e.to], e.to); } } } if(min_cost[t] == INF) return -1; for(int v = 0; v < V; v++) potential[v] += min_cost[v]; flow_t addflow = f; for(int v = t; v != s; v = prevv[v]) { addflow = min(addflow, graph[prevv[v]][preve[v]].cap); } f -= addflow; ret += addflow * potential[t]; for(int v = t; v != s; v = prevv[v]) { edge &e = graph[prevv[v]][preve[v]]; e.cap -= addflow; graph[v][e.rev].cap += addflow; } } return ret; } void output() { for(int i = 0; i < graph.size(); i++) { for(auto &e : graph[i]) { if(e.isrev) continue; auto &rev_e = graph[e.to][e.rev]; cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << rev_e.cap + e.cap << ")" << endl; } } } }; using ll = int64_t; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll N, M; cin >> N >> M; vector<ll> A(N), B(N), C(N); for(ll i = 0; i < N; i++){ cin >> A[i] >> B[i] >> C[i]; if(A[i] > C[i]) swap(A[i], C[i]); } PrimalDual<ll, ll> g(N * 4 + 2); const ll S = N * 4, T = S + 1; for(ll i = 0; i < N; i++) g.add_edge(S, i, 1, 0); vector<ll> index(N); iota(index.begin(), index.end(), 0); sort(index.begin(), index.end(), [&](ll x, ll y){ return A[x] < A[y]; }); for(ll i = 0; i < N; i++){ auto p = partition_point(index.begin(), index.end(), [&](ll j){ return A[j] <= B[i]; }); if(p == index.end()) continue; g.add_edge(i, *p + N, 1, 0); } for(ll i = 0; i + 1 < N; i++) g.add_edge(index[i] + N, index[i + 1] + N, N, 0); for(ll i = 0; i < N; i++) g.add_edge(i + N, i + N * 3, 1, -C[i]); sort(index.begin(), index.end(), [&](ll x, ll y){ return C[x] > C[y]; }); for(ll i = 0; i < N; i++){ auto p = partition_point(index.begin(), index.end(), [&](ll j){ return C[j] >= B[i]; }); if(p == index.end()) continue; g.add_edge(i, *p + N * 2, 1, -B[i]); } for(ll i = 0; i + 1 < N; i++) g.add_edge(index[i] + N * 2, index[i + 1] + N * 2, N, 0); for(ll i = 0; i < N; i++) g.add_edge(i + N * 2, i + N * 3, 1, 0); for(ll i = 0; i < N; i++) g.add_edge(i + N * 3, T, 1, 0); ll ans = g.min_cost_flow(S, T, N); if(ans == -1) return puts("NO") & 0; puts("YES"); puts(-ans >= M ? "KADOMATSU!" : "NO"); }