답안 #49948 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49948	2018-06-05T04:38:51 Z	tmwilliamlin168	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	64 ms	3852 KB

bridge

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(ll x) {
	ll rev=x;
	int count = 0;
	if(x == 0) {
putchar_unlocked('0');
return;
}
	while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
	rev = 0;
	while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
	while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
	while(count--)
putchar_unlocked('0');
}
inline char rc() {
	char c=getchar_unlocked();
	while(c!='A'&&c!='B')
		c=getchar_unlocked();
	return c;
}

const int mxN=1e5;
int k, n, med;
ll ba, a1[mxN+1], a2, bs, ts;
vector<pii> ps;
priority_queue<int> bpq;
priority_queue<int, vector<int>, greater<int>> tpq;

inline void upd(int x) {
	if(x<med)
		bpq.push(x), bs+=x;
	else
		tpq.push(x), ts+=x;
	if(bpq.size()+2<=tpq.size()) {
		bpq.push(med), bs+=med;
		med=tpq.top(), tpq.pop(), ts-=med;
	} else if(bpq.size()>=tpq.size()+2) {
		tpq.push(med), ts+=med;
		med=bpq.top(), bpq.pop(), bs-=med;
	}
}

int main() {
	k=in(), n=in();
	for(int i=0; i<n; ++i) {
		char z1, z2;
		pii pi;
		z1=rc(), pi.fi=in(), z2=rc(), pi.se=in();
		if(z1!=z2) {
			ps.push_back(pi);
			++ba;
		} else
			ba+=abs(pi.fi-pi.se);
	}
	sort(ps.begin(), ps.end(), [](const pii &a, const pii &b) {
		return a.fi+a.se<b.fi+b.se;
	});
	for(int i=0; i<ps.size(); ++i) {
		upd(ps[i].fi), upd(ps[i].se);
		a1[i+1]=ts-(ll)tpq.size()*med+((ll)bpq.size()-1)*med-bs;
	}
	a2=a1[ps.size()];
	if(k==2) {
		bpq=priority_queue<int>(), tpq=priority_queue<int, vector<int>, greater<int>>();
		med=bs=ts=0;
		for(int i=ps.size()-1; i>0; --i) {
			upd(ps[i].fi), upd(ps[i].se);
			a2=min(a1[i]+ts-(ll)tpq.size()*med+((ll)bpq.size()-1)*med-bs, a2);
		}
	}
	out(ba+a2);
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:92:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ps.size(); ++i) {
               ~^~~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	560 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	2 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	2 ms	640 KB	Output is correct
11	Correct	2 ms	640 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	640 KB	Output is correct
2	Correct	2 ms	640 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	2 ms	640 KB	Output is correct
7	Correct	2 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	3 ms	640 KB	Output is correct
12	Correct	17 ms	3412 KB	Output is correct
13	Correct	33 ms	3544 KB	Output is correct
14	Correct	27 ms	3544 KB	Output is correct
15	Correct	22 ms	3544 KB	Output is correct
16	Correct	20 ms	3544 KB	Output is correct
17	Correct	26 ms	3544 KB	Output is correct
18	Correct	14 ms	3544 KB	Output is correct
19	Correct	42 ms	3544 KB	Output is correct
20	Correct	22 ms	3544 KB	Output is correct
21	Correct	29 ms	3544 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	3544 KB	Output is correct
2	Correct	2 ms	3544 KB	Output is correct
3	Correct	2 ms	3544 KB	Output is correct
4	Correct	3 ms	3544 KB	Output is correct
5	Correct	2 ms	3544 KB	Output is correct
6	Correct	2 ms	3544 KB	Output is correct
7	Correct	2 ms	3544 KB	Output is correct
8	Correct	2 ms	3544 KB	Output is correct
9	Correct	2 ms	3544 KB	Output is correct
10	Correct	2 ms	3544 KB	Output is correct
11	Correct	2 ms	3544 KB	Output is correct
12	Correct	2 ms	3544 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	3544 KB	Output is correct
2	Correct	2 ms	3544 KB	Output is correct
3	Correct	2 ms	3544 KB	Output is correct
4	Correct	2 ms	3544 KB	Output is correct
5	Correct	2 ms	3544 KB	Output is correct
6	Correct	2 ms	3544 KB	Output is correct
7	Correct	2 ms	3544 KB	Output is correct
8	Correct	2 ms	3544 KB	Output is correct
9	Correct	2 ms	3544 KB	Output is correct
10	Correct	2 ms	3544 KB	Output is correct
11	Correct	2 ms	3544 KB	Output is correct
12	Correct	2 ms	3544 KB	Output is correct
13	Correct	2 ms	3544 KB	Output is correct
14	Correct	2 ms	3544 KB	Output is correct
15	Correct	2 ms	3544 KB	Output is correct
16	Correct	2 ms	3544 KB	Output is correct
17	Correct	2 ms	3544 KB	Output is correct
18	Correct	2 ms	3544 KB	Output is correct
19	Correct	2 ms	3544 KB	Output is correct
20	Correct	3 ms	3544 KB	Output is correct
21	Correct	2 ms	3544 KB	Output is correct
22	Correct	2 ms	3544 KB	Output is correct
23	Correct	2 ms	3544 KB	Output is correct
24	Correct	2 ms	3544 KB	Output is correct

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	3544 KB	Output is correct
2	Correct	2 ms	3544 KB	Output is correct
3	Correct	2 ms	3544 KB	Output is correct
4	Correct	2 ms	3544 KB	Output is correct
5	Correct	2 ms	3544 KB	Output is correct
6	Correct	2 ms	3544 KB	Output is correct
7	Correct	2 ms	3544 KB	Output is correct
8	Correct	2 ms	3544 KB	Output is correct
9	Correct	2 ms	3544 KB	Output is correct
10	Correct	2 ms	3544 KB	Output is correct
11	Correct	2 ms	3544 KB	Output is correct
12	Correct	2 ms	3544 KB	Output is correct
13	Correct	2 ms	3544 KB	Output is correct
14	Correct	2 ms	3544 KB	Output is correct
15	Correct	3 ms	3544 KB	Output is correct
16	Correct	2 ms	3544 KB	Output is correct
17	Correct	2 ms	3544 KB	Output is correct
18	Correct	2 ms	3544 KB	Output is correct
19	Correct	2 ms	3544 KB	Output is correct
20	Correct	3 ms	3544 KB	Output is correct
21	Correct	2 ms	3544 KB	Output is correct
22	Correct	2 ms	3544 KB	Output is correct
23	Correct	3 ms	3544 KB	Output is correct
24	Correct	3 ms	3544 KB	Output is correct
25	Correct	21 ms	3728 KB	Output is correct
26	Correct	43 ms	3728 KB	Output is correct
27	Correct	62 ms	3728 KB	Output is correct
28	Correct	64 ms	3764 KB	Output is correct
29	Correct	53 ms	3764 KB	Output is correct
30	Correct	27 ms	3764 KB	Output is correct
31	Correct	38 ms	3764 KB	Output is correct
32	Correct	48 ms	3764 KB	Output is correct
33	Correct	21 ms	3828 KB	Output is correct
34	Correct	47 ms	3828 KB	Output is correct
35	Correct	36 ms	3852 KB	Output is correct
36	Correct	49 ms	3852 KB	Output is correct
37	Correct	21 ms	3852 KB	Output is correct

답안 #49948

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 37.0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
37.0 / 37.0