結果
問題 | No.771 しおり |
ユーザー |
|
提出日時 | 2021-02-04 06:15:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 230 ms / 2,000 ms |
コード長 | 1,246 bytes |
コンパイル時間 | 1,054 ms |
コンパイル使用メモリ | 93,804 KB |
実行使用メモリ | 24,064 KB |
最終ジャッジ日時 | 2024-07-22 07:25:10 |
合計ジャッジ時間 | 4,928 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <iostream>#include <string>#include <algorithm>#include <iostream>#include <string>#include <algorithm>#include <vector>#include <iomanip>#include <cmath>#include <stdio.h>#include <queue>#include <deque>#include <cstdio>#include <set>#include <map>#include <bitset>#include <stack>#include <cctype>using namespace std;int dp[300030][20];int d[20][20];int a[20], b[20];int main() {int n;cin >> n;for (int i = 0; i < (1 << n); i++) {for (int j = 0; j < n; j++) {dp[i][j] = 1000000007;}}for (int i = 0; i < n; i++) {cin >> a[i] >> b[i];b[i] -= a[i];}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) {d[i][j] = 0;}else {d[i][j] = b[i] + a[j];}}}for (int i = 0; i < n; i++) {dp[(1 << i)][i] = 0;}for (int i = 0; i < (1 << n); i++) {for (int v = 0; v < n; v++) {if (!(i & (1 << v))) {continue;}for (int u = 0; u < n; u++) {if (i & (1 << u)) {continue;}dp[i | (1 << u)][u] = min(dp[i | (1 << u)][u], max(dp[i][v], d[v][u]));}}}int ans = 1000000007;for (int i = 0; i < n; i++) {if (ans > dp[(1 << n) - 1][i]) {ans = dp[(1 << n) - 1][i];}}cout << ans << endl;}