oj.uz

Submission #499119

# Submission time Handle Problem Language Result Execution time Memory
499119 2021-12-27T08:56:14 Z dennisstar Shopping Plans (CCO20_day2problem3) C++17
0 / 25
 71 ms 18252 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;
	sort(in.begin(), in.end(), [&](int x, int y) {
		return (e[x]&&s[x]<v[x].size()?(v[x][s[x]]-(s[x]?v[x][s[x]-1]:0)):INF)
			< (e[y]&&s[y]<v[y].size()?(v[y][s[y]]-(s[y]?v[y][s[y]-1]:0)):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, 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, 0);
			if (d.sk) pq.emplace(cost-v[ni][s[ni]]+(s[ni]?v[ni][s[ni]-1]:0)+v[i][s[i]]-(s[i]?v[i][s[i]-1]:0), nxt);
			pq.emplace(cost-v[ni][s[ni]]+(s[ni]?v[ni][s[ni]-1]:0), 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, 0));
		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, 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, 0));
	}

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

	return 0;
}
/*
5 2 7
1 5
1 3
2 3
1 6
2 1
1 1
1 1
*/

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:38: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]
   38 |   return (e[x]&&s[x]<v[x].size()?(v[x][s[x]]-(s[x]?v[x][s[x]-1]:0)):INF)
Main.cpp:39: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]
   39 |    < (e[y]&&s[y]<v[y].size()?(v[y][s[y]]-(s[y]?v[y][s[y]-1]:0)):INF);
Main.cpp: In function 'int main()':
Main.cpp:52: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]
   52 |   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 3 ms 836 KB Output is correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 3 ms 824 KB Output is correct
5 Correct 3 ms 968 KB Output is correct
6 Correct 3 ms 832 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 1 ms 368 KB Output is correct
10 Correct 3 ms 820 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 696 KB Output is correct
14 Correct 3 ms 844 KB Output is correct
15 Correct 2 ms 452 KB Output is correct
16 Correct 2 ms 704 KB Output is correct
17 Correct 3 ms 844 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 684 KB Output is correct
20 Correct 3 ms 972 KB Output is correct
21 Incorrect 1 ms 320 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 66 ms 18252 KB Output is correct
2 Correct 71 ms 18180 KB Output is correct
3 Correct 70 ms 18240 KB Output is correct
4 Correct 62 ms 18184 KB Output is correct
5 Correct 56 ms 10080 KB Output is correct
6 Correct 64 ms 9756 KB Output is correct
7 Correct 66 ms 17940 KB Output is correct
8 Correct 66 ms 17920 KB Output is correct
9 Incorrect 8 ms 964 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 3 ms 836 KB Output is correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 3 ms 824 KB Output is correct
5 Correct 3 ms 968 KB Output is correct
6 Correct 3 ms 832 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 1 ms 368 KB Output is correct
10 Correct 3 ms 820 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 696 KB Output is correct
14 Correct 3 ms 844 KB Output is correct
15 Correct 2 ms 452 KB Output is correct
16 Correct 2 ms 704 KB Output is correct
17 Correct 3 ms 844 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 684 KB Output is correct
20 Correct 3 ms 972 KB Output is correct
21 Incorrect 1 ms 320 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 2888 KB Output isn't correct
2 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 3 ms 836 KB Output is correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 3 ms 824 KB Output is correct
5 Correct 3 ms 968 KB Output is correct
6 Correct 3 ms 832 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 1 ms 368 KB Output is correct
10 Correct 3 ms 820 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 696 KB Output is correct
14 Correct 3 ms 844 KB Output is correct
15 Correct 2 ms 452 KB Output is correct
16 Correct 2 ms 704 KB Output is correct
17 Correct 3 ms 844 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 684 KB Output is correct
20 Correct 3 ms 972 KB Output is correct
21 Incorrect 1 ms 320 KB Output isn't correct
22 Halted 0 ms 0 KB -