結果
問題 | No.2354 Poor Sight in Winter |
ユーザー |
![]() |
提出日時 | 2023-06-16 22:33:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 1,707 bytes |
コンパイル時間 | 8,412 ms |
コンパイル使用メモリ | 312,572 KB |
最終ジャッジ日時 | 2025-02-14 06:32:49 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/extc++.h> #include <atcoder/all> using namespace std; using ll = long long; #define REP(i,n) for(int i=0;i<int(n);i++) #define FOR(i,a,b) for(int i=a;i<=int(b);i++) #define ALL(x) x.begin(),x.end() #define INF INT_MAX #define INFL LLONG_MAX / 4 using namespace atcoder; using mint = modint998244353; template<typename T> void chmin(T& a, T b) { a = min(a, b); } template<typename T> void chmax(T& a, T b) { a = max(a, b); } #define PR(x) cerr << #x << "=" << x << endl using i128 = __int128_t; struct Edge { int to; long long cost; int i = 0; }; int main() { int n, k; cin >> n >> k; vector<vector<Edge>> G(n+2); ll sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy; G[n].push_back({n+1,abs(gx - sx) + abs(gy - sy)}); vector<ll> x(n), y(n); REP(i, n) { cin >> x[i] >> y[i]; ll ds = abs(x[i] - sx) + abs(y[i] - sy); ll dg = abs(x[i] - gx) + abs(y[i] - gy); G[n].push_back({i,ds}); G[i].push_back({n+1,dg}); } REP(i, n) { REP(j, n) { if(i == j) continue; ll d = abs(x[i] - x[j]) + abs(y[i] - y[j]); G[i].push_back({j,d}); } } ll ok = 1e6; ll ng = 0; while(ok - ng > 1) { ll ch = (ok + ng) / 2; priority_queue<pair<int, int>> pq; pq.push({k, n}); vector<int> max_k(n+2, -INF); max_k[n] = k; while(pq.size()) { auto [nk, now] = pq.top(); pq.pop(); if(max_k[now] != nk) continue; for(auto e: G[now]) { ll newc = nk - (e.cost-1) / ch; if(max_k[e.to] < newc) { max_k[e.to] = newc; pq.push({newc, e.to}); } } } if(max_k[n+1] < 0) { ng = ch; } else { ok = ch; } } cout << ok; return 0; }