제출 #487865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
487865		MilosMilutinovic	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	2 ms	460 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=101000;
int k,n,m,s[N],t[N],a[N],b[N],p[N];
char ss[N],tt[N];
ll pf[N],sf[N];

struct ds{
	int n,m;
	ll s;
	ds() { n=s=0; }
	multiset<int> L,R;
	void add(int x,int y) {
		if (x>y) swap(x,y);
		if (n==0) {
			s=y-x;
			L.insert(x);
			R.insert(y);
			n+=2;
			m=x;
			return;
		}
		if (x<=m&&y<=m) {
			L.insert(x);
			L.insert(y);
			R.insert(*prev(L.end()));
			L.erase(prev(L.end()));
			ll diff=m-*L.rbegin();
			m=*L.rbegin();
			s+=abs(x-m)+abs(y-m);
			s+=diff;
		} else if (x<=m&&y>m) {
			L.insert(x);
			R.insert(y);
			s+=abs(x-m)+abs(y-m);
		} else {
			assert(x>m&&y>m);
			R.insert(x);
			R.insert(y);
			L.insert(*R.begin());
			R.erase(R.begin());
			ll diff=*L.rbegin()-m;
			m=*L.rbegin();
			s+=abs(x-m)+abs(y-m);
			s+=diff;
		}
		n+=2;
	}
};

int main() {
	scanf("%d%d",&k,&n);
	rep(i,1,n+1) scanf("\n%c %d %c %d",ss+i,s+i,tt+i,t+i);
	ll ans=1e18,same=0;
	rep(i,1,n+1) {
		if (ss[i]==tt[i]) {
			same+=abs(s[i]-t[i]);
		}
		else a[++m]=s[i],b[m]=t[i];
	}
	rep(i,1,m+1) p[i]=i;
	sort(p+1,p+1+m,[&](int i,int j) {
		return a[i]+b[i]<a[j]+b[j];
	});
	ds pref;
	rep(i,1,m+1) {
		pref.add(a[p[i]],b[p[i]]);
		pf[i]=pref.s;
	}
	ds suff;
	per(i,1,m+1) {
		suff.add(a[p[i]],b[p[i]]);
		sf[i]=suff.s;
	}
	rep(i,1,m+1) ans=min(ans,pf[i]+sf[i+1]);
	if (k==2) printf("%lld",ans+same+m);
	else printf("%lld\n",pf[m]+same+m);
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d%d",&k,&n);
      |  ~~~~~^~~~~~~~~~~~~~
bridge.cpp:73:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  rep(i,1,n+1) scanf("\n%c %d %c %d",ss+i,s+i,tt+i,t+i);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37