oj.uz

Submission #794828

# Submission time Handle Problem Language Result Execution time Memory
794828 2023-07-27T00:39:37 Z MODDI Palembang Bridges (APIO15_bridge) C++17
31 / 100
 2000 ms 5136 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<long long> vl;
int k, n;
ll ans = 0;
vl ord;
ll pos[100100][2];
int main(){
	ios_base::sync_with_stdio(false);
	cin>>k>>n;
	memset(pos, -1, sizeof pos);
	for(int i = 0; i < n; i++){
		char side1, side2;
		ll p1, p2;
		cin>>side1>>p1>>side2>>p2;
		if(side1 == side2){
			ans += abs(p1 - p2);
		}
		else
		{
			pos[i][0] = p1;
			pos[i][1] = p2;
			ord.pb(p1);
			ord.pb(p2);
		}
	}
	sort(ord.begin(), ord.end());
	int sz = (int)ord.size();
	if(ord.size() > 0 && k == 1){
		ll pref[sz];
		pref[0] = ord[0];
		for(int i = 1; i < sz; i++)
			pref[i] = pref[i-1] + ord[i];
		ll best = 1e18;
		for(int i = 0; i < sz; i++){
			ll here = ans;
			if(i+1 < sz)
			{
				here += pref[sz-1];
				here -= pref[i];
				here -= (sz - 1 - i) * ord[i];
			}
			if(i){
				here -= pref[i-1];
				here += i * ord[i];
			}
			here += (int)ord.size()/2;
			best = min(best, here);
		}
		cout<<best<<endl;
		return 0;
	}
	else if(ord.size() > 0 && k == 2){
		ll best = 1e18;
		for(int i = 0; i < sz; i++){
			for(int j = i + 1; j < sz; j++){
				// both bridges;
				if(ord[i] == ord[j])	continue;
				ll here = ans;
				for(int s = 0; s < n; s++){
					if(pos[s][0] == -1)	continue;
					ll mn = min(pos[s][0], pos[s][1]), mx = max(pos[s][0], pos[s][1]);
					if(pos[s][0] <= ord[i] && pos[s][1] <= ord[i]){
						here += 2 * ord[i] - pos[s][0] - pos[s][1] + 1;
						//cout<<"BOTH LEFT: "<<mn<<" "<<mx<<" "<<2*ord[i] - mn - mx + 1<<" "<<ord[i]<<" "<<ord[j]<<endl;
					}
					else if(pos[s][0] >= ord[j] && pos[s][1] >= ord[j]){
						here += pos[s][0] + pos[s][1] - 2*ord[j] + 1;
					}
					else if(mn<= ord[i] && mx >= ord[j]){
						here += ord[i] - mn;
						here += mx - ord[i];
						here++;
					}
					else if(mn <= ord[i] && mx <= ord[j]){
						here += ord[i] - mn;
						here += mx - ord[i];
						here++;
					}
					else if(mn <= ord[j] && mx >= ord[j]){
						here += ord[j] - mn;
						here += mx - ord[j];
						here++;
					}
					else if(ord[i] <= mn && mx <= ord[j]){
						ll small = mn + mx - 2 * ord[i] + 1, big = 2*ord[j] - mn - mx + 1;
						here += min(small, big);
					}
					else
					{
						//cout<<mn<<" "<<mx<<" "<<i<<" "<<ord[i]<<" "<<ord[j]<<endl;
						assert(false);
					}
				}
				//if(here == 10)	cout<<ord[i]<<" "<<ord[j]<<endl;
				best = min(best, here);
			}
		}
		cout<<best<<endl;
		return 0;
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 2 ms 1876 KB Output is correct
8 Correct 2 ms 1876 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 22 ms 5136 KB Output is correct
13 Correct 35 ms 5128 KB Output is correct
14 Correct 25 ms 4784 KB Output is correct
15 Correct 20 ms 3884 KB Output is correct
16 Correct 23 ms 5136 KB Output is correct
17 Correct 25 ms 5112 KB Output is correct
18 Correct 35 ms 5092 KB Output is correct
19 Correct 37 ms 5112 KB Output is correct
20 Correct 24 ms 5068 KB Output is correct
21 Correct 35 ms 5128 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 5 ms 1876 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 3 ms 1876 KB Output is correct
8 Correct 6 ms 1876 KB Output is correct
9 Correct 5 ms 1876 KB Output is correct
10 Correct 6 ms 1876 KB Output is correct
11 Correct 4 ms 1868 KB Output is correct
12 Correct 5 ms 1860 KB Output is correct
13 Correct 1952 ms 1908 KB Output is correct
14 Execution timed out 2076 ms 1876 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 5 ms 1876 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 3 ms 1876 KB Output is correct
8 Correct 5 ms 1900 KB Output is correct
9 Correct 5 ms 1876 KB Output is correct
10 Correct 5 ms 1876 KB Output is correct
11 Correct 3 ms 1860 KB Output is correct
12 Correct 5 ms 1876 KB Output is correct
13 Correct 1960 ms 1904 KB Output is correct
14 Execution timed out 2075 ms 1876 KB Time limit exceeded
15 Halted 0 ms 0 KB -