제출 #14529

#제출 시각아이디문제언어결과실행 시간메모리
14529dohyun0324Palembang Bridges (APIO15_bridge)C++98
22 / 100
83 ms5084 KiB
#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],dap2,dap3; 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.empty(); q2.empty(); 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; 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;} } dap2=dap; sort(a+1,a+w+1); sort(arr+1,arr+w2+1); if(k==1 || k==2){ for(i=1;i<=w2;i++) dap+=abs(arr[i]-arr[w]); dap3=dap; } if(k==2){ 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]); } if(k==2) printf("%lld",min(dap3+w,dap+w+dap2)); else printf("%lld",dap3+w); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'void pro(int)':
bridge.cpp:18:11: warning: unused variable 'c' [-Wunused-variable]
     int i,c=0;
           ^
bridge.cpp: In function 'int main()':
bridge.cpp:44:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&k,&n);
                         ^
bridge.cpp:46:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %c %d",&c1,&x1,&c2,&x2);
                                              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...