#include "tickets.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll NN = 1505;
ll n, m, k, has, B[NN], K[NN], a[NN][NN];
std::vector<std::vector<int>> answer;
std::vector<std::vector<int>> x;
vector<ll> bes[NN], kec[NN];
void sub1()
{
vector<ll> tmp;
for(ll i = 0; i < n; i++)
{
answer[i][0] = 0;
tmp.pb(x[i][0]);
}
sort(tmp.begin(), tmp.end());
for(ll i = 0; i < n; i++)
if(i < (n / 2))
has -= tmp[i];
else
has += tmp[i];
}
void sub4()
{
vector<pair<ll, pair<ll, ll> > >tmp;
for(ll i = 0; i < n; i++)
for(ll j = 0; j < m; j++)
tmp.pb(mp(x[i][j], mp(i, j)));
sort(tmp.begin(), tmp.end());
for(ll i = 0; i < (n * m); i++)
if(i < ((n * m) / 2))
has -= tmp[i].fi;
else
{
a[tmp[i].se.fi][tmp[i].se.se] = 1;
has += tmp[i].fi;
}
for(ll i = 0; i < n; i++)
{
for(ll j = 0; j < m; j++)
{
if(a[i][j])
{
B[i]++;
bes[i].pb(j);
}
else
{
K[i]++;
kec[i].pb(j);
}
}
}
for(ll i = 0; i < k; i++)
{
vector<pair<ll, ll> > z;
for(ll j = 0; j < n; j++)
z.pb(mp(B[j], j));
sort(z.begin(), z.end());
for(ll j = 0; j < n; j++)
{
ll idx = z[j].se;
// continue;
if(j < (n / 2))
{
ll temp = kec[idx].back();
kec[idx].pop_back();
// cout << idx << " " << temp << "K_\n";
answer[idx][temp] = i;
}
else
{
B[idx]--;
ll temp = bes[idx].back();
bes[idx].pop_back();
// cout << idx << " " << temp << "B_\n";
answer[idx][temp] = i;
}
}
}
}
void sub3()
{
for(ll i = 0; i < n; i++)
{
for(ll j = 0; j < m; j++)
{
if(x[i][j])
{
B[i]++;
bes[i].pb(j);
}
else
{
K[i]++;
kec[i].pb(j);
}
}
}
for(ll i = 0; i < k; i++)
{
vector<pair<ll, ll> > z;
for(ll j = 0; j < n; j++)
z.pb(mp(B[j], j));
sort(z.begin(), z.end());
for(ll j = 0; j < n; j++)
{
ll idx = z[j].se;
// continue;
if(j < (n / 2))
{
if(kec[idx].empty())
{
B[idx]--;
ll temp = bes[idx].back();
bes[idx].pop_back();
has += x[idx][temp];
answer[idx][temp] = i;
}
else
{
ll temp = kec[idx].back();
kec[idx].pop_back();
answer[idx][temp] = i;
}
}
else
{
if(bes[idx].empty())
{
ll temp = kec[idx].back();
kec[idx].pop_back();
answer[idx][temp] = i;
}
else
{
B[idx]--;
ll temp = bes[idx].back();
bes[idx].pop_back();
has += x[idx][temp];
answer[idx][temp] = i;
}
}
}
}
}
ll d[NN][NN];
ll b[NN][NN];
ll depe(ll pos, ll sisa)
{
if(pos == n && sisa == 0)
return 0;
if(sisa < 0 || pos == n)
return -1e18;
if(!b[pos][sisa])
{
b[pos][sisa] = 1;
if(depe(pos + 1, sisa) - x[pos][K[pos]] < depe(pos + 1, sisa - 1) + x[pos][B[pos]])
d[pos][sisa] = depe(pos + 1, sisa - 1) + x[pos][B[pos]];
else
d[pos][sisa] = depe(pos + 1, sisa) - x[pos][K[pos]];
}
return d[pos][sisa];
}
void bt(ll pos, ll sisa)
{
if(pos == n)
return ;
if(depe(pos + 1, sisa) - x[pos][K[pos]] < depe(pos + 1, sisa - 1) + x[pos][B[pos]])
{
answer[pos][B[pos]] = 0;
bt(pos + 1, sisa - 1);
}
else
{
answer[pos][K[pos]] = 0;
bt(pos + 1, sisa);
}
}
void sub2()
{
for(ll i = 0; i < n; i++)
{
vector<pair<ll, ll> > tmp;
for(ll j = 0; j < m; j++)
tmp.pb(mp(x[i][j], j));
sort(tmp.begin(), tmp.end());
K[i] = tmp[0].se;
B[i] = tmp[m - 1].se;
// cout << K[i] << " " << B[i] << "_\n";
}
has = depe(0, n / 2);
bt(0, n / 2);
}
long long find_maximum(int tk, std::vector<std::vector<int>> tx) {
k = tk;
x = tx;
n = x.size();
m = x[0].size();
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);
}
if(m == 1)
sub1();
else
if(k == 1)
sub2();
else
if(k == m)
sub4();
else
sub3();
allocate_tickets(answer);
return has;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
544 KB |
Output is correct |
6 |
Correct |
3 ms |
896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
1280 KB |
Output is correct |
5 |
Correct |
47 ms |
5880 KB |
Output is correct |
6 |
Correct |
906 ms |
85780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
640 KB |
Output is correct |
5 |
Correct |
36 ms |
4092 KB |
Output is correct |
6 |
Correct |
854 ms |
85552 KB |
Output is correct |
7 |
Correct |
796 ms |
85880 KB |
Output is correct |
8 |
Correct |
7 ms |
1408 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
8 ms |
1280 KB |
Output is correct |
13 |
Correct |
24 ms |
3328 KB |
Output is correct |
14 |
Correct |
31 ms |
3320 KB |
Output is correct |
15 |
Correct |
837 ms |
88340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
7 ms |
1088 KB |
Output is correct |
5 |
Correct |
67 ms |
6764 KB |
Output is correct |
6 |
Correct |
10 ms |
1280 KB |
Output is correct |
7 |
Correct |
20 ms |
7548 KB |
Output is correct |
8 |
Correct |
1404 ms |
134628 KB |
Output is correct |
9 |
Correct |
1325 ms |
132172 KB |
Output is correct |
10 |
Correct |
1367 ms |
132220 KB |
Output is correct |
11 |
Correct |
1400 ms |
134500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
1280 KB |
Output is correct |
3 |
Incorrect |
3 ms |
616 KB |
Contestant returned 6290855666 but the tickets gives a total value of 384402666338 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
1280 KB |
Output is correct |
3 |
Incorrect |
3 ms |
616 KB |
Contestant returned 6290855666 but the tickets gives a total value of 384402666338 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
544 KB |
Output is correct |
6 |
Correct |
3 ms |
896 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
1280 KB |
Output is correct |
11 |
Correct |
47 ms |
5880 KB |
Output is correct |
12 |
Correct |
906 ms |
85780 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
640 KB |
Output is correct |
17 |
Correct |
36 ms |
4092 KB |
Output is correct |
18 |
Correct |
854 ms |
85552 KB |
Output is correct |
19 |
Correct |
796 ms |
85880 KB |
Output is correct |
20 |
Correct |
7 ms |
1408 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
8 ms |
1280 KB |
Output is correct |
25 |
Correct |
24 ms |
3328 KB |
Output is correct |
26 |
Correct |
31 ms |
3320 KB |
Output is correct |
27 |
Correct |
837 ms |
88340 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
0 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
7 ms |
1088 KB |
Output is correct |
32 |
Correct |
67 ms |
6764 KB |
Output is correct |
33 |
Correct |
10 ms |
1280 KB |
Output is correct |
34 |
Correct |
20 ms |
7548 KB |
Output is correct |
35 |
Correct |
1404 ms |
134628 KB |
Output is correct |
36 |
Correct |
1325 ms |
132172 KB |
Output is correct |
37 |
Correct |
1367 ms |
132220 KB |
Output is correct |
38 |
Correct |
1400 ms |
134500 KB |
Output is correct |
39 |
Correct |
1 ms |
384 KB |
Output is correct |
40 |
Correct |
4 ms |
1280 KB |
Output is correct |
41 |
Incorrect |
3 ms |
616 KB |
Contestant returned 6290855666 but the tickets gives a total value of 384402666338 |
42 |
Halted |
0 ms |
0 KB |
- |