제출 #1042418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042418		Math4Life2020	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2065 ms	10328 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

ll calc(vector<ll> v) {
	vector<ll> v2=v;
	sort(v2.begin(),v2.end());
	ll val = 0;
	for (ll x: v2) {
		val += abs(x-v2[v2.size()/2]);
	}
	return val;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll K,N; cin >> K >> N;
	vector<pii> v;
	ll ans = 0;
	for (ll i=0;i<N;i++) {
		string p,q; ll s,t;
		cin >> p >> s >> q >> t;
		if (p==q) {
			ans += abs(s-t);
		} else {
			ans++;
			v.push_back({min(s,t),max(s,t)});
		}
	}
	vector<ll> v2;
	for (pii p0: v) {
		v2.push_back(p0.first);
		v2.push_back(p0.second);
	}
	sort(v2.begin(),v2.end());
	if (K==1) {
		cout << ans+calc(v2);
	} else {
		ll ans1[v.size()+1]; ll ans2[v.size()+1];
		vector<array<ll,3>> VTOT;
		for (ll i=0;i<v.size();i++) {
			VTOT.push_back({v[i].first+v[i].second,v[i].first,v[i].second});
		}
		sort(VTOT.begin(),VTOT.end());
		ans1[0]=0; ans2[v.size()]=0;
		vector<ll> vf; vector<ll> vb;
		for (ll T=0;T<VTOT.size();T++) {
			vf.push_back(VTOT[T][1]);
			vf.push_back(VTOT[T][2]);
			ans1[T+1]=calc(vf);
			vb.push_back(VTOT[v.size()-1-T][1]);
			vb.push_back(VTOT[v.size()-1-T][2]);
			ans2[v.size()-1-T]=calc(vb);
		}
		ll atotM = 1e18;
		for (ll i=0;i<=v.size();i++) {
			atotM = min(atotM,ans1[i]+ans2[i]);
		}
		cout << ans+atotM;
	}
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:41:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (ll i=0;i<v.size();i++) {
      |               ~^~~~~~~~~
bridge.cpp:47:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (ll T=0;T<VTOT.size();T++) {
      |               ~^~~~~~~~~~~~
bridge.cpp:56:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (ll i=0;i<=v.size();i++) {
      |               ~^~~~~~~~~~

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