結果
問題 |
No.1715 Dinner 2
|
ユーザー |
![]() |
提出日時 | 2021-10-22 22:25:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,255 bytes |
コンパイル時間 | 5,249 ms |
コンパイル使用メモリ | 254,600 KB |
最終ジャッジ日時 | 2025-01-25 03:55:14 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 2 WA * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; using mint = modint998244353; #endif using ll = long long; using ld = long double; const ll INF = 1ll<<60; const ld EPS = 1.0/1e9; #define endl "\n" #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() #define del(x) sort(all(x)); x.erase(unique(all(x)),x.end()); int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll n,d; cin >> n >> d; vector<ll>p(n); vector<ll>q(n); rep(i,0,n) cin >> p[i] >> q[i]; vector<pair<ll,ll>>pq; rep(i,0,n){ pq.emplace_back(p[i]-q[i],p[i]); } vector<vector<pair<ll,ll>>>dp(2,vector<pair<ll,ll>>(n,{-INF,-INF})); rep(i,0,n){ dp[0][i].first=-pq[i].second; dp[0][i].second=-pq[i].first; } rep(i,0,n){ ll x=-INF; ll ind=-1; rep(j,0,n){ if(x<dp[0][i].first-pq[j].second){ x=max(x,dp[0][i].first-pq[j].second); ind=j; } } dp[1][i].first=x; dp[1][i].second=dp[0][i].second-pq[ind].first; } ll tmp=-INF; ll tmp2=-INF; rep(i,0,n){ tmp=max(tmp,min(dp[1][i].first,dp[1][i].second)); } cout << tmp << endl; }