제출 #48219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48219		square1001	Palembang Bridges (APIO15_bridge)	C++14	31 / 100	2081 ms	2812 KiB

bridge

#include <cmath>
#include <string>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, K;
	cin >> K >> N;
	long long curs = 0;
	vector<int> a, b;
	for (int i = 0; i < N; i++) {
		string sa, sb; int va, vb;
		cin >> sa >> va >> sb >> vb;
		if (va > vb) swap(va, vb);
		if (sa == sb) curs += vb - va;
		else {
			a.push_back(va);
			b.push_back(vb);
		}
	}
	vector<int> pv;
	pv.insert(pv.end(), a.begin(), a.end());
	pv.insert(pv.end(), b.begin(), b.end());
	sort(pv.begin(), pv.end());
	N = a.size();
	if (K == 1) {
		long long ret = curs + N;
		for (int i = 0; i < N; i++) {
			ret += abs(a[i] - pv[N]) + abs(b[i] - pv[N]);
		}
		cout << ret << '\n';
	}
	else {
		long long ret = (N == 0 ? 0 : 1LL << 60);
		for (int i = 0; i < pv.size(); i++) {
			for (int j = 0; j < i; j++) {
				long long sum = 0;
				for (int k = 0; k < N; k++) {
					if (a[k] + b[k] > pv[i] + pv[j]) {
						sum += abs(a[k] - pv[i]) + abs(b[k] - pv[i]);
					}
					else {
						sum += abs(a[k] - pv[j]) + abs(b[k] - pv[j]);
					}
				}
				ret = min(ret, sum);
			}
		}
		cout << N + ret + curs << '\n';
	}
	return 0;
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < pv.size(); i++) {
                   ~~^~~~~~~~~~~

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