結果
問題 |
No.3292 World Map Distance
|
ユーザー |
|
提出日時 | 2025-10-03 22:41:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 483 ms / 3,000 ms |
コード長 | 1,469 bytes |
コンパイル時間 | 2,108 ms |
コンパイル使用メモリ | 211,512 KB |
実行使用メモリ | 43,844 KB |
最終ジャッジ日時 | 2025-10-03 22:41:30 |
合計ジャッジ時間 | 9,691 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); long long H,W,N; cin >> N >> H >> W; vector<long long> X,Y; while(N--){ long long x,y; cin >> x >> y,x--,y--; X.push_back(x),Y.push_back(y); } N = X.size(); sort(X.begin(),X.end()),sort(Y.begin(),Y.end()); auto f = [&](long long n,vector<long long> &A) -> long long { map<long long,pair<long long,long long>> M; int half = n/2; for(auto a : A){ if(a <= half){ M[0].first--; M[0].second += a+1; M[a+1].first += 2; M[a+n/2+1].first--; M[a+(n+1)/2+1].first--; } else{ if(a < n-1) M[a+1].first += 2; long long a0 = n-1-a; M[0].second += a0; M[0].first++; M[(a+n/2+1)%n].first--; M[(a+(n+1)/2+1)%n].first--; } } long long ret = 0,now = 0,add = 0,back = -1; M[n] = {0,0}; for(auto [k,v] : M){ long long move = k-1-back; now += add*move; ret = max(ret,now); if(k == n) break; auto [v1,v2] = v; now += v2,add += v1,back = k; now += add,ret = max(ret,now); } return ret; }; cout << f(H,X)+f(W,Y) << endl; }