結果
問題 | No.1341 真ん中を入れ替えて門松列 |
ユーザー |
![]() |
提出日時 | 2021-01-15 23:32:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 939 ms / 2,000 ms |
コード長 | 13,475 bytes |
コンパイル時間 | 3,160 ms |
コンパイル使用メモリ | 225,140 KB |
最終ジャッジ日時 | 2025-01-17 20:46:18 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long MOD=1000000007;// const long long MOD=998244353;#define LOCAL#pragma region Macrostypedef long long ll;typedef __int128_t i128;typedef unsigned int uint;typedef unsigned long long ull;#define ALL(x) (x).begin(),(x).end()const int INF=1e9;const long long IINF=1e18;const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};const char dir[4]={'D','R','U','L'};template<typename T>istream &operator>>(istream &is,vector<T> &v){for (T &x:v) is >> x;return is;}template<typename T>ostream &operator<<(ostream &os,const vector<T> &v){for (int i=0;i<v.size();++i){os << v[i] << (i+1==v.size()?"": " ");}return os;}template<typename T,typename U>ostream &operator<<(ostream &os,const pair<T,U> &p){os << '(' << p.first << ',' << p.second << ')';return os;}template<typename T,typename U,typename V>ostream&operator<<(ostream &os,const tuple<T,U,V> &t){os << '(' << get<0>(t) << ',' << get<1>(t) << ',' << get<2>(t) << ')';return os;}template<typename T,typename U,typename V,typename W>ostream&operator<<(ostream &os,const tuple<T,U,V,W> &t){os << '(' << get<0>(t) << ',' << get<1>(t) << ',' << get<2>(t) << ',' << get<3>(t) << ')';return os;}template<typename T,typename U>ostream &operator<<(ostream &os,const map<T,U> &m){os << '{';for (auto itr=m.begin();itr!=m.end();){os << '(' << itr->first << ',' << itr->second << ')';if (++itr!=m.end()) os << ',';}os << '}';return os;}template<typename T,typename U>ostream &operator<<(ostream &os,const unordered_map<T,U> &m){os << '{';for (auto itr=m.begin();itr!=m.end();){os << '(' << itr->first << ',' << itr->second << ')';if (++itr!=m.end()) os << ',';}os << '}';return os;}template<typename T>ostream &operator<<(ostream &os,const set<T> &s){os << '{';for (auto itr=s.begin();itr!=s.end();){os << *itr;if (++itr!=s.end()) os << ',';}os << '}';return os;}template<typename T>ostream &operator<<(ostream &os,const multiset<T> &s){os << '{';for (auto itr=s.begin();itr!=s.end();){os << *itr;if (++itr!=s.end()) os << ',';}os << '}';return os;}template<typename T>ostream &operator<<(ostream &os,const unordered_set<T> &s){os << '{';for (auto itr=s.begin();itr!=s.end();){os << *itr;if (++itr!=s.end()) os << ',';}os << '}';return os;}template<typename T>ostream &operator<<(ostream &os,const deque<T> &v){for (int i=0;i<v.size();++i){os << v[i] << (i+1==v.size()?"": " ");}return os;}void debug_out(){cerr << '\n';}template<class Head,class... Tail>void debug_out(Head&& head,Tail&&... tail){cerr << head;if (sizeof...(Tail)>0) cerr << ", ";debug_out(move(tail)...);}#ifdef LOCAL#define debug(...) cerr << " ";\cerr << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << '\n';\cerr << " ";\debug_out(__VA_ARGS__)#else#define debug(...) 42#endiftemplate<typename T> T gcd(T x,T y){return y!=0?gcd(y,x%y):x;}template<typename T> T lcm(T x,T y){return x/gcd(x,y)*y;}template<class T1,class T2> inline bool chmin(T1 &a,T2 b){if (a>b){a=b; return true;} return false;}template<class T1,class T2> inline bool chmax(T1 &a,T2 b){if (a<b){a=b; return true;} return false;}#pragma endregion#ifndef ATCODER_INTERNAL_CSR_HPP#define ATCODER_INTERNAL_CSR_HPP 1#include <algorithm>#include <utility>#include <vector>namespace atcoder {namespace internal {template <class E> struct csr {std::vector<int> start;std::vector<E> elist;csr(int n, const std::vector<std::pair<int, E>>& edges): start(n + 1), elist(edges.size()) {for (auto e : edges) {start[e.first + 1]++;}for (int i = 1; i <= n; i++) {start[i] += start[i - 1];}auto counter = start;for (auto e : edges) {elist[counter[e.first]++] = e.second;}}};} // namespace internal} // namespace atcoder#endif // ATCODER_INTERNAL_CSR_HPP#ifndef ATCODER_INTERNAL_QUEUE_HPP#define ATCODER_INTERNAL_QUEUE_HPP 1#include <vector>namespace atcoder {namespace internal {template <class T> struct simple_queue {std::vector<T> payload;int pos = 0;void reserve(int n) { payload.reserve(n); }int size() const { return int(payload.size()) - pos; }bool empty() const { return pos == int(payload.size()); }void push(const T& t) { payload.push_back(t); }T& front() { return payload[pos]; }void clear() {payload.clear();pos = 0;}void pop() { pos++; }};} // namespace internal} // namespace atcoder#endif // ATCODER_INTERNAL_QUEUE_HPP#ifndef ATCODER_MINCOSTFLOW_HPP#define ATCODER_MINCOSTFLOW_HPP 1#include <algorithm>#include <cassert>#include <limits>#include <queue>#include <vector>namespace atcoder {template <class Cap, class Cost> struct mcf_graph {public:mcf_graph() {}mcf_graph(int n) : _n(n) {}int add_edge(int from, int to, Cap cap, Cost cost) {assert(0 <= from && from < _n);assert(0 <= to && to < _n);assert(0 <= cap);assert(0 <= cost);int m = int(_edges.size());_edges.push_back({from, to, cap, 0, cost});return m;}struct edge {int from, to;Cap cap, flow;Cost cost;};edge get_edge(int i) {int m = int(_edges.size());assert(0 <= i && i < m);return _edges[i];}std::vector<edge> edges() { return _edges; }std::pair<Cap, Cost> flow(int s, int t) {return flow(s, t, std::numeric_limits<Cap>::max());}std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {return slope(s, t, flow_limit).back();}std::vector<std::pair<Cap, Cost>> slope(int s, int t) {return slope(s, t, std::numeric_limits<Cap>::max());}std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {assert(0 <= s && s < _n);assert(0 <= t && t < _n);assert(s != t);int m = int(_edges.size());std::vector<int> edge_idx(m);auto g = [&]() {std::vector<int> degree(_n), redge_idx(m);std::vector<std::pair<int, _edge>> elist;elist.reserve(2 * m);for (int i = 0; i < m; i++) {auto e = _edges[i];edge_idx[i] = degree[e.from]++;redge_idx[i] = degree[e.to]++;elist.push_back({e.from, {e.to, -1, e.cap - e.flow, e.cost}});elist.push_back({e.to, {e.from, -1, e.flow, -e.cost}});}auto _g = internal::csr<_edge>(_n, elist);for (int i = 0; i < m; i++) {auto e = _edges[i];edge_idx[i] += _g.start[e.from];redge_idx[i] += _g.start[e.to];_g.elist[edge_idx[i]].rev = redge_idx[i];_g.elist[redge_idx[i]].rev = edge_idx[i];}return _g;}();auto result = slope(g, s, t, flow_limit);for (int i = 0; i < m; i++) {auto e = g.elist[edge_idx[i]];_edges[i].flow = _edges[i].cap - e.cap;}return result;}private:int _n;std::vector<edge> _edges;// inside edgestruct _edge {int to, rev;Cap cap;Cost cost;};std::vector<std::pair<Cap, Cost>> slope(internal::csr<_edge>& g,int s,int t,Cap flow_limit) {// variants (C = maxcost):// -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0// reduced cost (= e.cost + dual[e.from] - dual[e.to]) >= 0 for all edge// dual_dist[i] = (dual[i], dist[i])std::vector<std::pair<Cost, Cost>> dual_dist(_n);std::vector<int> prev_e(_n);std::vector<bool> vis(_n);struct Q {Cost key;int to;bool operator<(Q r) const { return key > r.key; }};std::vector<int> que_min;std::vector<Q> que;auto dual_ref = [&]() {for (int i = 0; i < _n; i++) {dual_dist[i].second = std::numeric_limits<Cost>::max();}std::fill(vis.begin(), vis.end(), false);que_min.clear();que.clear();// que[0..heap_r) was heapifiedsize_t heap_r = 0;dual_dist[s].second = 0;que_min.push_back(s);while (!que_min.empty() || !que.empty()) {int v;if (!que_min.empty()) {v = que_min.back();que_min.pop_back();} else {while (heap_r < que.size()) {heap_r++;std::push_heap(que.begin(), que.begin() + heap_r);}v = que.front().to;std::pop_heap(que.begin(), que.end());que.pop_back();heap_r--;}if (vis[v]) continue;vis[v] = true;if (v == t) break;// dist[v] = shortest(s, v) + dual[s] - dual[v]// dist[v] >= 0 (all reduced cost are positive)// dist[v] <= (n-1)CCost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second;for (int i = g.start[v]; i < g.start[v + 1]; i++) {auto e = g.elist[i];if (!e.cap) continue;// |-dual[e.to] + dual[v]| <= (n-1)C// cost <= C - -(n-1)C + 0 = nCCost cost = e.cost - dual_dist[e.to].first + dual_v;if (dual_dist[e.to].second - dist_v > cost) {Cost dist_to = dist_v + cost;dual_dist[e.to].second = dist_to;prev_e[e.to] = e.rev;if (dist_to == dist_v) {que_min.push_back(e.to);} else {que.push_back(Q{dist_to, e.to});}}}}if (!vis[t]) {return false;}for (int v = 0; v < _n; v++) {if (!vis[v]) continue;// dual[v] = dual[v] - dist[t] + dist[v]// = dual[v] - (shortest(s, t) + dual[s] - dual[t]) +// (shortest(s, v) + dual[s] - dual[v]) = - shortest(s,// t) + dual[t] + shortest(s, v) = shortest(s, v) -// shortest(s, t) >= 0 - (n-1)Cdual_dist[v].first -= dual_dist[t].second - dual_dist[v].second;}return true;};Cap flow = 0;Cost cost = 0, prev_cost_per_flow = -1;std::vector<std::pair<Cap, Cost>> result = {{Cap(0), Cost(0)}};while (flow < flow_limit) {if (!dual_ref()) break;Cap c = flow_limit - flow;for (int v = t; v != s; v = g.elist[prev_e[v]].to) {c = std::min(c, g.elist[g.elist[prev_e[v]].rev].cap);}for (int v = t; v != s; v = g.elist[prev_e[v]].to) {auto& e = g.elist[prev_e[v]];e.cap += c;g.elist[e.rev].cap -= c;}Cost d = -dual_dist[s].first;flow += c;cost += c * d;if (prev_cost_per_flow == d) {result.pop_back();}result.push_back({flow, cost});prev_cost_per_flow = d;}return result;}};} // namespace atcoder#endif // ATCODER_MINCOSTFLOW_HPPint main(){cin.tie(0);ios::sync_with_stdio(false);int N; ll M; cin >> N >> M;vector<int> A(N),B(N),C(N);vector<pair<int,int>> Max,Min;for (int i=0;i<N;++i){cin >> A[i] >> B[i] >> C[i];if (A[i]<C[i]) swap(A[i],C[i]);Max.emplace_back(A[i],i);Min.emplace_back(C[i],i);}sort(ALL(Max)); sort(ALL(Min));atcoder::mcf_graph<int,ll> PD(3*N+2);int s=3*N,t=s+1,lb,ub,mid;for (int i=0;i<N;++i){PD.add_edge(s,i,1,0);PD.add_edge(N+i,t,1,0);PD.add_edge(2*N+i,t,1,INF-A[Min[i].second]);lb=-1,ub=N;while (ub-lb>1){mid=(ub+lb)>>1;(Max[mid].first<B[i]?lb:ub)=mid;}if (lb>=0) PD.add_edge(i,N+lb,1,INF-B[i]);lb=-1,ub=N;while (ub-lb>1){mid=(ub+lb)>>1;(Min[mid].first>B[i]?ub:lb)=mid;}if (ub<N) PD.add_edge(i,2*N+ub,1,0);}for (int i=0;i<N-1;++i){PD.add_edge(N+i+1,N+i,N,0);PD.add_edge(2*N+i,2*N+i+1,N,0);}auto res=PD.flow(s,t,N);if (res.first<N){cout << "NO" << '\n';return 0;}cout << "YES" << '\n';ll ans=ll(INF)*N-res.second;cout << (ans>=M?"KADOMATSU!":"NO") << '\n';}