# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
14503 | dohyun0324 | Palembang Bridges (APIO15_bridge) | C++98 | 86 ms | 5084 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int>q;
priority_queue<int,vector<int>,greater<int> >q2;
char c1,c2;
long long dap,d[3][100010];
int t,w2,k,n,x1,x2,w,arr[200010];
struct data{
int x,y;
bool operator<(const data&r)const{
return (x+y)<r.x+r.y;
}
}a[100010];
void pro(int p)
{
int i,c=0;
long long sum=0,sum2=0,mid=0;
q.push(min(a[1].x,a[1].y)); q2.push(max(a[1].x,a[1].y));
d[p][1]=abs(a[1].x-a[1].y);
sum=min(a[1].x,a[1].y); sum2=a[1].x+a[1].y;
for(i=2;i<=w;i++){
sum2+=a[i].x+a[i].y;
if(q.top()>a[i].x){
sum+=a[i].x-q.top();
q2.push(q.top()); q.pop(); q.push(a[i].x);
}
else q2.push(a[i].x);
sum+=q2.top(); q.push(q2.top()); q2.pop();
if(q.top()>a[i].y){
sum+=a[i].y-q.top();
q2.push(q.top()); q.pop(); q.push(a[i].y);
}
else q2.push(a[i].y);
mid=q.top();
d[p][i]=mid*i-sum+(sum2-sum)-mid*i;
}
}
int main()
{
int i,dap2=0;
scanf("%d %d",&k,&n);
for(i=1;i<=n;i++){
scanf(" %c %d %c %d",&c1,&x1,&c2,&x2);
if(c1==c2) dap+=abs(x2-x1);
else{w++; a[w].x=x1; a[w].y=x2; arr[++w2]=x1; arr[++w2]=x2;}
}
sort(a+1,a+w+1); sort(arr+1,arr+w2+1);
if(k==1){
for(i=1;i<=w2;i++) dap+=abs(arr[i]-arr[w]);
}
else{
dap2=dap; dap=2147483647;
pro(1); reverse(a+1,a+w+1); pro(2);
for(i=1;i<=w;i++) dap=min(dap,d[1][i]+d[2][w-i]);
}
printf("%lld",dap+w+dap2);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |