結果
問題 | No.2354 Poor Sight in Winter |
ユーザー | Heart_Blue |
提出日時 | 2023-06-16 22:38:42 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,909 ms / 2,000 ms |
コード長 | 1,805 bytes |
コンパイル時間 | 1,937 ms |
コンパイル使用メモリ | 138,696 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-24 15:22:32 |
合計ジャッジ時間 | 16,795 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 1,132 ms
6,940 KB |
testcase_12 | AC | 902 ms
6,940 KB |
testcase_13 | AC | 1,800 ms
6,944 KB |
testcase_14 | AC | 1,909 ms
6,944 KB |
testcase_15 | AC | 1,685 ms
6,940 KB |
testcase_16 | AC | 1,801 ms
6,940 KB |
testcase_17 | AC | 1,905 ms
6,940 KB |
testcase_18 | AC | 302 ms
6,940 KB |
testcase_19 | AC | 946 ms
6,944 KB |
testcase_20 | AC | 370 ms
6,944 KB |
testcase_21 | AC | 9 ms
6,940 KB |
testcase_22 | AC | 138 ms
6,944 KB |
testcase_23 | AC | 150 ms
6,940 KB |
testcase_24 | AC | 740 ms
6,940 KB |
testcase_25 | AC | 77 ms
6,940 KB |
testcase_26 | AC | 53 ms
6,944 KB |
testcase_27 | AC | 3 ms
6,940 KB |
testcase_28 | AC | 6 ms
6,940 KB |
ソースコード
#pragma GCC optimize("Ofast,no-stack-protector")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")#include <cstdlib>#include <cctype>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>#include <vector>#include <string>#include <iostream>#include <sstream>#include <map>#include <set>#include <queue>#include <stack>#include <fstream>#include <numeric>#include <iomanip>#include <bitset>#include <list>#include <stdexcept>#include <functional>#include <utility>#include <ctime>#include <cassert>using namespace std;typedef long long LL;typedef unsigned long long ULL;#define MEM(a,b) memset((a),(b),sizeof(a))const LL INF = 1e9 + 7;const int N = 5e2 + 10;int a[N][N];int d[N][N];pair<int, int> vp[N];void floyd(int n){for (int k = 0; k <= n; k++){for (int i = 0; i <= n; i++){for (int j = 0; j <= n; j++)a[i][j] = min(a[i][j], a[i][k] + a[k][j]);}}}inline int dis(int i, int j){return abs(vp[i].first - vp[j].first) + abs(vp[i].second - vp[j].second);}int main(){//freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);int n, k;scanf("%d%d", &n, &k);scanf("%d%d%d%d", &vp[0].first, &vp[0].second, &vp[n + 1].first, &vp[n + 1].second);for (int i = 1; i <= n; i++)scanf("%d%d", &vp[i].first, &vp[i].second);n++;for (int i = 0; i <= n; i++){for (int j = 0; j <= n; j++)d[i][j] = dis(i, j);}int l = 1, r = dis(0, n);int ans = r;while (l <= r){int mid = (l + r) / 2;for (int i = 0; i <= n; i++){for (int j = 0; j <= n; j++){int d = ::d[i][j] - mid;d = max(0, d);a[i][j] = (d + mid - 1) / (mid);}}floyd(n);if (a[0][n] <= k) ans = mid, r = mid - 1;else l = mid + 1;}printf("%d\n", ans);return 0;}