답안 #34190 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
34190	2017-11-08T09:21:56 Z	nibnalin	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	689 ms	16648 KB

bridge

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

typedef long long int lli;

const lli maxn = lli(1e5)+5, inf = lli(1e17)+5;

lli n, S[maxn], T[maxn], pref[maxn], suff[maxn], psum, asum;
vector<pair<lli, lli>> A;
multiset<lli> peeche, aage;

inline bool cmp(pair<lli, lli>& a, pair<lli, lli>& b)
{
	return (a.first+a.second < b.first+b.second);
}

void daalo(lli v)
{
	if(peeche.empty())
	{
		peeche.insert(v), psum += v;
		return;
	}

	if(v < *peeche.rbegin()) peeche.insert(v), psum += v;
	else aage.insert(v), asum += v;

	while(lli(peeche.size()) < lli(aage.size()))
	{
		lli x = *aage.begin();
		aage.erase(aage.begin()), asum -= x;
		peeche.insert(x), psum += x;
	}

	while(lli(aage.size()) < lli(peeche.size()))
	{
		lli x = *peeche.rbegin();
		peeche.erase(peeche.find(x)), psum -= x;
		aage.insert(x), asum += x;
	}
}

void solve()
{
	n = lli(A.size());
	sort(A.begin(), A.end(), cmp);

	peeche.clear(), aage.clear();
	psum = asum = 0;
	for(lli i = 0;i < n;i++)
	{
		daalo(A[i].first), daalo(A[i].second);
		lli tmp = *peeche.rbegin();
		pref[i] = lli(peeche.size())*tmp-psum+asum-lli(aage.size())*tmp;
		//cout << A[i].first << " " << A[i].second << " " << pref[i] << " " << tmp << "\n";
	}

	peeche.clear(), aage.clear();
	psum = asum = 0;
	for(lli i = n-1;i >= 0;i--)
	{
		daalo(A[i].first), daalo(A[i].second);
		lli tmp = *peeche.rbegin();
		suff[i] = lli(peeche.size())*tmp-psum+asum-lli(aage.size())*tmp;
	}
}

int main(void)
{
	lli k, res = 0;
	string p, q;
	scanf("%lld%lld", &k, &n);

	for(lli i = 0;i < n;i++)
	{
		cin >> p >> S[i] >> q >> T[i];
		if(p == q) res += abs(S[i]-T[i]);
		else
		{
			res++;
			A.push_back({S[i], T[i]});
		}
	}

	if(!A.empty())
	{
		solve();
	
		if(k == 1) res += pref[n-1];
		else
		{
			lli ans = inf;
			for(lli i = 0;i < n-1;i++) ans = min(ans, pref[i]+suff[i+1]);
			res += ans;
		}
	}
	
	printf("%lld\n", res);
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:76:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &k, &n);
                           ^

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	5148 KB	Output is correct
2	Correct	0 ms	5148 KB	Output is correct
3	Correct	0 ms	5280 KB	Output is correct
4	Correct	0 ms	5280 KB	Output is correct
5	Correct	0 ms	5280 KB	Output is correct
6	Correct	0 ms	5280 KB	Output is correct
7	Correct	0 ms	5280 KB	Output is correct
8	Correct	0 ms	5280 KB	Output is correct
9	Correct	3 ms	5280 KB	Output is correct
10	Correct	0 ms	5280 KB	Output is correct
11	Correct	3 ms	5280 KB	Output is correct
12	Correct	303 ms	16648 KB	Output is correct
13	Correct	689 ms	16648 KB	Output is correct
14	Correct	579 ms	15592 KB	Output is correct
15	Correct	283 ms	11664 KB	Output is correct
16	Correct	293 ms	16648 KB	Output is correct
17	Correct	369 ms	16648 KB	Output is correct
18	Correct	289 ms	16648 KB	Output is correct
19	Correct	383 ms	16648 KB	Output is correct
20	Correct	346 ms	16648 KB	Output is correct
21	Correct	396 ms	16648 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	메모리	Grader output
1	Correct	5148 KB	Output is correct
2	Correct	5148 KB	Output is correct
3	Correct	5148 KB	Output is correct
4	Correct	5148 KB	Output is correct
5	Correct	5148 KB	Output is correct
6	Correct	5148 KB	Output is correct
7	Correct	5148 KB	Output is correct
8	Correct	5148 KB	Output is correct
9	Correct	5148 KB	Output is correct
10	Correct	5148 KB	Output is correct
11	Correct	5148 KB	Output is correct
12	Correct	5148 KB	Output is correct

Subtask #4
32.0 / 32.0

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

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	5148 KB	Output is correct
2	Correct	0 ms	5148 KB	Output is correct
3	Correct	0 ms	5148 KB	Output is correct
4	Correct	0 ms	5148 KB	Output is correct
5	Correct	0 ms	5148 KB	Output is correct
6	Correct	0 ms	5148 KB	Output is correct
7	Correct	0 ms	5148 KB	Output is correct
8	Correct	0 ms	5148 KB	Output is correct
9	Correct	0 ms	5148 KB	Output is correct
10	Correct	0 ms	5148 KB	Output is correct
11	Correct	0 ms	5148 KB	Output is correct
12	Correct	0 ms	5148 KB	Output is correct
13	Correct	0 ms	5280 KB	Output is correct
14	Correct	0 ms	5280 KB	Output is correct
15	Correct	0 ms	5280 KB	Output is correct
16	Correct	0 ms	5148 KB	Output is correct
17	Correct	0 ms	5280 KB	Output is correct
18	Correct	0 ms	5148 KB	Output is correct
19	Correct	0 ms	5280 KB	Output is correct
20	Correct	0 ms	5280 KB	Output is correct
21	Correct	0 ms	5280 KB	Output is correct
22	Correct	0 ms	5280 KB	Output is correct
23	Correct	0 ms	5280 KB	Output is correct
24	Correct	0 ms	5280 KB	Output is correct
25	Correct	283 ms	16648 KB	Output is correct
26	Correct	419 ms	16648 KB	Output is correct
27	Correct	586 ms	16648 KB	Output is correct
28	Correct	549 ms	16648 KB	Output is correct
29	Correct	479 ms	16648 KB	Output is correct
30	Correct	223 ms	11136 KB	Output is correct
31	Correct	293 ms	16648 KB	Output is correct
32	Correct	343 ms	16648 KB	Output is correct
33	Correct	276 ms	16648 KB	Output is correct
34	Correct	359 ms	16648 KB	Output is correct
35	Correct	339 ms	16648 KB	Output is correct
36	Correct	336 ms	16648 KB	Output is correct
37	Correct	326 ms	16648 KB	Output is correct

답안 #34190

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