oj.uz

Submission #39771

# Submission time Handle Problem Language Result Execution time Memory
39771 2018-01-18T11:54:48 Z 14kg Palembang Bridges (APIO15_bridge) C++11
0 / 100
 1 ms 1952 KB 
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#define N 100001
#define min2(x,y) (x<y?x:y)

using namespace std;
typedef pair<int, pair<int, int> > pip;
int n, K, out;
pair<int, int> in[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;

void f1() {
	int x1 = n, x2 = 0, w = 0, sum = 0, tot;

	for (int i = 1; i <= n; i++) {
		sum += in[i].first;
		Q.push({ in[i].first,1 }), Q.push({ in[i].second,2 });
	} tot = sum * 2;

	while (!Q.empty()) {
		sum -= (Q.top().first - w)*x1, sum += (Q.top().first - w)*x2;
		tot = min2(tot, sum * 2), w = Q.top().first;
		if (Q.top().second == 1) x1--;
		else x2++;
		Q.pop();
	} out += tot;
}
int main() {
//	freopen("input.txt", "r", stdin);
	int k, x, y;
	char in_a, in_b;

	scanf("%d %d ", &K, &k);
	while (k--) {
		scanf("%c %d %c %d ", &in_a, &x, &in_b, &y);
		if (x > y) x += y, y = x - y, x -= y;
		out += y - x;
		if (in_a != in_b) out++, in[++n] = { x,y };
	}

	if (K == 1) f1();
	printf("%d", out);
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:36:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d ", &K, &k);
                         ^
bridge.cpp:38:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c %d %c %d ", &in_a, &x, &in_b, &y);
                                              ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1952 KB Output is correct
2 Correct 0 ms 1952 KB Output is correct
3 Correct 0 ms 1952 KB Output is correct
4 Correct 1 ms 1952 KB Output is correct
5 Incorrect 1 ms 1952 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 1952 KB Output is correct
2 Correct 0 ms 1952 KB Output is correct
3 Correct 0 ms 1952 KB Output is correct
4 Correct 1 ms 1952 KB Output is correct
5 Incorrect 0 ms 1952 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1952 KB Output is correct
2 Correct 0 ms 1952 KB Output is correct
3 Correct 0 ms 1952 KB Output is correct
4 Incorrect 0 ms 1952 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1952 KB Output is correct
2 Correct 0 ms 1952 KB Output is correct
3 Correct 0 ms 1952 KB Output is correct
4 Incorrect 0 ms 1952 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1952 KB Output is correct
2 Correct 0 ms 1952 KB Output is correct
3 Correct 0 ms 1952 KB Output is correct
4 Incorrect 0 ms 1952 KB Output isn't correct
5 Halted 0 ms 0 KB -