結果
問題 | No.1341 真ん中を入れ替えて門松列 |
ユーザー | chineristAC |
提出日時 | 2021-01-15 22:46:33 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,322 bytes |
コンパイル時間 | 2,670 ms |
コンパイル使用メモリ | 151,412 KB |
実行使用メモリ | 605,696 KB |
最終ジャッジ日時 | 2024-05-05 00:47:29 |
合計ジャッジ時間 | 6,354 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,624 KB |
testcase_01 | AC | 2 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 | 96 ms
5,376 KB |
testcase_07 | TLE | - |
testcase_08 | AC | 15 ms
5,376 KB |
testcase_09 | MLE | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<iostream> #include<vector> #include<string> #include<map> #include<set> #include<queue> #include<algorithm> #include<cmath> #include<iomanip> #include<random> #include<stdio.h> using namespace std; typedef long long ll; typedef pair<ll,ll> p; 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 10; 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; } } } }; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); ll n,m; cin>>n>>m; vector<p> min_AC = {}; vector<p> max_AC = {}; vector<ll> B = {}; ll a,b,c; for (int i=0;i<n;i++){ cin>>a>>b>>c; if (a<c){ min_AC.push_back(make_pair(a,i)); max_AC.push_back(make_pair(c,i)); } else{ min_AC.push_back(make_pair(c,i)); max_AC.push_back(make_pair(a,i)); } B.push_back(b); } PrimalDual<ll,ll> G(3*n+2); for (int i=0;i<n;i++){ G.add_edge(0,i+1,1,0); } sort(min_AC.begin(),min_AC.end()); ll pos,next,val; for (int i=0;i<n-1;i++){ pos = min_AC[i].second; next = min_AC[i+1].second; G.add_edge(n+1+pos,n+1+next,10000000000000000,0); } for (int i=0;i<n;i++){ pos = min_AC[i].second; val = max_AC[pos].first; G.add_edge(n+1+pos,2*n+1+pos,1,-val); } for (int i=0;i<n;i++){ b = B[i]; for (int j=0;j<n;j++){ if (min_AC[j].first > b){ G.add_edge(i+1,n+1+min_AC[j].second,1,0); break; } } } sort(max_AC.begin(),max_AC.end()); for (int i=n-1;i>0;i--){ pos = max_AC[i].second; next = max_AC[i-1].second; G.add_edge(2*n+1+pos,2*n+1+next,1000000000000000,0); } for (int i=0;i<n;i++){ b = B[i]; for (int j=n-1;j>-1;j--){ if (max_AC[j].first < b){ G.add_edge(i+1,2*n+1+max_AC[j].second,1,-b); } } } for (int i=0;i<n;i++){ G.add_edge(2*n+1+i,3*n+1,1,0); } ll res = G.min_cost_flow(0,3*n+1,n); if (res!=10){ cout<<"YES"<<endl; if (-res >= m){ cout<<"KADOMATSU!"<<endl; } else{ cout<<"NO"<<endl; } } else{ cout<<"NO"<<endl; } }