Submission #497315

#	Time	Username	Problem	Language	Result	Execution time	Memory
497315		daongocha	Shopping Plans (CCO20_day2problem3)	C++14	25 / 25	284 ms	68396 KiB

Main

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5