oj.uz

Submission #884831

# Submission time Handle Problem Language Result Execution time Memory
884831 2023-12-08T14:06:39 Z Hakiers Palembang Bridges (APIO15_bridge) C++17
17 / 100
 2000 ms 4296 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 1e5 + 7;
constexpr ll oo = 2e18;
ll total;
pair<ll, ll> T[MAXN];
vector<ll> Z;
int n, k;

ll check(ll l, ll r){
	ll res = 0;
	
	
	for(int i = 1; i <= n; i++){
		if(T[i].first == -1) continue;
		if(T[i].first <= l && l <= T[i].second) continue;
		if(T[i].first <= r && r <= T[i].second) continue;
		
		ll cost1 = min(abs(T[i].first - l), abs(T[i].second-l));
		ll cost2 = min(abs(T[i].first - r), abs(T[i].second-r));
		res += 2*min(cost1, cost2);
	}
	return res;
}

ll solve(){
	ll res = oo;
	
	if(k == 2){
	for(int i = 0; i < Z.size(); i++)
		for(int j = i; j < Z.size(); j++)
			res = min(res, check(Z[i], Z[j]));
	}
	else {
		for(int j = 0; j < Z.size(); j++)
				res = min(res, check(Z[j], Z[j]));
	}

	return res;
}

int main(){
	cin >> k >> n;
	
	for(int i = 1; i <= n; i++){
		char x, y;
		ll a, b;
		cin >> x >> a >> y >> b;
		if(b < a) swap(a, b);
		if(x != y){
			total += (b-a+1);
			T[i] = {a, b};
		}
		else{
			total += (b-a);
			T[i] = {-1, -1};
		}
		Z.push_back(a);
		Z.push_back(b);
	}
	
	sort(Z.begin(), Z.end());
	
	
	cout << total + solve() << "\n";
}

Compilation message

bridge.cpp: In function 'll solve()':
bridge.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < Z.size(); i++)
      |                 ~~^~~~~~~~~~
bridge.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int j = i; j < Z.size(); j++)
      |                  ~~^~~~~~~~~~
bridge.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int j = 0; j < Z.size(); j++)
      |                  ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 444 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 8 ms 516 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 10 ms 344 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Correct 7 ms 452 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 8 ms 348 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 8 ms 348 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Correct 7 ms 348 KB Output is correct
12 Execution timed out 2101 ms 4296 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 5 ms 428 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 7 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 7 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 7 ms 348 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 7 ms 344 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 7 ms 348 KB Output is correct
11 Correct 4 ms 444 KB Output is correct
12 Correct 7 ms 348 KB Output is correct
13 Execution timed out 2007 ms 344 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 7 ms 448 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 7 ms 444 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 7 ms 348 KB Output is correct
13 Execution timed out 2090 ms 348 KB Time limit exceeded
14 Halted 0 ms 0 KB -