QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#546934 | #1961. Postman | ucup-team052# | WA | 1ms | 4632kb | C++23 | 2.3kb | 2024-09-04 16:02:53 | 2024-09-04 16:02:53 |
Judging History
answer
#include<bits/stdc++.h>
#define D(...) fprintf(stderr,__VA_ARGS__)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
using namespace std;
using LL=long long;
const int N=100005;
int n,w,t,id[N],_id[N];
LL x[N],ans[N];
struct DS{
priority_queue<LL>q1;
priority_queue<LL,vector<LL>,greater<LL> >q2;
LL s;
void clear(){
D("clear\n");
s=0;
while(!q1.empty())q1.pop();
while(!q2.empty())q2.pop();
}
int size()const{return SZ(q1)+SZ(q2);}
void push(int x){
D("push %d\n",x);
q2.push(x);
}
LL query(int k){
while(SZ(q1)<k){
s+=q2.top();
q1.push(q2.top());
q2.pop();
}
while(SZ(q1)>k){
s-=q1.top();
q2.push(q1.top());
q1.pop();
}
if(SZ(q1)&&SZ(q2)){
while(q1.top()>q2.top()){
LL x=q1.top();
LL y=q2.top();
s=s-x+y;
q1.pop();
q2.pop();
q1.push(y),q2.push(x);
}
}
assert(SZ(q1)==k);
D("query %d = %lld\n",k,s);
return s;
}
}ds;
void solve(int w,int e){
ds.clear();
rep(i,0,n)id[i]=i;
sort(id,id+n+1,[&](int lhs,int rhs){return x[lhs]<x[rhs];});
rep(i,0,n)_id[id[i]]=i;
int bg=_id[0];
rep(ed,0,n)if(ed!=bg){ // id[ed] at x[id[ed]]
if(ed<bg){
int least_w=(bg!=0)+(ed!=n);
int least_e=1;
if(w>=least_w&&e>=least_e){
ans[id[ed]]=min(ans[id[ed]],x[id[bg]]-x[id[0]]+x[id[n]]-x[id[0]]+x[id[n]]-x[id[ed]]);
}
}else{
int least_w=(bg!=0)+(ed!=n);
int most_w=bg+n-ed;
if(w>=least_w&&w<=most_w){
ans[id[ed]]=min(ans[id[ed]],x[id[bg]]-x[id[0]]+x[id[n]]-x[id[0]]+x[id[n]]-x[id[ed]]);
}
if(w>most_w){
if(w<=most_w+ds.size()){
ans[id[ed]]=min(ans[id[ed]],x[id[bg]]-x[id[0]]+x[id[n]]-x[id[0]]+x[id[n]]-x[id[ed]]+ds.query(w-most_w));
}
}
}
if(ed-1>bg){
ds.push(x[id[ed]]-x[id[ed-1]]);
}
}
}
int main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>w>>t;
x[0]=0;
rep(i,1,n)cin>>x[i];
memset(ans,63,sizeof(ans));
solve(w,n-w);
rep(i,0,n)x[i]*=-1;
solve(n-w,w);
LL res;
if(t==2){
res=ans[n];
}else{
res=*min_element(ans+1,ans+n+1);
}
if(res>=1e18){
puts("-1");
}else{
printf("%lld\n",res);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4632kb
input:
100 0 1 751 558 131 292 317 886 785 847 224 668 649 358 725 250 953 65 176 733 461 84 114 977 628 673 798 863 373 827 51 630 518 347 527 876 366 241 452 670 813 314 846 342 357 460 985 581 841 843 282 907 327 656 411 944 421 99 441 388 568 763 167 351 793 916 517 109 999 390 272 639 513 534 304 253 ...
output:
999
result:
ok single line: '999'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 4548kb
input:
100 50 1 654 349 533 94 619 754 498 939 469 518 3 661 431 214 195 198 989 548 561 312 262 629 807 981 624 639 178 765 706 782 888 611 553 363 336 91 176 485 735 791 596 455 390 760 995 202 417 82 798 883 209 155 725 908 789 56 49 899 231 423 815 228 314 400 748 946 736 840 385 446 938 284 10 917 593...
output:
1206
result:
wrong answer 1st lines differ - expected: '1397', found: '1206'