#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;
auto get = [&](int i) { return s[i]?v[i][s[i]-1]:0; };
sort(in.begin(), in.end(), [&](int x, int y) {
return (e[x]&&s[x]<v[x].size()?(v[x][s[x]]-get(x)):INF)
< (e[y]&&s[y]<v[y].size()?(v[y][s[y]]-get(x)):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-v[in[0]][0], 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);
if (d.sk) pq.emplace(cost-v[ni][s[ni]]+get(ni)+v[i][s[i]]-get(i), nxt);
pq.emplace(cost-v[ni][s[ni]]+get(ni), 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));
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));
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));
}
while (k>=0) k--, cout<<"-1\n";
return 0;
}
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:39: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]
39 | return (e[x]&&s[x]<v[x].size()?(v[x][s[x]]-get(x)):INF)
Main.cpp:40: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]
40 | < (e[y]&&s[y]<v[y].size()?(v[y][s[y]]-get(x)):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<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if (!d.in&&ni!=-1&&s[ni]!=v[ni].size()&&e[ni]) {
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
18292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
2932 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
1740 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
