Submission #545989

#	Time	Username	Problem	Language	Result	Execution time	Memory
545989		aryan12	Cloud Computing (CEOI18_clo)	C++17	100 / 100	738 ms	2644 KiB

clo

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
 
const int N = 1e5 + 5, INF = 1e16;
vector<vector<int> > dp(2, vector<int> (N, -INF));
 
bool cmp(array<int, 3> a, array<int, 3> b)
{
	if(a[1] == b[1])
	{
		return a[0] > b[0]; //so that stores are before customers
	}
	return a[1] > b[1];
}
 
void Solve() 
{
	int n;
	cin >> n;
	vector<array<int, 3> > store(n);
	vector<array<int, 3> > together;
	for(int i = 0; i < n; i++)
	{
		cin >> store[i][0] >> store[i][1] >> store[i][2];
		together.push_back({store[i][0], store[i][1], -store[i][2]});
	}
	int m;
	cin >> m;
	vector<array<int, 3> > customer(m);
	for(int i = 0; i < m; i++)
	{
		cin >> customer[i][0] >> customer[i][1] >> customer[i][2];
		together.push_back({-customer[i][0], customer[i][1], customer[i][2]});
	}
	sort(together.begin(), together.end(), cmp);
 
	dp[0][0] = 0;
	for(int i = 0; i < together.size(); i++)
	{
		//cout << together[i][0] << " " << together[i][1] << " " << together[i][2] << "\n";
		int cur = (i + 1) % 2, prev = i % 2;
		for(int j = 0; j < N; j++)
		{
			dp[cur][j] = dp[prev][j];
		}
		if(together[i][0] > 0) //it is a store
		{
			for(int j = together[i][0]; j < N; j++)
			{
				dp[cur][j] = max(dp[cur][j], dp[prev][j - together[i][0]] + together[i][2]);
			}
		}
		else
		{
			for(int j = 0; j < N + together[i][0]; j++) //together[i][0] is actually -ve
			{
				dp[cur][j] = max(dp[cur][j], dp[prev][j - together[i][0]] + together[i][2]);
			}
		}
	}
	int ans = 0;
	int x = together.size();
	int cur = x % 2;
	for(int i = 0; i < N; i++)
	{
		ans = max(ans, dp[cur][i]);
	}
	cout << ans << "\n";
}
 
int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) 
	{
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

clo.cpp: In function 'void Solve()':
clo.cpp:41:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < together.size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10