Submission #8407207


Source Code Expand

#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include<bitset>
#include<list>
#include<cassert>
#include<numeric>

using namespace std;

const long long N = 1e5 + 5;

pair<long long, long long> coins[N];
long long dp[N];
long long n;
long long pd[N];
long long x, y, z;
long long ans;
long long javab = 0;

bool cmp(pair<long long, long long> p1, pair<long long, long long> p2)
{
	long long v1 = p1.first - p1.second;
	long long v2 = p2.first - p2.second;
	return v1 < v2;
}

void calc()
{
	multiset<long long> s;
	for (long long i = 0; i < y; i++)
	{
		s.insert(coins[i].second);
		dp[y - 1] += coins[i].second;
	}
	for (long long i = y; i < n; i++)
	{
		long long tmp = coins[i].second;
		dp[i] = dp[i - 1];
		if (*s.begin() < tmp)
		{
			dp[i] = dp[i - 1] + tmp - *s.begin();
			s.erase(s.begin());
			s.insert(tmp);
		}
	}
	reverse(coins, coins + n);
	s.clear();
	for (long long i = 0; i < x; i++)
	{
		s.insert(coins[i].first);
		pd[x - 1] += coins[i].first;
	}
	for (long long i = x; i < n; i++)
	{
		pd[i] = pd[i - 1];
		long long tmp = coins[i].first;
		if (*s.begin() < tmp)
		{
			pd[i] = pd[i - 1] + tmp - *s.begin();
			s.erase(s.begin());
			s.insert(tmp);
		}
	}
	reverse(coins, coins + n);
	reverse(pd, pd + n);

}

int main() 
{
	cin >> x >> y >> z;
	n = x + y + z;
	for (long long i = 0; i < x + y + z; i++)
	{
		long long a, b, c;
		cin >> a >> b >> c;
		coins[i] = {a - c, b - c};
		ans += c;
	}
	sort(coins, coins + n, cmp);
	calc();
	/*
	for (long long i = 0; i < n; i++)
	{
		cout << coins[i].first << " " << coins[i].second << endl;
	}
	cout << endl;
	for (long long i = 0; i < n; i++)
	{
		cout << pd[i] << " ";
	}
	cout << endl;
	*/
	for (long long i = y - 1; i < n - x; i++)
	{
		javab = max(javab, ans + dp[i] + pd[i + 1]);
	}
	cout << javab;


}

Submission Info

Submission Time
Task C - Coins
User Aryanv
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1994 Byte
Status AC
Exec Time 164 ms
Memory 7424 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 3
AC × 35
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 24 ms 1024 KB
subtask_1_03.txt AC 41 ms 1536 KB
subtask_1_04.txt AC 77 ms 3200 KB
subtask_1_05.txt AC 88 ms 2944 KB
subtask_1_06.txt AC 121 ms 3712 KB
subtask_1_07.txt AC 26 ms 1408 KB
subtask_1_08.txt AC 100 ms 3712 KB
subtask_1_09.txt AC 26 ms 1408 KB
subtask_1_10.txt AC 107 ms 3840 KB
subtask_1_11.txt AC 162 ms 6528 KB
subtask_1_12.txt AC 137 ms 5760 KB
subtask_1_13.txt AC 155 ms 7424 KB
subtask_1_14.txt AC 148 ms 4480 KB
subtask_1_15.txt AC 156 ms 4736 KB
subtask_1_16.txt AC 114 ms 6144 KB
subtask_1_17.txt AC 111 ms 5632 KB
subtask_1_18.txt AC 119 ms 4224 KB
subtask_1_19.txt AC 135 ms 4736 KB
subtask_1_20.txt AC 164 ms 5632 KB
subtask_1_21.txt AC 130 ms 5120 KB
subtask_1_22.txt AC 164 ms 5376 KB
subtask_1_23.txt AC 161 ms 6272 KB
subtask_1_24.txt AC 156 ms 4736 KB
subtask_1_25.txt AC 116 ms 7040 KB
subtask_1_26.txt AC 122 ms 6528 KB
subtask_1_27.txt AC 125 ms 4992 KB
subtask_1_28.txt AC 135 ms 4864 KB
subtask_1_29.txt AC 1 ms 256 KB