結果

問題 No.1341 真ん中を入れ替えて門松列
ユーザー ei1333333
提出日時 2021-01-15 23:07:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 6,649 bytes
コンパイル時間 2,313 ms
コンパイル使用メモリ 211,960 KB
最終ジャッジ日時 2025-01-17 20:25:51
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 10 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
using int64 = long long;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
os << p.first << " " << p.second;
return os;
}
template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
is >> p.first >> p.second;
return is;
}
template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
for(int i = 0; i < (int) v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
for(T &in : v) is >> in;
return is;
}
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template< typename T = int64 >
vector< T > make_v(size_t a) {
return vector< T >(a);
}
template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}
template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
t = v;
}
template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
for(auto &e : t) fill_v(e, v);
}
template< typename F >
struct FixPoint : F {
FixPoint(F &&f) : F(forward< F >(f)) {}
template< typename... Args >
decltype(auto) operator()(Args &&... args) const {
return F::operator()(*this, forward< Args >(args)...);
}
};
template< typename F >
inline decltype(auto) MFP(F &&f) {
return FixPoint< F >{forward< F >(f)};
}
template< typename key_t, typename val_t >
struct RadixHeap {
static constexpr int bit = sizeof(key_t) * 8;
array< vector< pair< key_t, val_t > >, bit > vs;
size_t sz;
key_t last;
RadixHeap() : sz(0), last(0) {}
bool empty() const { return sz == 0; }
size_t size() const { return sz; }
inline int getbit(int a) const {
return a ? bit - __builtin_clz(a) : 0;
}
inline int getbit(int64_t a) const {
return a ? bit - __builtin_clzll(a) : 0;
}
void push(const key_t &key, const val_t &val) {
sz++;
vs[getbit(key ^ last)].emplace_back(key, val);
}
pair< key_t, val_t > pop() {
if(vs[0].empty()) {
int idx = 1;
while(vs[idx].empty()) idx++;
last = min_element(vs[idx].begin(), vs[idx].end())->first;
for(auto &p:vs[idx]) vs[getbit(p.first ^ last)].emplace_back(p);
vs[idx].clear();
}
--sz;
auto res = vs[0].back();
vs[0].pop_back();
return res;
}
};
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;
RadixHeap< int64_t, int > que;
potential.assign(V, 0);
preve.assign(V, -1);
prevv.assign(V, -1);
while(f > 0) {
min_cost.assign(V, INF);
que.push(0, s);
min_cost[s] = 0;
while(!que.empty()) {
auto p = 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.push(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;
}
}
}
};
int main() {
int N;
int64 M;
cin >> N >> M;
vector< int > X(N), Y(N), Z(N);
for(int i = 0; i < N; i++) {
int A, B, C;
cin >> A >> B >> C;
if(A > C) swap(A, C);
X[i] = A;
Y[i] = B;
Z[i] = C;
}
sort(begin(Y), end(Y));
PrimalDual< int64, int64 > flow(N + N + N + N + 2);
int S = N + N + N + N;
int T = S + 1;
// <-----
for(int i = N - 2; i >= 0; i--) {
flow.add_edge(i + N + 1, i + N, flow.INF, 0);
}
// ---->
for(int i = 1; i < N; i++) {
flow.add_edge(i + N + N - 1, i + N + N, flow.INF, 0);
}
for(int i = 0; i < N; i++) {
flow.add_edge(i + N, i + N + N + N, 1, 0);
flow.add_edge(i + N + N, i + N + N + N, 1, inf - Y[i]);
flow.add_edge(i + N + N + N, T, 1, 0);
}
for(int i = 0; i < N; i++) {
vector< int > ok(N);
for(int j = 0; j < N; j++) {
if(Y[j] < X[i]) ok[j] = 1;
else if(Z[i] < Y[j]) ok[j] = 2;
}
flow.add_edge(S, i, 1, 0);
for(int j = 0; j < N; j++) {
if(ok[j] == 2) {
flow.add_edge(i, j + N + N, 1, 0);
break;
}
}
for(int j = N - 1; j >= 0; j--) {
if(ok[j] == 1) {
flow.add_edge(i, j + N, 1, inf - Z[i]);
break;
}
}
}
auto ret = flow.min_cost_flow(S, T, N);
if(ret == -1) {
cout << "NO\n";
} else {
cout << "YES\n";
ret -= 1LL * inf * N;
ret *= -1;
if(ret >= M) cout << "KADOMATSU!\n";
else cout << "NO\n";
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0