Submission #499253

#	Time	Username	Problem	Language	Result	Execution time	Memory
499253		dennisstar	Shopping Plans (CCO20_day2problem3)	C++17	20 / 25	252 ms	29124 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e9;

struct dt {
	int i, cur, use, lst, sk, in;
	dt(int i=0, int c=0, int u=0, int l=0, int sk=0, int in=0) : i(i), cur(c), use(u), lst(l), sk(sk), in(in) {}
	bool operator <(dt p) const {
		return i>p.i;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, m, k;
	cin>>n>>m>>k;
	vector<vector<int>> v(m);
	vector<int> s(m), e(m);
	ll mn=0;
	for (int i=0, a, b; i<n; i++) cin>>a>>b, v[a-1].emplace_back(b);
	for (int i=0; i<m; i++) {
		cin>>s[i]>>e[i];
		sort(v[i].begin(), v[i].end());
		if (v[i].size()<s[i]) {
			while (k--) cout<<"-1\n";
			return 0;
		}
		for (int j=0; j<s[i]; j++) mn+=v[i][j];
	}

	vector<int> in(m);
	for (int i=0; i<m; i++) in[i]=i;
	auto get = [&](int i) { return s[i]?v[i][s[i]-1]:0; };
	sort(in.begin(), in.end(), [&](int x, int y) {
		return (e[x]&&s[x]<v[x].size()?(v[x][s[x]]-get(x)):INF)
			< (e[y]&&s[y]<v[y].size()?(v[y][s[y]]-get(y)):INF);
	});

	priority_queue<pair<ll, dt>> pq;
	if (s[in[0]]) pq.emplace(-mn, dt(0, s[in[0]]-1, 1, v[in[0]].size(), 0, 1));
	else pq.emplace(-mn-v[in[0]][0], dt(0, 0, 1, v[in[0]].size(), 1)), k--, cout<<mn<<'\n';
	while (pq.size()&&k) {
		auto [cost, d]=pq.top();
		pq.pop();
		int i=in[d.i];
		int ni=d.i+1<m?in[d.i+1]:-1;
		cout<<-cost<<'\n';
		k--;

		if (!d.in&&ni!=-1&&s[ni]!=v[ni].size()&&e[ni]) {
			dt nxt(d.i+1, s[ni], 1, v[ni].size(), 1);
			if (d.sk) pq.emplace(cost-v[ni][s[ni]]+get(ni)+v[i][s[i]]-get(i), nxt);
			pq.emplace(cost-v[ni][s[ni]]+get(ni), nxt);
		}
		if (d.cur+1<d.lst) pq.emplace(cost-v[i][d.cur+1]+v[i][d.cur], dt(d.i, d.cur+1, d.use, d.lst, d.in));
		if (s[i]<=d.use&&d.use<e[i]&&d.cur) pq.emplace(cost-v[i][0], dt(d.i, 0, d.use+1, d.cur, 0));
		if (d.use<s[i]) pq.emplace(cost-v[i][s[i]-d.use]+v[i][s[i]-d.use-1], dt(d.i, s[i]-d.use, d.use+1, d.cur, 0));
	}

	while (k--) cout<<"-1\n";

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:28:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   28 |   if (v[i].size()<s[i]) {
Main.cpp: In lambda function:
Main.cpp:39:21: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   return (e[x]&&s[x]<v[x].size()?(v[x][s[x]]-get(x)):INF)
Main.cpp:40:17: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    < (e[y]&&s[y]<v[y].size()?(v[y][s[y]]-get(y)):INF);
Main.cpp: In function 'int main()':
Main.cpp:54:27: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   if (!d.in&&ni!=-1&&s[ni]!=v[ni].size()&&e[ni]) {

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5