#include "tickets.h"
#include <bits/stdc++.h>
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ve = vector <T>;
template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
using ull = unsigned long long;
const int oo = 1e9;
const ll OO = 1e18;
const int N = 1e6 + 10;
const int M = 3e3 + 100;
const int mod = 1e9 + 7;
ll dp[M][M];
int p[M][M];
int cnt[M][2];
ve <int> ones[M];
ve <int> zero[M];
set <int> can[M];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
ve <ve <int>> A = x;
set <pair <int, int>> ST;
for (int i = 0; i < n; i++) ST.insert({cnt[i][1], i});
ve <int> used(n, 0);
ll ans = 0;
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row(m);
for (int j = 0; j < m; j++) row[j] = -1;
answer.push_back(row);
}
ve <array <int, 3>> V;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
V.pb({x[i][j] + x[i][m - k + j], i, j});
}
for (int j = m - k; j < m; j++) ans += x[i][j];
}
sort(all(V));
set <pii> cnt;
ve <int> need(n, 0);
ve <ve <int>> have(n);
for (int i = 0; i < k; i++) cnt.insert({0, i});
for (int i = 0; i < k * n / 2; i++) {
ans -= V[i][0];
need[V[i][1]]++;
have[V[i][1]].pb(V[i][2]);
}
for (int i = 0; i < n; i++) {
int nd = need[i];
ve <pii> Z;
while(sz(Z) < nd) {
auto [x, id] = *cnt.begin();
cnt.erase(cnt.begin());
Z.pb({x + 1, id});
}
fe (x, Z) {
cnt.insert(x);
answer[i][have[i].back()] = x.se;
have[i].pop_back();
}
}
for (int i = 0; i < n; i++) {
set <int> can;
for (int j = 0; j < k; j++) can.insert(j);
for (int j = 0; j < m; j++) {
if (answer[i][j] != -1) can.erase(answer[i][j]);
}
for (int j = m - 1; j >= 0; j--) {
if (!sz(can)) break;
answer[i][j] = *can.begin();
can.erase(can.begin());
}
}
allocate_tickets(answer);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
608 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
3 ms |
1236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
23 ms |
3932 KB |
Output is correct |
6 |
Correct |
448 ms |
69396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
2 ms |
764 KB |
Output is correct |
5 |
Correct |
26 ms |
3620 KB |
Output is correct |
6 |
Correct |
640 ms |
74560 KB |
Output is correct |
7 |
Correct |
707 ms |
80004 KB |
Output is correct |
8 |
Correct |
4 ms |
1044 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
7 ms |
1432 KB |
Output is correct |
13 |
Correct |
22 ms |
3300 KB |
Output is correct |
14 |
Correct |
26 ms |
3408 KB |
Output is correct |
15 |
Correct |
793 ms |
83296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
928 KB |
Output is correct |
5 |
Correct |
38 ms |
5056 KB |
Output is correct |
6 |
Correct |
8 ms |
1352 KB |
Output is correct |
7 |
Correct |
7 ms |
1712 KB |
Output is correct |
8 |
Correct |
985 ms |
89592 KB |
Output is correct |
9 |
Correct |
891 ms |
85844 KB |
Output is correct |
10 |
Correct |
915 ms |
85756 KB |
Output is correct |
11 |
Correct |
1006 ms |
90692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
2 ms |
852 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
4 ms |
852 KB |
Output is correct |
6 |
Correct |
3 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
2 ms |
924 KB |
Output is correct |
11 |
Correct |
3 ms |
852 KB |
Output is correct |
12 |
Correct |
3 ms |
928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
2 ms |
852 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
4 ms |
852 KB |
Output is correct |
6 |
Correct |
3 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
2 ms |
852 KB |
Output is correct |
10 |
Correct |
2 ms |
924 KB |
Output is correct |
11 |
Correct |
3 ms |
852 KB |
Output is correct |
12 |
Correct |
3 ms |
928 KB |
Output is correct |
13 |
Correct |
17 ms |
3840 KB |
Output is correct |
14 |
Correct |
19 ms |
3908 KB |
Output is correct |
15 |
Correct |
26 ms |
4368 KB |
Output is correct |
16 |
Correct |
35 ms |
5056 KB |
Output is correct |
17 |
Correct |
1 ms |
592 KB |
Output is correct |
18 |
Correct |
3 ms |
868 KB |
Output is correct |
19 |
Correct |
2 ms |
752 KB |
Output is correct |
20 |
Correct |
28 ms |
3908 KB |
Output is correct |
21 |
Correct |
35 ms |
4400 KB |
Output is correct |
22 |
Correct |
34 ms |
4252 KB |
Output is correct |
23 |
Correct |
33 ms |
4672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
608 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
3 ms |
1236 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
3 ms |
852 KB |
Output is correct |
11 |
Correct |
23 ms |
3932 KB |
Output is correct |
12 |
Correct |
448 ms |
69396 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
2 ms |
764 KB |
Output is correct |
17 |
Correct |
26 ms |
3620 KB |
Output is correct |
18 |
Correct |
640 ms |
74560 KB |
Output is correct |
19 |
Correct |
707 ms |
80004 KB |
Output is correct |
20 |
Correct |
4 ms |
1044 KB |
Output is correct |
21 |
Correct |
1 ms |
596 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
23 |
Correct |
1 ms |
596 KB |
Output is correct |
24 |
Correct |
7 ms |
1432 KB |
Output is correct |
25 |
Correct |
22 ms |
3300 KB |
Output is correct |
26 |
Correct |
26 ms |
3408 KB |
Output is correct |
27 |
Correct |
793 ms |
83296 KB |
Output is correct |
28 |
Correct |
1 ms |
596 KB |
Output is correct |
29 |
Correct |
1 ms |
596 KB |
Output is correct |
30 |
Correct |
1 ms |
596 KB |
Output is correct |
31 |
Correct |
3 ms |
928 KB |
Output is correct |
32 |
Correct |
38 ms |
5056 KB |
Output is correct |
33 |
Correct |
8 ms |
1352 KB |
Output is correct |
34 |
Correct |
7 ms |
1712 KB |
Output is correct |
35 |
Correct |
985 ms |
89592 KB |
Output is correct |
36 |
Correct |
891 ms |
85844 KB |
Output is correct |
37 |
Correct |
915 ms |
85756 KB |
Output is correct |
38 |
Correct |
1006 ms |
90692 KB |
Output is correct |
39 |
Correct |
1 ms |
596 KB |
Output is correct |
40 |
Correct |
2 ms |
852 KB |
Output is correct |
41 |
Correct |
2 ms |
852 KB |
Output is correct |
42 |
Correct |
2 ms |
852 KB |
Output is correct |
43 |
Correct |
4 ms |
852 KB |
Output is correct |
44 |
Correct |
3 ms |
852 KB |
Output is correct |
45 |
Correct |
1 ms |
596 KB |
Output is correct |
46 |
Correct |
1 ms |
596 KB |
Output is correct |
47 |
Correct |
2 ms |
852 KB |
Output is correct |
48 |
Correct |
2 ms |
924 KB |
Output is correct |
49 |
Correct |
3 ms |
852 KB |
Output is correct |
50 |
Correct |
3 ms |
928 KB |
Output is correct |
51 |
Correct |
17 ms |
3840 KB |
Output is correct |
52 |
Correct |
19 ms |
3908 KB |
Output is correct |
53 |
Correct |
26 ms |
4368 KB |
Output is correct |
54 |
Correct |
35 ms |
5056 KB |
Output is correct |
55 |
Correct |
1 ms |
592 KB |
Output is correct |
56 |
Correct |
3 ms |
868 KB |
Output is correct |
57 |
Correct |
2 ms |
752 KB |
Output is correct |
58 |
Correct |
28 ms |
3908 KB |
Output is correct |
59 |
Correct |
35 ms |
4400 KB |
Output is correct |
60 |
Correct |
34 ms |
4252 KB |
Output is correct |
61 |
Correct |
33 ms |
4672 KB |
Output is correct |
62 |
Correct |
47 ms |
9764 KB |
Output is correct |
63 |
Correct |
47 ms |
9828 KB |
Output is correct |
64 |
Correct |
98 ms |
12664 KB |
Output is correct |
65 |
Correct |
297 ms |
41368 KB |
Output is correct |
66 |
Correct |
417 ms |
48544 KB |
Output is correct |
67 |
Correct |
7 ms |
1688 KB |
Output is correct |
68 |
Correct |
9 ms |
1372 KB |
Output is correct |
69 |
Correct |
449 ms |
77816 KB |
Output is correct |
70 |
Correct |
741 ms |
87204 KB |
Output is correct |
71 |
Correct |
947 ms |
99708 KB |
Output is correct |
72 |
Correct |
932 ms |
92652 KB |
Output is correct |
73 |
Correct |
886 ms |
104352 KB |
Output is correct |
74 |
Correct |
658 ms |
78420 KB |
Output is correct |
75 |
Correct |
672 ms |
90548 KB |
Output is correct |