oj.uz

Submission #886259

# Submission time Handle Problem Language Result Execution time Memory
886259 2023-12-11T16:15:16 Z tsumondai Palembang Bridges (APIO15_bridge) C++17
0 / 100
 2 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;

#define Task "APIO15_bridge"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int MAXN = 1e5 + 5;

const int oo = 1e9, mod = 1e9 + 7;
int K, N, M;
int D[MAXN], E[MAXN];

struct Z {
	int a, b;
} A[MAXN];

void proc(int V[]) {
	if (!N) return;
	int val = abs(A[1].a - A[1].b);
	priority_queue <int> p, q;
	int mid = A[1].a;
	if (A[1].b < mid) p.push(A[1].b);
	else q.push(-A[1].b);
	V[1] = val;
	for (int i = 2; i <= N; i++) {
		val += abs(mid - A[i].a) + abs(mid - A[i].b);
		if (A[i].a < mid) p.push(A[i].a);
		else q.push(-A[i].a);
		if (A[i].b < mid) p.push(A[i].b);
		else q.push(-A[i].b);
		while (p.size() < q.size()) {
			int nxt = -q.top(); q.pop();
			p.push(mid);
			val += (int)(nxt - mid) * p.size() - (int)(nxt - mid) * (q.size() + 1);
			mid = nxt;
		}
		while (p.size() > q.size() + 1) {
			int nxt = p.top(); p.pop();
			q.push(-mid);
			val += (int)(mid - nxt) * q.size() - (int)(mid - nxt) * (p.size() + 1);
			mid = nxt;
		}
		V[i] = val;
	}
}

int process() {
	cin >> K >> M;
	vector <int> arr;
	int def = 0;
	while (M--) {
		char p, q; int a, b;
		cin >> p >> a >> q >> b;
		if (p == q) { def += abs(a - b); continue; }
		A[++N] = {a, b};
	}
	sort(A + 1, A + N + 1, [](const Z & a, const Z & b) {
		return a.a + a.b < b.a + b.b;
	});
	proc(D);
	if (K == 1) { cout << D[N] + def + N; return 0; }
	reverse(A + 1, A + N + 1);
	proc(E);
	int ans = 1e9;
	for (int i = 0; i <= N; i++) ans = min(ans, def + D[i] + E[N - i] + N);
	cout << ans;
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	if (fopen(Task".INP", "r")) {
		freopen(Task".INP", "r", stdin);
		freopen(Task".OUT", "w", stdout);
	}
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

// dont stop

Compilation message

bridge.cpp: In function 'int process()':
bridge.cpp:59:15: warning: control reaches end of non-void function [-Wreturn-type]
   59 |  vector <int> arr;
      |               ^~~
bridge.cpp: In function 'int main()':
bridge.cpp:82:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   freopen(Task".INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:83:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   freopen(Task".OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 1 ms 416 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -