# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
118436 | str0ct | 화살표 그리기 (KOI18_arrowH) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
long long color[101010],opt[101010],sum;
typedef struct{
long long ipt,w;
}nd;
bool operator<(nd a,nd b){
return a.w<b.w;
}
nd arr[101010];
int main(){
int N;
scanf("%d",&N);
for(int i=0;i<N;i++)
scanf("%lld%lld",&arr[i].w,&arr[i].ipt);
sort(arr,arr+n);
memset(color,-1,sizeof(color));
for(int i=0;i<N;i++){
if(color[arr[i].ipt]!=-1)
opt[i]=arr[i].w-color[arr[i].ipt];
color[arr[i].ipt]=arr[i].w;
}
memset(color,-1,sizeof(color));
for(int i=N-1;i>=0;i--){
if(color[arr[i].ipt]!=-1&&(opt[i]==0||opt[i]>color[arr[i].ipt]-arr[i].w))
opt[i]=color[arr[i].ipt]-arr[i].w;
color[arr[i].ipt]=arr[i].w;
}
for(int i=0;i<N;i++)
sum+=opt[i];
printf("%lld",sum);
}