제출 #1277748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277748		zyb_txdy	Shopping Plans (CCO20_day2problem3)	C++17	25 / 25	223 ms	47136 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
#define lowbit(x) (x & -x)

using namespace std;

constexpr int N = 2e5 + 5;

int n, m, k;
int l[N], r[N], ord[N];
vector<int> a[N];
struct Node1 {
	int x, y, z;
	ll w;
	bool operator<(const Node1& t) const {
		return w > t.w;
	}
};
struct Node2 {
	int x, y;
	ll w;
	bool operator<(const Node2& t) const {
		return w > t.w;
	}
};

priority_queue<Node1> q[N];
vector<ll> res[N];
ll get(int i, int k) {
	if (res[i].size() >= k) {
		return res[i][k - 1];
	}
	if (res[i].size() == 0) {
		ll cnt = 0;
		for (int j = 0; j < l[i]; ++j) {
			cnt += a[i][j];
		}
		q[i].push({l[i] - 1, l[i] - 1, a[i].size(), cnt});
	}
	while (res[i].size() < k && !q[i].empty()) {
		auto u = q[i].top();
		q[i].pop();
		res[i].push_back(u.w);
		if (u.x == u.y && u.y + 1 < min(u.z, r[i]) && u.z == a[i].size()) {
			q[i].push({u.x + 1, u.x + 1, u.z, u.w + a[i][u.x + 1]});
		}
		if (u.x >= 0) {
			if (u.y + 1 < u.z) {
				q[i].push({u.x, u.y + 1, u.z, u.w + (a[i][u.y + 1] - a[i][u.y])});
			}
			if (u.x < u.y && u.x > 0) {
				q[i].push({u.x - 1, u.x, u.y, u.w + (a[i][u.x] - a[i][u.x - 1])});
			}
		}
	}
	if (res[i].size() < k) {
		return -1;
	} else {
		return res[i][k - 1];
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
	}
	for (int i = 1; i <= m; ++i) {
		cin >> l[i] >> r[i];
		if (a[i].size() < l[i]) {
			for (int j = 1; j <= k; ++j) {
				cout << "-1\n";
			}
			return 0;
		}
		sort(a[i].begin(), a[i].end());
	}
	
	iota(ord + 1, ord + m + 1, 1);
	sort(ord + 1, ord + m + 1, [](int x, int y) {
		if (get(x, 2) < 0 || get(y, 2) < 0) {
			return get(x, 2) > get(y, 2);
		}
		return get(x, 2) - get(x, 1) < get(y, 2) - get(y, 1);
	});
	
	ll w = 0;
	for (int i = 1; i <= m; ++i) {
		w += get(i, 1);
	}
	cout << w << '\n';
	priority_queue<Node2> q;
	if (get(ord[1], 2) >= get(ord[1], 1)) {
		q.push({1, 2, w + (get(ord[1], 2) - get(ord[1], 1))});
	}
	for (int i = 1; i < k; ++i) {
		if (q.empty()) {
			cout << "-1\n";
			continue;
		}
		auto u = q.top();
		q.pop();
		cout << u.w << '\n';
		w = get(ord[u.x], u.y + 1) - get(ord[u.x], u.y);
		if (w >= 0) {
			q.push({u.x, u.y + 1, u.w + w});
		}
		if (u.x < m) {
			w = get(ord[u.x + 1], 2) - get(ord[u.x + 1], 1);
			if (w >= 0) {
				q.push({u.x + 1, 2, u.w + w});
				if (u.y == 2) {
					w = (get(ord[u.x + 1], 2) - get(ord[u.x + 1], 1)) - (get(ord[u.x], 2) - get(ord[u.x], 1));
					if (w >= 0) {
						q.push({u.x + 1, 2, u.w + w});
					}
				}
			}
		}
	}
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'long long int get(int, int)':
Main.cpp:39:57: warning: narrowing conversion of 'a[i].std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   39 |                 q[i].push({l[i] - 1, l[i] - 1, a[i].size(), cnt});
      |                                                ~~~~~~~~~^~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5