#include<bits/stdc++.h>
#include "tickets.h"
using namespace std;
using ll = long long;
const int inf = 1e9;
#ifdef ONPC
#define debug(args...) {cout << "[" << #args << "]: "; debug_out(args);}
#else
#define debug(args...) {42;}
#endif
void debug_out() {
cout << endl;
}
template<typename H, typename... T>
void debug_out(vector<H> h, T... t) {
cout << "{";
for (H i : h) cout << i << ", ";
cout << "}, ";
debug_out(t...);
}
template<typename H, typename... T>
void debug_out(H h, T... t) {
cout << h << ", ";
debug_out(t...);
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<tuple<int,int,int>> pos(n);
for (int i = 0; i < n; i++)
pos[i] = {-x[i][0], x[i][m-1], i};
sort(pos.begin(), pos.end(), [&](auto a, auto b) {
return get<1>(a) - get<0>(a) > get<1>(b) - get<0>(b);
});
int space = m - k;
vector score(n, vector<ll>());
for (int i = 0; i < n; i++) {
ll cur = accumulate(x[i].begin(), x[i].end(), 0ll);
ll base = cur;
if (!space) score[i].push_back(0);
for (int j = 0; j < m; j++) {
cur -= x[i][j];
if (j >= space) {
cur += -x[i][j - space];
}
if (j >= space-1)
score[i].push_back(cur - base);
}
assert((int)score[i].size() == k + 1);
debug(i, score[i]);
}
constexpr ll infl = 1e18;
vector dp(n+1, vector<ll>(n / 2 * k + 1, -infl));
vector par(n+1, vector<int>(n / 2 * k + 1, -1));
dp[n][0] = 0;
for (int i = n-1; i >= 0; i--) {
for (int rem = 0; rem <= n / 2 * k; rem++) {
for (int use = 0; use <= k&& use <= rem; use++) {
if (dp[i+1][rem - use] + score[i][use] > dp[i][rem]) {
dp[i][rem] = dp[i+1][rem - use] + score[i][use];
par[i][rem] = use;
}
}
}
debug(i, dp[i], par[i]);
}
debug(dp[0][n/2 * k]);
vector<int> use(n);
for (int i = 0, rem = n / 2 * k; i < n; i++) {
use[i] = par[i][rem];
rem -= par[i][rem];
}
debug(use);
vector type(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < use[i]; j++)
type[i][j] = -1;
for (int j = 0; j < k - use[i]; j++)
rbegin(type[i])[j] = 1;
}
ll sum = 0;
vector ans(n, vector<int>(m, -1));
int round_low = 0;
for (int i = 0; i < n; i++) {
debug(i, ans[i]);
for (int j = 0; j < m; j++) {
if (type[i][j] == -1) {
sum -= x[i][j];
ans[i][j] = round_low++;
if (round_low >= k) round_low -= k;
}
}
int round = round_low;
for (int j = 0; j < m; j++) {
if (type[i][j] == 1) {
sum += x[i][j];
ans[i][j] = round++;
if (round >= k) round -= k;
}
}
debug(i, ans[i]);
}
allocate_tickets(ans);
return sum;
}
Compilation message
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
10 | #define debug(args...) {42;}
| ^~
tickets.cpp:55:9: note: in expansion of macro 'debug'
55 | debug(i, score[i]);
| ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
10 | #define debug(args...) {42;}
| ^~
tickets.cpp:71:9: note: in expansion of macro 'debug'
71 | debug(i, dp[i], par[i]);
| ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
10 | #define debug(args...) {42;}
| ^~
tickets.cpp:73:5: note: in expansion of macro 'debug'
73 | debug(dp[0][n/2 * k]);
| ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
10 | #define debug(args...) {42;}
| ^~
tickets.cpp:80:5: note: in expansion of macro 'debug'
80 | debug(use);
| ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
10 | #define debug(args...) {42;}
| ^~
tickets.cpp:94:9: note: in expansion of macro 'debug'
94 | debug(i, ans[i]);
| ^~~~~
tickets.cpp:10:25: warning: statement has no effect [-Wunused-value]
10 | #define debug(args...) {42;}
| ^~
tickets.cpp:110:9: note: in expansion of macro 'debug'
110 | debug(i, ans[i]);
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
852 KB |
Output is correct |
6 |
Correct |
13 ms |
14164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
18 ms |
3644 KB |
Output is correct |
6 |
Correct |
439 ms |
75400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
7 ms |
1948 KB |
Output is correct |
5 |
Correct |
738 ms |
82780 KB |
Output is correct |
6 |
Runtime error |
1520 ms |
2097152 KB |
Execution killed with signal 9 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
19 ms |
3572 KB |
Output is correct |
5 |
Execution timed out |
3048 ms |
163152 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
572 KB |
Output is correct |
3 |
Correct |
2 ms |
724 KB |
Output is correct |
4 |
Correct |
3 ms |
1336 KB |
Output is correct |
5 |
Correct |
6 ms |
2004 KB |
Output is correct |
6 |
Correct |
12 ms |
2764 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
564 KB |
Output is correct |
9 |
Correct |
9 ms |
2388 KB |
Output is correct |
10 |
Correct |
9 ms |
2388 KB |
Output is correct |
11 |
Correct |
15 ms |
3156 KB |
Output is correct |
12 |
Correct |
16 ms |
3184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
572 KB |
Output is correct |
3 |
Correct |
2 ms |
724 KB |
Output is correct |
4 |
Correct |
3 ms |
1336 KB |
Output is correct |
5 |
Correct |
6 ms |
2004 KB |
Output is correct |
6 |
Correct |
12 ms |
2764 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
564 KB |
Output is correct |
9 |
Correct |
9 ms |
2388 KB |
Output is correct |
10 |
Correct |
9 ms |
2388 KB |
Output is correct |
11 |
Correct |
15 ms |
3156 KB |
Output is correct |
12 |
Correct |
16 ms |
3184 KB |
Output is correct |
13 |
Correct |
21 ms |
4660 KB |
Output is correct |
14 |
Correct |
24 ms |
8936 KB |
Output is correct |
15 |
Correct |
810 ms |
83480 KB |
Output is correct |
16 |
Correct |
2990 ms |
163632 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
6 ms |
4820 KB |
Output is correct |
19 |
Correct |
3 ms |
2516 KB |
Output is correct |
20 |
Correct |
1419 ms |
109876 KB |
Output is correct |
21 |
Correct |
1298 ms |
103360 KB |
Output is correct |
22 |
Correct |
2749 ms |
153488 KB |
Output is correct |
23 |
Correct |
2509 ms |
143888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
852 KB |
Output is correct |
6 |
Correct |
13 ms |
14164 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
18 ms |
3644 KB |
Output is correct |
12 |
Correct |
439 ms |
75400 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
7 ms |
1948 KB |
Output is correct |
17 |
Correct |
738 ms |
82780 KB |
Output is correct |
18 |
Runtime error |
1520 ms |
2097152 KB |
Execution killed with signal 9 |
19 |
Halted |
0 ms |
0 KB |
- |