結果
問題 | No.2890 Chiffon |
ユーザー |
![]() |
提出日時 | 2024-09-13 23:17:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,925 bytes |
コンパイル時間 | 3,131 ms |
コンパイル使用メモリ | 260,612 KB |
実行使用メモリ | 89,536 KB |
最終ジャッジ日時 | 2024-09-13 23:17:49 |
合計ジャッジ時間 | 7,270 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 WA * 11 TLE * 1 -- * 32 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/segtree>using namespace std;using ll = long long;using ld = long double;using ull = unsigned long long;template <class T>using max_heap = priority_queue<T>;template <class T>using min_heap = priority_queue<T, vector<T>, greater<T>>;#define rep(i, l, r) for (ll i = (l); i < (r); i++)#define rrep(i, r, l) for (ll i = (r); i-- > (l);)#define all(x) begin(x), end(x)template <class T>bool chmin(T& lhs, T rhs) {return lhs > rhs ? (lhs = rhs, true) : false;}template <class T>bool chmax(T& lhs, T rhs) {return lhs < rhs ? (lhs = rhs, true) : false;}struct IOIO {IOIO() { cin.tie(0)->sync_with_stdio(0); }} ioio;template <class S, class T>ostream& operator<<(ostream& os, const pair<S, T>& p) {os << '(' << p.first << ", " << p.second << ')';return os;}template <class T>ostream& operator<<(ostream& os, const vector<T>& vs) {os << '{';rep(i, 0, (int)vs.size()) os << vs[i] << (i + 1 == (int)vs.size() ? "" : ", ");os << '}';return os;}template <class T>ostream& operator<<(ostream& os, const set<T>& vs) {os << '{';for (auto it = vs.begin(); it != vs.end(); it++) {if (it != vs.begin()) { os << ", "; }os << *it;}os << '}';return os;}template <class T, class U>ostream& operator<<(ostream& os, const map<T, U>& vs) {os << '{';for (auto it = vs.begin(); it != vs.end(); it++) {if (it != vs.begin()) { os << ", "; }os << *it;}os << '}';return os;}#ifdef DEBUGvoid dump_func() { cerr << endl; }template <class Head, class... Tail>void dump_func(Head&& head, Tail&&... tail) {cerr << head;if (sizeof...(Tail) > 0) { cerr << ", "; }dump_func(std::move(tail)...);}#define dump(...) cerr << "[" + string(#__VA_ARGS__) + "] ", dump_func(__VA_ARGS__)#else#define dump(...) static_cast<int>(0)#endifint main() {int n, k;cin >> n >> k;vector<int> a(k);rep(i, 0, k) cin >> a[i];rep(i, 0, k) a.push_back(a[i] + 2 * n);a.push_back(a[0] + 4 * n);auto sol = [&](int key) {vector<int> d(2 * k);rep(i, 0, 2 * k) d[i] = key - (a[i + 1] - a[i]);vector<int> to(2 * k, -1);map<ll, int> mn, mx;mn[0] = 2 * k;mx[0] = 2 * k;ll sum = 0;const int none = 1e9;rrep(i, 2 * k, 0) {sum += d[i];int mni = none;{auto it = mn.upper_bound(sum - key);if (it != mn.begin()) {it--;mni = it->second;}}int mxi = none;{auto it = mx.lower_bound(sum);if (it != mx.end()) { mxi = it->second; }}if (mxi < mni) { to[i] = mxi; }{auto it = mn.lower_bound(sum);while (it != mn.end()) { it = mn.erase(it); }}{auto it = mx.begin();while (it != mx.end() && it->first <= sum) it = mx.erase(it);}mn[sum] = i;mx[sum] = i;}const int ng = -2;vector<int> memo(2 * k, -1);auto find = [&](auto&& self, int i, int d) -> int {if (d <= i) { return i; }if (memo[i] == ng) return ng;if (memo[i] != -1) { return memo[i] = self(self, memo[i], d); }if (to[i] != -1) {return memo[i] = self(self, to[i], d);} else return memo[i] = ng;};rep(i, 0, k) {if (find(find, i, k + i) == k + i) { return true; }}return false;};int ok = 0;int ng = 2 * n + 1;while (ng - ok > 1) {int key = (ok + ng) / 2;if (sol(key)) ok = key;else ng = key;}cout << ok << '\n';}