oj.uz

Submission #499242

# Submission time Handle Problem Language Result Execution time Memory
499242 2021-12-27T13:54:25 Z dennisstar Shopping Plans (CCO20_day2problem3) C++17
0 / 25
 70 ms 18296 KB 
#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, 0)), 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';

		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>=0) k--, cout<<"-1\n";

	return 0;
}

Compilation message

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:53: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]
   53 |   if (!d.in&&ni!=-1&&s[ni]!=v[ni].size()&&e[ni]) {

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 4 ms 816 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 3 ms 848 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 3 ms 716 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 716 KB Output is correct
20 Correct 3 ms 844 KB Output is correct
21 Incorrect 1 ms 332 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 18296 KB Output is correct
2 Correct 66 ms 18088 KB Output is correct
3 Correct 66 ms 18104 KB Output is correct
4 Correct 70 ms 18120 KB Output is correct
5 Correct 56 ms 10032 KB Output is correct
6 Correct 58 ms 9688 KB Output is correct
7 Correct 66 ms 17828 KB Output is correct
8 Correct 62 ms 17728 KB Output is correct
9 Incorrect 5 ms 844 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 4 ms 816 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 3 ms 848 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 3 ms 716 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 716 KB Output is correct
20 Correct 3 ms 844 KB Output is correct
21 Incorrect 1 ms 332 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2908 KB Output is correct
2 Incorrect 36 ms 1740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 4 ms 816 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 3 ms 848 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 3 ms 716 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 716 KB Output is correct
20 Correct 3 ms 844 KB Output is correct
21 Incorrect 1 ms 332 KB Output isn't correct
22 Halted 0 ms 0 KB -