oj.uz

답안 #763864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763864 2023-06-23T01:28:20 Z qwerasdfzxcl Palembang Bridges (APIO15_bridge) C++17
0 / 100
 5 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll solve2(vector<pair<int, int>> V){
	if (V.empty()) return 0;
	ll ret = 4e18;
	vector<int> X;
	for (auto &[x, y]:V) {X.push_back(x); X.push_back(y);}

	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());

	vector<ll> V2;
	for (int i=0;i<(int)X.size();i++){
		ll t = 4e18;
		for (int j=i+1;j<(int)X.size();j++){
			ll val = 0;
			for (auto &[x, y]:V){
				val += min(abs(x-X[i]) + abs(y-X[i]), abs(x-X[j]) + abs(y-X[j]));
			}
			ret = min(ret, val);
			t = min(t, val);
		}

		V2.push_back(t);
	}

	int prv = 0;
	for (int i=0;i<(int)V2.size()-1;i++){
		int typ;
		if (V2[i] > V2[i+1]) typ = 0;
		else if (V2[i] == V2[i+1]) typ = 1;
		else typ = 2;

		assert(prv <= typ);
		prv = typ;
	}

	return ret;
}

int main(){
	int k, n;
	scanf("%d %d", &k, &n);

	ll ans = 0;
	vector<pair<int, int>> V;

	for (int i=1;i<=n;i++){
		char cx, cy;
		int px, py;
		scanf(" %c %d %c %d", &cx, &px, &cy, &py);

		if (cx==cy) {ans += abs(px-py); continue;}
		if (cx=='B') swap(px, py);
		V.emplace_back(px, py);

		ans++;
	}

	if (k==2) ans += solve2(V);
	printf("%lld\n", ans);
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d %d", &k, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf(" %c %d %c %d", &cx, &px, &cy, &py);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Runtime error 4 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Runtime error 4 ms 432 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Runtime error 5 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -