結果
問題 | No.1715 Dinner 2 |
ユーザー |
![]() |
提出日時 | 2021-10-22 22:04:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 1,960 bytes |
コンパイル時間 | 2,135 ms |
コンパイル使用メモリ | 199,292 KB |
最終ジャッジ日時 | 2025-01-25 03:41:08 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>using namespace atcoder;//#pragma GCC optimize ("O3")using namespace std;#define reps(i,s,n) for(int i = s; i < n; i++)#define rep(i,n) reps(i,0,n)#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)#define Rrep(i,n) Rreps(i,n,0)#define ALL(a) a.begin(), a.end()using ll = long long;using vec = vector<ll>;using mat = vector<vec>;ll N,M,H,W,Q,K,A,B;string S;using P = pair<ll, ll>;using tp = tuple<ll, ll, ll>;const ll INF = (1LL<<60);template<class T> bool chmin(T &a, const T b){if(a > b) {a = b; return true;}else return false;}template<class T> bool chmax(T &a, const T b){if(a < b) {a = b; return true;}else return false;}template<class T> void my_printv(std::vector<T> v,bool endline = true){if(!v.empty()){for(std::size_t i{}; i<v.size()-1; ++i) std::cout<<v[i]<<" ";std::cout<<v.back();}if(endline) std::cout<<std::endl;}using mint = modint998244353;using vm = vector<mint>;int main() {cin.tie(nullptr);ios::sync_with_stdio(false);cin>>N>>K;vec p(N), q(N);rep(i, N) cin>>p[i]>>q[i];const int st = (int)1e+8;auto ok = [&](int bd){vec dp(N);rep(i, N){if(st - p[i] < bd){dp[i] = - INF;}else{dp[i] = st - p[i] + q[i];}}rep(lp, K - 1){vec ndp(N, -INF);rep(lp2, 2) {M = -INF;rep(tmp, N) {int i = (lp2 ? N - 1 - tmp : tmp);if(M - p[i] >= bd) chmax(ndp[i], M - p[i] + q[i]);chmax(M, dp[i]);}}dp = ndp;}return *max_element(ALL(dp)) != -INF;};ll lb = 0, ub = st;while(ub - lb > 1){ll cen = lb + (ub - lb) / 2;(ok(cen) ? lb : ub) = cen;}cout<<lb - st<<endl;}