結果
問題 | No.771 しおり |
ユーザー |
|
提出日時 | 2024-09-17 08:08:42 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 189 ms / 2,000 ms |
コード長 | 1,684 bytes |
コンパイル時間 | 2,090 ms |
コンパイル使用メモリ | 207,748 KB |
実行使用メモリ | 34,004 KB |
最終ジャッジ日時 | 2024-09-17 08:08:48 |
合計ジャッジ時間 | 5,717 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h>using namespace std;#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 R(a) rep(i,0,a)#define RR(a,b) rep(i,0,a)rep(j,0,b)#define RRR(a,b,c) RR(a,b)rep(k,0,c)#define el '\n'#define YN(p) cout << (p?"Yes":"No") << el;#define SU(p) cout << p << el;#define PU(p) cout << p.first << ' ' << p.second << el;#define VU(p) R(p.size())cout << p[i] << (i!=p.size()-1?' ':el);#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()#define Toup(s) transform(all(s),s.begin(),[](char c){return toupper(c);})#define Tolow(s) transform(all(s),s.begin(),[](char c){return tolower(c);})#define fix() cout << fixed << setprecision(12);using ll = long long;const int inf = 1073741823;const ll INFL=1LL<<60;const ll mod= 998244353;const ll MOD=1000000007;bool ok=false;const int fj[4]={0,1,0,-1};//上右下左const int fi[4]={-1,0,1,0};int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n;cin >> n;vector<pair<int,int>>book(n);R(n)cin >> book[i].first >> book[i].second;vector<vector<int>>dp((1<<n),vector<int>(n+1,inf));dp[0][0]=0;auto dis=[=](int j,int k){return book[j].second-book[j].first+book[k].first;};R(1<<n){if(i==0){rep(j,0,n)dp[1<<j][j+1]=0;continue;}rep(j,1,n+1){if(!(i&(1<<(j-1))))continue;rep(k,1,n+1){if(i&(1<<(k-1)))continue;dp[i|(1<<(k-1))][k]=min(dp[i|(1<<(k-1))][k],max(dp[i][j],dis(j-1,k-1)));}}}int ans=inf;R(n)ans=min(ans,dp[(1<<n)-1][i+1]);SU(ans)}