結果
| 問題 |
No.3292 World Map Distance
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-10-03 23:06:30 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,089 ms / 3,000 ms |
| コード長 | 2,329 bytes |
| コンパイル時間 | 1,734 ms |
| コンパイル使用メモリ | 126,724 KB |
| 実行使用メモリ | 72,356 KB |
| 最終ジャッジ日時 | 2025-10-03 23:06:48 |
| 合計ジャッジ時間 | 16,534 ms |
|
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <numeric>
using namespace std;
using ll = long long;
ll solve(vector<ll> A, ll X) {
sort(A.begin(),A.end());
vector<ll> value = A;
value.push_back(0);
value.push_back(X-1);
sort(value.begin(),value.end());
value.erase(unique(value.begin(), value.end()), value.end());
int M = A.size();
vector<ll> T;
for (int i = 0;i < M;i++) {
T.push_back(A[i]);
T.push_back((A[i]+1)%X);
T.push_back((A[i]-1+X)%X);
if ((2*A[i]) > X) {
ll ad = ((2*A[i]) - X + 1) / 2;
ad--;
T.push_back(ad);
T.push_back((ad+1)%X);
T.push_back((ad-1+X)%X);
}
ll ad = ((2*A[i])+X) / 2;ad++;
ad = ad % X;
T.push_back(ad);
T.push_back((ad-1+X)%X);
T.push_back((ad+1)%X);
}
for (auto v : T) value.push_back(v);
sort(value.begin(),value.end());
value.erase(unique(value.begin(), value.end()), value.end());
int K = value.size();
vector<ll> S(K, 0), CNT(K, 0);
for (auto v : A) {
int id = lower_bound(value.begin(),value.end(), v) - value.begin();
CNT[id]++;
S[id] += v;
}
for (int i = 1;i < K;i++) {
CNT[i] += CNT[i-1];
S[i] += S[i-1];
}
ll res = 0;
sort(T.begin(),T.end());
T.erase(unique(T.begin(),T.end()),T.end());
for (auto x : T) {
int ix = lower_bound(value.begin(),value.end(),x) - value.begin();
ll sc = 0;
int l = -1;
if ((2*x) > X) {
ll ups = (((2*x)-X+1)) / 2;
ups--;
auto itr = upper_bound(value.begin(),value.end(), ups);
itr--;
l = itr - value.begin();
sc += ((X-x) * CNT[l]) + (S[l]);
sc += ((CNT[ix]-CNT[l])*x) - (S[ix]-S[l]);
}
if (l == -1) {
sc += (CNT[ix] * x) - S[ix];
}
ll ups = ((2*x)+X) / 2;
ups++;
auto it = lower_bound(value.begin(),value.end(), ups);
if (it != value.end()) {
int id = it - value.begin();
if (id != 0) {
sc += ((X+x) * (CNT.back() - CNT[id-1])) - (S.back() - S[id-1]);
sc += (S[id-1] - S[ix]) - (x * (CNT[id-1] - CNT[ix]));
}
} else {
sc += (S.back() - S[ix]) - (x * (CNT.back() - CNT[ix]));
}
res = max(res, sc);
}
return res;
}
int main() {
int N;ll X, Y;cin >> N >> X >> Y;
vector<ll> x, y;
for (int i = 0;i < N;i++) {
ll a ,b;cin >> a >> b;
a--;b--;
x.push_back(a);
y.push_back(b);
}
ll res = solve(x, X) + solve(y, Y);
cout << res << endl;
}