結果
問題 |
No.3292 World Map Distance
|
ユーザー |
|
提出日時 | 2025-10-03 23:16:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,579 bytes |
コンパイル時間 | 1,088 ms |
コンパイル使用メモリ | 80,008 KB |
実行使用メモリ | 45,460 KB |
最終ジャッジ日時 | 2025-10-03 23:16:31 |
合計ジャッジ時間 | 7,821 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 WA * 7 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cassert> using namespace std; long solve(int X,vector<int>x) { vector<int>pos=x; for(int p:x) { pos.push_back((p+X/2)%X); pos.push_back((p+(X+1)/2)%X); } sort(pos.begin(),pos.end()); pos.erase(unique(pos.begin(),pos.end()),pos.end()); const int sz=pos.size(); { pos.reserve(sz+sz+sz); for(int i=0;i<sz;i++) { int t=pos[i]; pos.push_back(t+X); } for(int i=0;i<sz;i++) { int t=pos[i]; pos.push_back(t+X+X); } } vector<long>im0(pos.size()+1),im1(pos.size()+1); for(int p:x) { int l,m,r; if(X%2==0) { l=lower_bound(pos.begin(),pos.end(),p+X-X/2)-pos.begin(); m=lower_bound(pos.begin(),pos.end(),p+X)-pos.begin(); r=lower_bound(pos.begin(),pos.end(),p+X+X/2)-pos.begin(); } else { l=lower_bound(pos.begin(),pos.end(),p+X-X/2)-pos.begin(); m=lower_bound(pos.begin(),pos.end(),p+X)-pos.begin(); r=lower_bound(pos.begin(),pos.end(),p+X+X/2+1)-pos.begin(); } im0[l]+=p+X; im0[m]-=p+X; im1[l]-=1; im1[m]+=1; im0[m]-=p+X; im0[r]+=p+X; im1[m]+=1; im1[r]-=1; } vector<long>ret(sz); for(int i=0;i<pos.size();i++) { im0[i+1]+=im0[i]; im1[i+1]+=im1[i]; ret[i%sz]+=im0[i]+im1[i]*pos[i]; } long ans=0; for(int i=0;i<sz;i++) { ans=max(ans,ret[i]); //cout<<pos[i]<<" "<<ret[i]<<"\n"; } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N,X,Y; cin>>N>>X>>Y; vector<int>x(N),y(N); for(int i=0;i<N;i++)cin>>x[i]>>y[i],x[i]--,y[i]--; long t=solve(X,x); long u=solve(Y,y); cout<<t+u<<endl; }