oj.uz

Submission #499232

# Submission time Handle Problem Language Result Execution time Memory
499232 2021-12-27T13:42:54 Z dennisstar Shopping Plans (CCO20_day2problem3) C++17
0 / 25
 113 ms 30632 KB 
#include <bits/stdc++.h>
#define int long long

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;
	}
};

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

	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:29:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wsign-compare]
   29 |   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<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   return (e[x]&&s[x]<v[x].size()?(v[x][s[x]]-(s[x]?v[x][s[x]-1]:0)):INF)
Main.cpp:40:17: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    < (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:53:27: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long 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 1144 KB Output is correct
2 Correct 4 ms 1124 KB Output is correct
3 Correct 3 ms 1148 KB Output is correct
4 Correct 3 ms 1028 KB Output is correct
5 Correct 3 ms 1112 KB Output is correct
6 Correct 3 ms 1120 KB Output is correct
7 Correct 3 ms 996 KB Output is correct
8 Correct 3 ms 1000 KB Output is correct
9 Correct 2 ms 452 KB Output is correct
10 Correct 4 ms 1104 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 1 ms 624 KB Output is correct
13 Correct 2 ms 848 KB Output is correct
14 Correct 3 ms 1136 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 2 ms 876 KB Output is correct
17 Correct 4 ms 1024 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 3 ms 860 KB Output is correct
20 Correct 5 ms 1124 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 77 ms 30632 KB Output is correct
2 Correct 85 ms 30456 KB Output is correct
3 Correct 85 ms 30484 KB Output is correct
4 Correct 113 ms 30464 KB Output is correct
5 Correct 78 ms 16036 KB Output is correct
6 Correct 72 ms 15776 KB Output is correct
7 Correct 82 ms 30288 KB Output is correct
8 Correct 79 ms 30196 KB Output is correct
9 Incorrect 10 ms 956 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 1144 KB Output is correct
2 Correct 4 ms 1124 KB Output is correct
3 Correct 3 ms 1148 KB Output is correct
4 Correct 3 ms 1028 KB Output is correct
5 Correct 3 ms 1112 KB Output is correct
6 Correct 3 ms 1120 KB Output is correct
7 Correct 3 ms 996 KB Output is correct
8 Correct 3 ms 1000 KB Output is correct
9 Correct 2 ms 452 KB Output is correct
10 Correct 4 ms 1104 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 1 ms 624 KB Output is correct
13 Correct 2 ms 848 KB Output is correct
14 Correct 3 ms 1136 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 2 ms 876 KB Output is correct
17 Correct 4 ms 1024 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 3 ms 860 KB Output is correct
20 Correct 5 ms 1124 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 Incorrect 57 ms 4456 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 1144 KB Output is correct
2 Correct 4 ms 1124 KB Output is correct
3 Correct 3 ms 1148 KB Output is correct
4 Correct 3 ms 1028 KB Output is correct
5 Correct 3 ms 1112 KB Output is correct
6 Correct 3 ms 1120 KB Output is correct
7 Correct 3 ms 996 KB Output is correct
8 Correct 3 ms 1000 KB Output is correct
9 Correct 2 ms 452 KB Output is correct
10 Correct 4 ms 1104 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 1 ms 624 KB Output is correct
13 Correct 2 ms 848 KB Output is correct
14 Correct 3 ms 1136 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 2 ms 876 KB Output is correct
17 Correct 4 ms 1024 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 3 ms 860 KB Output is correct
20 Correct 5 ms 1124 KB Output is correct
21 Incorrect 1 ms 332 KB Output isn't correct
22 Halted 0 ms 0 KB -