oj.uz

Submission #497315

# Submission time Handle Problem Language Result Execution time Memory
497315 2021-12-23T02:49:51 Z daongocha Shopping Plans (CCO20_day2problem3) C++14
25 / 25
 284 ms 68396 KB 
#include <bits/stdc++.h>

#define int long long

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);

using namespace std;

const int MAXN = 2e5 + 5;
vector<int> group[MAXN];
int l[MAXN], r[MAXN];
int pidx[MAXN];
int pstart[MAXN];

struct state {
	int idx, cur, cnt, lst;
	bool skippable, is_base;
	state() {}
	state(int I, int a, int b, int c): idx(I), cur(a), cnt(b), lst(c) {
		skippable = is_base = 0;
	}
	bool operator < (state p) const {
		return idx < p.idx;
	} 
};

int lst(int a) {
	return (l[a] ? group[a][l[a] - 1] : 0);
}

signed main() {
	#ifndef PICHU_LOCAL_DEF
		//fileopen1("LAH");
	#endif

	cin.tie(0)->sync_with_stdio(0);

	int n, m, k;
	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++) {
		int a, c; cin >> a >> c;
		group[a].push_back(c);
	}
	
	for (int i = 1; i <= m; i++) {
		cin >> l[i] >> r[i];
	}
	
	priority_queue<pair<int, state>, vector<pair<int, state>>, greater<pair<int, state>>> pq;
	int base = 0;

	for (int i = 1; i <= m; i++) {
		sort(group[i].begin(), group[i].end());
		int sz = group[i].size();
		if (sz < l[i]) {
			while (k--) cout << -1 << '\n';
			return 0;
		}

		for (int j = 0; j < l[i]; j++) base += group[i][j];
		pidx[i] = i;
	}

	sort(pidx + 1, pidx + m + 1, [](int a, int b) {
		int left;
		if (!r[a]) left = 1e9;
		else left = (l[a] == group[a].size() ? 1e9 : group[a][l[a]] - lst(a));
		
		int right;
		if (!r[b]) right = 1e9;
		else right = (l[b] == group[b].size() ? 1e9 : group[b][l[b]] - lst(b));
		
		return left < right;
	});

	state sv;
	if (l[pidx[1]]) sv = state(1, l[pidx[1]] - 1, 1, group[pidx[1]].size()), 
	sv.is_base = 1;
	else {
		sv = state(1, 0, 1, group[pidx[1]].size());
		cout << base << '\n';
		base += group[pidx[1]][0];
		sv.skippable = 1;
		sv.is_base = 0;
		k--;
	}
	pq.push({base, sv});

	for (int i = 1; i <= k; i++) {
		if (pq.empty()) {
			cout << -1;
			if (i < k) cout << '\n';
			continue;
		}
		else {
			auto cs = pq.top(); pq.pop();
			int cost = cs.first; state st = cs.second;
			cout << cost;
			if (i < k) cout << '\n';

			// Divide into different states

			int idx = pidx[st.idx], nidx = pidx[st.idx + 1];

			// Move to next idx
			if (!st.is_base && st.idx < m && l[nidx] != group[nidx].size() && r[nidx]) {
				state nw(st.idx + 1, l[nidx], 1, group[nidx].size());
				nw.skippable = 1;
				if (st.skippable)  {
					pq.push({cost + group[nidx][l[nidx]] - lst(nidx) - group[idx][l[idx]] + lst(idx), nw});
				}
				pq.push({cost + group[nidx][l[nidx]] - lst(nidx), nw});
			}

			// move cur to right
			if (st.cur + 1 < st.lst) {
				state nw = st;
				nw.is_base = nw.skippable = 0;
				if (st.is_base) {
					nw.is_base = 0;
					nw.skippable = 1;
				}
				nw.cur++;
				pq.push({cost + group[idx][nw.cur] - group[idx][nw.cur - 1], nw});
			}

			// fix cur, move pointer before
			{
				state nw = st;
				nw.lst = st.cur;
				nw.is_base = nw.skippable = 0;
				
				if (st.cnt < l[idx]) {
					nw.cnt++;
					int nxt = l[idx] - st.cnt - 1;
					nw.cur = nxt + 1;
					if (nw.cur < nw.lst) pq.push({cost - group[idx][nxt] + group[idx][nxt + 1], nw});
				}
			}

			// add new pointer to 0
			if (st.cnt >= l[idx] && st.cnt < r[idx]) {
				state nw = st;
				nw.is_base = nw.skippable = 0;
				nw.cnt++;
				nw.lst = st.cur;
				nw.cur = 0;
				if (nw.lst) pq.push({cost + group[idx][0], nw});
			}
		}
	}
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:69:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   else left = (l[a] == group[a].size() ? 1e9 : group[a][l[a]] - lst(a));
      |                ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:73:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   else right = (l[b] == group[b].size() ? 1e9 : group[b][l[b]] - lst(b));
      |                 ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:108:45: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    if (!st.is_base && st.idx < m && l[nidx] != group[nidx].size() && r[nidx]) {
      |                                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5736 KB Output is correct
2 Correct 5 ms 5748 KB Output is correct
3 Correct 6 ms 5732 KB Output is correct
4 Correct 5 ms 5676 KB Output is correct
5 Correct 6 ms 5744 KB Output is correct
6 Correct 5 ms 5780 KB Output is correct
7 Correct 5 ms 5648 KB Output is correct
8 Correct 5 ms 5652 KB Output is correct
9 Correct 4 ms 5200 KB Output is correct
10 Correct 6 ms 5732 KB Output is correct
11 Correct 4 ms 5160 KB Output is correct
12 Correct 4 ms 5292 KB Output is correct
13 Correct 5 ms 5520 KB Output is correct
14 Correct 6 ms 5748 KB Output is correct
15 Correct 4 ms 5352 KB Output is correct
16 Correct 4 ms 5596 KB Output is correct
17 Correct 5 ms 5712 KB Output is correct
18 Correct 4 ms 5200 KB Output is correct
19 Correct 4 ms 5604 KB Output is correct
20 Correct 5 ms 5776 KB Output is correct
21 Correct 3 ms 5072 KB Output is correct
22 Correct 4 ms 5520 KB Output is correct
23 Correct 5 ms 5680 KB Output is correct
24 Correct 4 ms 5300 KB Output is correct
25 Correct 4 ms 5288 KB Output is correct
26 Correct 5 ms 5648 KB Output is correct
27 Correct 5 ms 5648 KB Output is correct
28 Correct 7 ms 5624 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 31236 KB Output is correct
2 Correct 82 ms 31024 KB Output is correct
3 Correct 75 ms 31092 KB Output is correct
4 Correct 75 ms 31284 KB Output is correct
5 Correct 64 ms 18592 KB Output is correct
6 Correct 78 ms 18476 KB Output is correct
7 Correct 76 ms 30828 KB Output is correct
8 Correct 76 ms 30712 KB Output is correct
9 Correct 16 ms 5660 KB Output is correct
10 Correct 77 ms 31168 KB Output is correct
11 Correct 22 ms 5860 KB Output is correct
12 Correct 35 ms 7012 KB Output is correct
13 Correct 89 ms 30868 KB Output is correct
14 Correct 70 ms 31204 KB Output is correct
15 Correct 16 ms 5792 KB Output is correct
16 Correct 87 ms 30736 KB Output is correct
17 Correct 73 ms 31008 KB Output is correct
18 Correct 25 ms 6340 KB Output is correct
19 Correct 79 ms 31076 KB Output is correct
20 Correct 68 ms 31472 KB Output is correct
21 Correct 16 ms 5712 KB Output is correct
22 Correct 81 ms 17936 KB Output is correct
23 Correct 73 ms 30456 KB Output is correct
24 Correct 17 ms 5796 KB Output is correct
25 Correct 17 ms 5784 KB Output is correct
26 Correct 58 ms 18672 KB Output is correct
27 Correct 59 ms 18608 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5736 KB Output is correct
2 Correct 5 ms 5748 KB Output is correct
3 Correct 6 ms 5732 KB Output is correct
4 Correct 5 ms 5676 KB Output is correct
5 Correct 6 ms 5744 KB Output is correct
6 Correct 5 ms 5780 KB Output is correct
7 Correct 5 ms 5648 KB Output is correct
8 Correct 5 ms 5652 KB Output is correct
9 Correct 4 ms 5200 KB Output is correct
10 Correct 6 ms 5732 KB Output is correct
11 Correct 4 ms 5160 KB Output is correct
12 Correct 4 ms 5292 KB Output is correct
13 Correct 5 ms 5520 KB Output is correct
14 Correct 6 ms 5748 KB Output is correct
15 Correct 4 ms 5352 KB Output is correct
16 Correct 4 ms 5596 KB Output is correct
17 Correct 5 ms 5712 KB Output is correct
18 Correct 4 ms 5200 KB Output is correct
19 Correct 4 ms 5604 KB Output is correct
20 Correct 5 ms 5776 KB Output is correct
21 Correct 3 ms 5072 KB Output is correct
22 Correct 4 ms 5520 KB Output is correct
23 Correct 5 ms 5680 KB Output is correct
24 Correct 4 ms 5300 KB Output is correct
25 Correct 4 ms 5288 KB Output is correct
26 Correct 5 ms 5648 KB Output is correct
27 Correct 5 ms 5648 KB Output is correct
28 Correct 7 ms 5624 KB Output is correct
29 Correct 76 ms 31236 KB Output is correct
30 Correct 82 ms 31024 KB Output is correct
31 Correct 75 ms 31092 KB Output is correct
32 Correct 75 ms 31284 KB Output is correct
33 Correct 64 ms 18592 KB Output is correct
34 Correct 78 ms 18476 KB Output is correct
35 Correct 76 ms 30828 KB Output is correct
36 Correct 76 ms 30712 KB Output is correct
37 Correct 16 ms 5660 KB Output is correct
38 Correct 77 ms 31168 KB Output is correct
39 Correct 22 ms 5860 KB Output is correct
40 Correct 35 ms 7012 KB Output is correct
41 Correct 89 ms 30868 KB Output is correct
42 Correct 70 ms 31204 KB Output is correct
43 Correct 16 ms 5792 KB Output is correct
44 Correct 87 ms 30736 KB Output is correct
45 Correct 73 ms 31008 KB Output is correct
46 Correct 25 ms 6340 KB Output is correct
47 Correct 79 ms 31076 KB Output is correct
48 Correct 68 ms 31472 KB Output is correct
49 Correct 16 ms 5712 KB Output is correct
50 Correct 81 ms 17936 KB Output is correct
51 Correct 73 ms 30456 KB Output is correct
52 Correct 17 ms 5796 KB Output is correct
53 Correct 17 ms 5784 KB Output is correct
54 Correct 58 ms 18672 KB Output is correct
55 Correct 59 ms 18608 KB Output is correct
56 Correct 199 ms 43500 KB Output is correct
57 Correct 183 ms 40644 KB Output is correct
58 Correct 188 ms 41584 KB Output is correct
59 Correct 159 ms 39324 KB Output is correct
60 Correct 194 ms 31512 KB Output is correct
61 Correct 220 ms 41340 KB Output is correct
62 Correct 154 ms 37600 KB Output is correct
63 Correct 125 ms 35168 KB Output is correct
64 Correct 66 ms 10984 KB Output is correct
65 Correct 175 ms 40668 KB Output is correct
66 Correct 81 ms 13712 KB Output is correct
67 Correct 59 ms 10112 KB Output is correct
68 Correct 101 ms 31560 KB Output is correct
69 Correct 189 ms 41496 KB Output is correct
70 Correct 17 ms 5992 KB Output is correct
71 Correct 98 ms 31792 KB Output is correct
72 Correct 191 ms 39192 KB Output is correct
73 Correct 15 ms 5704 KB Output is correct
74 Correct 84 ms 19896 KB Output is correct
75 Correct 189 ms 43768 KB Output is correct
76 Correct 20 ms 5584 KB Output is correct
77 Correct 78 ms 18556 KB Output is correct
78 Correct 130 ms 35180 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8624 KB Output is correct
2 Correct 54 ms 6856 KB Output is correct
3 Correct 17 ms 5712 KB Output is correct
4 Correct 17 ms 5856 KB Output is correct
5 Correct 230 ms 43760 KB Output is correct
6 Correct 206 ms 42904 KB Output is correct
7 Correct 223 ms 43452 KB Output is correct
8 Correct 198 ms 42764 KB Output is correct
9 Correct 217 ms 43884 KB Output is correct
10 Correct 214 ms 42580 KB Output is correct
11 Correct 195 ms 41828 KB Output is correct
12 Correct 156 ms 41680 KB Output is correct
13 Correct 122 ms 19076 KB Output is correct
14 Correct 204 ms 42944 KB Output is correct
15 Correct 211 ms 42916 KB Output is correct
16 Correct 79 ms 18732 KB Output is correct
17 Correct 92 ms 31236 KB Output is correct
18 Correct 230 ms 42912 KB Output is correct
19 Correct 88 ms 31468 KB Output is correct
20 Correct 101 ms 31108 KB Output is correct
21 Correct 194 ms 42496 KB Output is correct
22 Correct 78 ms 18588 KB Output is correct
23 Correct 98 ms 31280 KB Output is correct
24 Correct 239 ms 43764 KB Output is correct
25 Correct 83 ms 31644 KB Output is correct
26 Correct 80 ms 31588 KB Output is correct
27 Correct 182 ms 41220 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5736 KB Output is correct
2 Correct 5 ms 5748 KB Output is correct
3 Correct 6 ms 5732 KB Output is correct
4 Correct 5 ms 5676 KB Output is correct
5 Correct 6 ms 5744 KB Output is correct
6 Correct 5 ms 5780 KB Output is correct
7 Correct 5 ms 5648 KB Output is correct
8 Correct 5 ms 5652 KB Output is correct
9 Correct 4 ms 5200 KB Output is correct
10 Correct 6 ms 5732 KB Output is correct
11 Correct 4 ms 5160 KB Output is correct
12 Correct 4 ms 5292 KB Output is correct
13 Correct 5 ms 5520 KB Output is correct
14 Correct 6 ms 5748 KB Output is correct
15 Correct 4 ms 5352 KB Output is correct
16 Correct 4 ms 5596 KB Output is correct
17 Correct 5 ms 5712 KB Output is correct
18 Correct 4 ms 5200 KB Output is correct
19 Correct 4 ms 5604 KB Output is correct
20 Correct 5 ms 5776 KB Output is correct
21 Correct 3 ms 5072 KB Output is correct
22 Correct 4 ms 5520 KB Output is correct
23 Correct 5 ms 5680 KB Output is correct
24 Correct 4 ms 5300 KB Output is correct
25 Correct 4 ms 5288 KB Output is correct
26 Correct 5 ms 5648 KB Output is correct
27 Correct 5 ms 5648 KB Output is correct
28 Correct 7 ms 5624 KB Output is correct
29 Correct 76 ms 31236 KB Output is correct
30 Correct 82 ms 31024 KB Output is correct
31 Correct 75 ms 31092 KB Output is correct
32 Correct 75 ms 31284 KB Output is correct
33 Correct 64 ms 18592 KB Output is correct
34 Correct 78 ms 18476 KB Output is correct
35 Correct 76 ms 30828 KB Output is correct
36 Correct 76 ms 30712 KB Output is correct
37 Correct 16 ms 5660 KB Output is correct
38 Correct 77 ms 31168 KB Output is correct
39 Correct 22 ms 5860 KB Output is correct
40 Correct 35 ms 7012 KB Output is correct
41 Correct 89 ms 30868 KB Output is correct
42 Correct 70 ms 31204 KB Output is correct
43 Correct 16 ms 5792 KB Output is correct
44 Correct 87 ms 30736 KB Output is correct
45 Correct 73 ms 31008 KB Output is correct
46 Correct 25 ms 6340 KB Output is correct
47 Correct 79 ms 31076 KB Output is correct
48 Correct 68 ms 31472 KB Output is correct
49 Correct 16 ms 5712 KB Output is correct
50 Correct 81 ms 17936 KB Output is correct
51 Correct 73 ms 30456 KB Output is correct
52 Correct 17 ms 5796 KB Output is correct
53 Correct 17 ms 5784 KB Output is correct
54 Correct 58 ms 18672 KB Output is correct
55 Correct 59 ms 18608 KB Output is correct
56 Correct 199 ms 43500 KB Output is correct
57 Correct 183 ms 40644 KB Output is correct
58 Correct 188 ms 41584 KB Output is correct
59 Correct 159 ms 39324 KB Output is correct
60 Correct 194 ms 31512 KB Output is correct
61 Correct 220 ms 41340 KB Output is correct
62 Correct 154 ms 37600 KB Output is correct
63 Correct 125 ms 35168 KB Output is correct
64 Correct 66 ms 10984 KB Output is correct
65 Correct 175 ms 40668 KB Output is correct
66 Correct 81 ms 13712 KB Output is correct
67 Correct 59 ms 10112 KB Output is correct
68 Correct 101 ms 31560 KB Output is correct
69 Correct 189 ms 41496 KB Output is correct
70 Correct 17 ms 5992 KB Output is correct
71 Correct 98 ms 31792 KB Output is correct
72 Correct 191 ms 39192 KB Output is correct
73 Correct 15 ms 5704 KB Output is correct
74 Correct 84 ms 19896 KB Output is correct
75 Correct 189 ms 43768 KB Output is correct
76 Correct 20 ms 5584 KB Output is correct
77 Correct 78 ms 18556 KB Output is correct
78 Correct 130 ms 35180 KB Output is correct
79 Correct 55 ms 8624 KB Output is correct
80 Correct 54 ms 6856 KB Output is correct
81 Correct 17 ms 5712 KB Output is correct
82 Correct 17 ms 5856 KB Output is correct
83 Correct 230 ms 43760 KB Output is correct
84 Correct 206 ms 42904 KB Output is correct
85 Correct 223 ms 43452 KB Output is correct
86 Correct 198 ms 42764 KB Output is correct
87 Correct 217 ms 43884 KB Output is correct
88 Correct 214 ms 42580 KB Output is correct
89 Correct 195 ms 41828 KB Output is correct
90 Correct 156 ms 41680 KB Output is correct
91 Correct 122 ms 19076 KB Output is correct
92 Correct 204 ms 42944 KB Output is correct
93 Correct 211 ms 42916 KB Output is correct
94 Correct 79 ms 18732 KB Output is correct
95 Correct 92 ms 31236 KB Output is correct
96 Correct 230 ms 42912 KB Output is correct
97 Correct 88 ms 31468 KB Output is correct
98 Correct 101 ms 31108 KB Output is correct
99 Correct 194 ms 42496 KB Output is correct
100 Correct 78 ms 18588 KB Output is correct
101 Correct 98 ms 31280 KB Output is correct
102 Correct 239 ms 43764 KB Output is correct
103 Correct 83 ms 31644 KB Output is correct
104 Correct 80 ms 31588 KB Output is correct
105 Correct 182 ms 41220 KB Output is correct
106 Correct 44 ms 6440 KB Output is correct
107 Correct 56 ms 8884 KB Output is correct
108 Correct 49 ms 7324 KB Output is correct
109 Correct 58 ms 8476 KB Output is correct
110 Correct 242 ms 44756 KB Output is correct
111 Correct 237 ms 43904 KB Output is correct
112 Correct 251 ms 43980 KB Output is correct
113 Correct 221 ms 43380 KB Output is correct
114 Correct 251 ms 44956 KB Output is correct
115 Correct 284 ms 43652 KB Output is correct
116 Correct 214 ms 68396 KB Output is correct
117 Correct 175 ms 42444 KB Output is correct
118 Correct 140 ms 22328 KB Output is correct
119 Correct 95 ms 16116 KB Output is correct
120 Correct 238 ms 43644 KB Output is correct
121 Correct 94 ms 31600 KB Output is correct
122 Correct 100 ms 31508 KB Output is correct
123 Correct 240 ms 44196 KB Output is correct
124 Correct 81 ms 19400 KB Output is correct
125 Correct 106 ms 31256 KB Output is correct
126 Correct 202 ms 43816 KB Output is correct
127 Correct 80 ms 18616 KB Output is correct
128 Correct 92 ms 31844 KB Output is correct
129 Correct 238 ms 45316 KB Output is correct
130 Correct 100 ms 31476 KB Output is correct
131 Correct 100 ms 31416 KB Output is correct
132 Correct 186 ms 42416 KB Output is correct