# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
432729 | 2021-06-18T12:53:49 Z | Enkognit | Carnival Tickets (IOI20_tickets) | C++14 | 1475 ms | 140652 KB |
#include <bits/stdc++.h> #include "tickets.h" #define ll long long #define mp make_pair #define pb push_back #define pll pair<ll,ll> #define pii pair<int,int> #define fi first #define se second #define all(v) v.begin(),v.end() using namespace std; ll qq[100005]; vector<vector<pll> > a; vector<ll> mn[100005], mx[100005]; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); std::vector<std::vector<int> > answer; set<pll> s; for (int i = 0; i < n; i++) { vector<pll> vv; for (int j = 0; j < m; j++) vv.pb(mp(x[i][j], j)); qq[i]=k; sort(all(vv)); a.pb(vv); //cout << i << " : " << a[i].back().fi << " " << a[i][qq[i]-1].fi << "\n"; s.insert(mp(-(a[i].back().fi+a[i][qq[i]-1].fi), i)); } for (int i = 0; i < k*n/2; i++) { pll x=*s.begin(); s.erase(s.begin()); //cout << x.fi << " " << x.se << "\n"; qq[x.se]--; if (qq[x.se]>0) { s.insert(mp(-(a[x.se][a[x.se].size()-(k-qq[x.se])-1].fi+a[x.se][qq[x.se]-1].fi), x.se)); } } //cout << "---\n"; answer.resize(n); for (int i = 0; i < n; i++) { answer[i].resize(m, -1); for (int j = 0; j < a[i].size(); j++) if (j<qq[i]) mn[i].pb(a[i][j].se); else if (j>=a[i].size()-(k-qq[i])) mx[i].pb(a[i][j].se); reverse(all(mn[i])); //cout << i << " " << mx[i].size() << " " << mn[i].size() << "\n"; } ll ans=0; for (int i = 0; i < k; i++) { //cout << i << "\n"; vector<pll> vv; for (int j = 0; j < n; j++) vv.pb(mp(-mx[j].size(), j)); sort(all(vv)); for (int j = 0; j < n/2; j++) { answer[vv[j].se][mx[vv[j].se].back()]=i; ans+=a[vv[j].se][mx[vv[j].se].back()].fi; mx[vv[j].se].pop_back(); } for (int j = n/2; j < n; j++) { answer[vv[j].se][mn[vv[j].se].back()]=i; ans-=a[vv[j].se][mn[vv[j].se].back()].fi; mn[vv[j].se].pop_back(); } } //cout << "---\n"; allocate_tickets(answer); return ans; } /* 4 2 1 5 9 1 4 3 6 2 7 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Correct | 4 ms | 4940 KB | Output is correct |
4 | Correct | 4 ms | 4940 KB | Output is correct |
5 | Correct | 4 ms | 5068 KB | Output is correct |
6 | Correct | 6 ms | 5580 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Correct | 4 ms | 5000 KB | Output is correct |
4 | Correct | 6 ms | 5324 KB | Output is correct |
5 | Correct | 41 ms | 9320 KB | Output is correct |
6 | Correct | 769 ms | 102980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Correct | 4 ms | 4940 KB | Output is correct |
4 | Correct | 6 ms | 5264 KB | Output is correct |
5 | Correct | 38 ms | 9276 KB | Output is correct |
6 | Correct | 868 ms | 109088 KB | Output is correct |
7 | Correct | 959 ms | 115276 KB | Output is correct |
8 | Correct | 9 ms | 5452 KB | Output is correct |
9 | Correct | 4 ms | 4940 KB | Output is correct |
10 | Correct | 4 ms | 4940 KB | Output is correct |
11 | Correct | 5 ms | 4940 KB | Output is correct |
12 | Correct | 12 ms | 6060 KB | Output is correct |
13 | Correct | 32 ms | 8628 KB | Output is correct |
14 | Correct | 32 ms | 8700 KB | Output is correct |
15 | Correct | 990 ms | 115648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Correct | 4 ms | 4940 KB | Output is correct |
4 | Correct | 8 ms | 5388 KB | Output is correct |
5 | Correct | 49 ms | 10628 KB | Output is correct |
6 | Correct | 12 ms | 5856 KB | Output is correct |
7 | Correct | 14 ms | 6220 KB | Output is correct |
8 | Correct | 1399 ms | 140336 KB | Output is correct |
9 | Correct | 1326 ms | 132984 KB | Output is correct |
10 | Correct | 1352 ms | 131684 KB | Output is correct |
11 | Correct | 1475 ms | 140652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Correct | 8 ms | 5216 KB | Output is correct |
3 | Correct | 10 ms | 5312 KB | Output is correct |
4 | Correct | 8 ms | 5260 KB | Output is correct |
5 | Correct | 7 ms | 5324 KB | Output is correct |
6 | Correct | 9 ms | 5376 KB | Output is correct |
7 | Correct | 5 ms | 4940 KB | Output is correct |
8 | Correct | 4 ms | 4940 KB | Output is correct |
9 | Correct | 8 ms | 5324 KB | Output is correct |
10 | Correct | 8 ms | 5324 KB | Output is correct |
11 | Correct | 9 ms | 5264 KB | Output is correct |
12 | Correct | 9 ms | 5324 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Correct | 8 ms | 5216 KB | Output is correct |
3 | Correct | 10 ms | 5312 KB | Output is correct |
4 | Correct | 8 ms | 5260 KB | Output is correct |
5 | Correct | 7 ms | 5324 KB | Output is correct |
6 | Correct | 9 ms | 5376 KB | Output is correct |
7 | Correct | 5 ms | 4940 KB | Output is correct |
8 | Correct | 4 ms | 4940 KB | Output is correct |
9 | Correct | 8 ms | 5324 KB | Output is correct |
10 | Correct | 8 ms | 5324 KB | Output is correct |
11 | Correct | 9 ms | 5264 KB | Output is correct |
12 | Correct | 9 ms | 5324 KB | Output is correct |
13 | Correct | 37 ms | 9372 KB | Output is correct |
14 | Correct | 35 ms | 9424 KB | Output is correct |
15 | Correct | 49 ms | 9916 KB | Output is correct |
16 | Correct | 77 ms | 10588 KB | Output is correct |
17 | Correct | 5 ms | 5068 KB | Output is correct |
18 | Correct | 8 ms | 5388 KB | Output is correct |
19 | Correct | 5 ms | 5196 KB | Output is correct |
20 | Correct | 39 ms | 9384 KB | Output is correct |
21 | Correct | 45 ms | 9808 KB | Output is correct |
22 | Correct | 54 ms | 9740 KB | Output is correct |
23 | Correct | 56 ms | 10168 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Correct | 4 ms | 4940 KB | Output is correct |
4 | Correct | 4 ms | 4940 KB | Output is correct |
5 | Correct | 4 ms | 5068 KB | Output is correct |
6 | Correct | 6 ms | 5580 KB | Output is correct |
7 | Correct | 4 ms | 4940 KB | Output is correct |
8 | Correct | 4 ms | 4940 KB | Output is correct |
9 | Correct | 4 ms | 5000 KB | Output is correct |
10 | Correct | 6 ms | 5324 KB | Output is correct |
11 | Correct | 41 ms | 9320 KB | Output is correct |
12 | Correct | 769 ms | 102980 KB | Output is correct |
13 | Correct | 4 ms | 4940 KB | Output is correct |
14 | Correct | 4 ms | 4940 KB | Output is correct |
15 | Correct | 4 ms | 4940 KB | Output is correct |
16 | Correct | 6 ms | 5264 KB | Output is correct |
17 | Correct | 38 ms | 9276 KB | Output is correct |
18 | Correct | 868 ms | 109088 KB | Output is correct |
19 | Correct | 959 ms | 115276 KB | Output is correct |
20 | Correct | 9 ms | 5452 KB | Output is correct |
21 | Correct | 4 ms | 4940 KB | Output is correct |
22 | Correct | 4 ms | 4940 KB | Output is correct |
23 | Correct | 5 ms | 4940 KB | Output is correct |
24 | Correct | 12 ms | 6060 KB | Output is correct |
25 | Correct | 32 ms | 8628 KB | Output is correct |
26 | Correct | 32 ms | 8700 KB | Output is correct |
27 | Correct | 990 ms | 115648 KB | Output is correct |
28 | Correct | 4 ms | 4940 KB | Output is correct |
29 | Correct | 4 ms | 4940 KB | Output is correct |
30 | Correct | 4 ms | 4940 KB | Output is correct |
31 | Correct | 8 ms | 5388 KB | Output is correct |
32 | Correct | 49 ms | 10628 KB | Output is correct |
33 | Correct | 12 ms | 5856 KB | Output is correct |
34 | Correct | 14 ms | 6220 KB | Output is correct |
35 | Correct | 1399 ms | 140336 KB | Output is correct |
36 | Correct | 1326 ms | 132984 KB | Output is correct |
37 | Correct | 1352 ms | 131684 KB | Output is correct |
38 | Correct | 1475 ms | 140652 KB | Output is correct |
39 | Correct | 4 ms | 4940 KB | Output is correct |
40 | Correct | 8 ms | 5216 KB | Output is correct |
41 | Correct | 10 ms | 5312 KB | Output is correct |
42 | Correct | 8 ms | 5260 KB | Output is correct |
43 | Correct | 7 ms | 5324 KB | Output is correct |
44 | Correct | 9 ms | 5376 KB | Output is correct |
45 | Correct | 5 ms | 4940 KB | Output is correct |
46 | Correct | 4 ms | 4940 KB | Output is correct |
47 | Correct | 8 ms | 5324 KB | Output is correct |
48 | Correct | 8 ms | 5324 KB | Output is correct |
49 | Correct | 9 ms | 5264 KB | Output is correct |
50 | Correct | 9 ms | 5324 KB | Output is correct |
51 | Correct | 37 ms | 9372 KB | Output is correct |
52 | Correct | 35 ms | 9424 KB | Output is correct |
53 | Correct | 49 ms | 9916 KB | Output is correct |
54 | Correct | 77 ms | 10588 KB | Output is correct |
55 | Correct | 5 ms | 5068 KB | Output is correct |
56 | Correct | 8 ms | 5388 KB | Output is correct |
57 | Correct | 5 ms | 5196 KB | Output is correct |
58 | Correct | 39 ms | 9384 KB | Output is correct |
59 | Correct | 45 ms | 9808 KB | Output is correct |
60 | Correct | 54 ms | 9740 KB | Output is correct |
61 | Correct | 56 ms | 10168 KB | Output is correct |
62 | Correct | 91 ms | 17036 KB | Output is correct |
63 | Correct | 90 ms | 17124 KB | Output is correct |
64 | Correct | 143 ms | 19852 KB | Output is correct |
65 | Correct | 516 ms | 58628 KB | Output is correct |
66 | Correct | 623 ms | 63644 KB | Output is correct |
67 | Correct | 14 ms | 6412 KB | Output is correct |
68 | Correct | 10 ms | 5836 KB | Output is correct |
69 | Correct | 752 ms | 113304 KB | Output is correct |
70 | Correct | 1103 ms | 126148 KB | Output is correct |
71 | Correct | 1431 ms | 140272 KB | Output is correct |
72 | Correct | 1178 ms | 123616 KB | Output is correct |
73 | Correct | 1361 ms | 135612 KB | Output is correct |
74 | Correct | 931 ms | 110248 KB | Output is correct |
75 | Correct | 1164 ms | 122632 KB | Output is correct |