結果
問題 | 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 / 4using 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 << endlusing 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;}