結果
問題 | No.1341 真ん中を入れ替えて門松列 |
ユーザー |
![]() |
提出日時 | 2021-01-16 00:27:04 |
言語 | C++11 (gcc 13.3.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,894 bytes |
コンパイル時間 | 1,360 ms |
コンパイル使用メモリ | 102,880 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-26 19:00:17 |
合計ジャッジ時間 | 18,549 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 13 TLE * 1 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <iostream>#include <cstdio>#include <cmath>#include <ctime>#include <cstdlib>#include <cassert>#include <vector>#include <list>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <string>#include <algorithm>#include <utility>#include <complex>#define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define all(x) (x).begin(),(x).end()#define inf 1e18using namespace std;typedef long long llint;typedef long long ll;typedef pair<int, int> P;ll n, m;int l[3005], r[3005], a[3005];priority_queue<P> Q, Q2;priority_queue<P, vector<P>, greater<P> > Q3;int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;rep(i, 1, n){cin >> l[i] >> a[i] >> r[i];if(l[i] > r[i]) swap(l[i], r[i]);}sort(a+1, a+n+1);ll ans = -inf;rep(i, 0, n){int cnt = 0;while(Q.size()) Q.pop();while(Q2.size()) Q2.pop();while(Q3.size()) Q3.pop();rep(j, 1, n) Q.push(P(l[j], r[j]));ll sum = 0;for(int j = i; j >= 1; j--){while(Q.size() && Q.top().first > a[j]){Q2.push(P(Q.top().second, Q.top().first));Q.pop();}if(Q2.size() == 0) goto end;sum += Q2.top().first;Q2.pop();}while(Q.size()) Q3.push(P(Q.top().second, Q.top().first)), Q.pop();while(Q2.size()) Q3.push(Q2.top()), Q2.pop();for(int j = i+1; j <= n; j++){while(Q3.size() && Q3.top().first < a[j]) cnt++, Q3.pop();if(cnt == 0) goto end;sum += a[j];cnt--;}chmax(ans, sum);if(ans >= m) break;end:;}if(ans < 0) cout << "NO" << endl;else{cout << "YES" << endl;if(ans >= m) cout << "KADOMATSU!" << endl;else cout << "NO" << endl;}return 0;}