#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define pb push_back
#define eb emplace_back
#define SZ(a) ((int)a.size())
#define REP(i,n) for(int i=0;i<(n);i++)
const int maxn = 1505;
int n,m,k;
std::vector<std::vector<int>> ans;
vector<int> idx[maxn]; //pos
vector<int> idx2[maxn]; //neg
set<pii> st;
void distribute(){//distrubute all tickets in idx[] to k rounds, each round with n/2 distinct color
REP(i,n){
st.insert(MP(SZ(idx[i]),i));
}
REP(i,k){
auto it = prev(st.end());
vector<int> clr={};
bool vis[maxn]={0};
REP(j,n/2){
clr.pb(it->S);
--it;
}
for(int j:clr){
vis[j] = 1;
ans[j][idx[j].back()] = i;
st.erase(MP(SZ(idx[j]),j));
idx[j].pop_back();
st.insert(MP(SZ(idx[j]),j));
}
REP(j,n) if(!vis[j]){
ans[j][idx2[j].back()] = i;
idx2[j].pop_back();
}
}
}
// bool check(vector<int> v){
// assert(SZ(v)==n);
// sort(ALL(v));
// reverse(ALL(v));
// int sum = 0;
// REP(i,SZ(v)){
// sum+=v[i];
// if(sum>(i+1) * k) return 0;
// }
// return 1;
// }
ll val[maxn][maxn];
priority_queue<pll> pq;
int iter[maxn];
long long find_maximum(int _k, std::vector<std::vector<int>> a) {
n = a.size();
m = a[0].size();
k=_k;
ans.resize(n);
REP(i,n) ans[i].resize(m);
REP(i,n) REP(j,m) ans[i][j]=-1;
ll ret = 0;
REP(i,n){
REP(j,k) ret -= a[i][j];
REP(j,k){
val[i][j] = a[i][m-1-j] + a[i][k-1-j];
}
}
REP(i,n) iter[i] = 0;
REP(i,n) pq.push(MP(val[i][0],i));
REP(T,n*k/2){
auto cur = pq.top();
pq.pop();
int idx = cur.S;
ret += cur.F;
iter[idx]++;
if(iter[idx]==k) continue;
pq.push(MP(val[idx][iter[idx]],idx));
}
// REP(i,n) cout<<iter[i]<<" \n"[i==n-1];
{
REP(i,n){
REP(j,k-iter[i])
idx2[i].pb(j);
REP(j,iter[i])
idx[i].pb(m-1-j);
}
// REP(i,n) {
// for(int j:idx[i]) cout<<j<<' ';
// cout<<'\n';
// }
distribute();
}
allocate_tickets(ans);
return ret;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
768 KB |
Output is correct |
5 |
Correct |
1 ms |
1664 KB |
Output is correct |
6 |
Correct |
6 ms |
6912 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 |
3 ms |
896 KB |
Output is correct |
5 |
Correct |
31 ms |
3704 KB |
Output is correct |
6 |
Correct |
743 ms |
57720 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 |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
896 KB |
Output is correct |
5 |
Correct |
32 ms |
4344 KB |
Output is correct |
6 |
Correct |
827 ms |
73592 KB |
Output is correct |
7 |
Correct |
891 ms |
79608 KB |
Output is correct |
8 |
Correct |
5 ms |
1152 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 |
416 KB |
Output is correct |
12 |
Correct |
9 ms |
1792 KB |
Output is correct |
13 |
Correct |
28 ms |
4864 KB |
Output is correct |
14 |
Correct |
28 ms |
3576 KB |
Output is correct |
15 |
Correct |
949 ms |
81368 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 |
4 ms |
896 KB |
Output is correct |
5 |
Correct |
47 ms |
5112 KB |
Output is correct |
6 |
Correct |
8 ms |
896 KB |
Output is correct |
7 |
Correct |
15 ms |
7296 KB |
Output is correct |
8 |
Correct |
1269 ms |
84492 KB |
Output is correct |
9 |
Correct |
1183 ms |
80632 KB |
Output is correct |
10 |
Correct |
1177 ms |
78976 KB |
Output is correct |
11 |
Correct |
1256 ms |
84144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
896 KB |
Output is correct |
3 |
Correct |
3 ms |
896 KB |
Output is correct |
4 |
Correct |
3 ms |
896 KB |
Output is correct |
5 |
Correct |
3 ms |
896 KB |
Output is correct |
6 |
Correct |
4 ms |
896 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
3 ms |
896 KB |
Output is correct |
10 |
Correct |
4 ms |
896 KB |
Output is correct |
11 |
Correct |
3 ms |
896 KB |
Output is correct |
12 |
Correct |
4 ms |
896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
896 KB |
Output is correct |
3 |
Correct |
3 ms |
896 KB |
Output is correct |
4 |
Correct |
3 ms |
896 KB |
Output is correct |
5 |
Correct |
3 ms |
896 KB |
Output is correct |
6 |
Correct |
4 ms |
896 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
3 ms |
896 KB |
Output is correct |
10 |
Correct |
4 ms |
896 KB |
Output is correct |
11 |
Correct |
3 ms |
896 KB |
Output is correct |
12 |
Correct |
4 ms |
896 KB |
Output is correct |
13 |
Correct |
32 ms |
3704 KB |
Output is correct |
14 |
Correct |
32 ms |
3704 KB |
Output is correct |
15 |
Correct |
39 ms |
4416 KB |
Output is correct |
16 |
Correct |
47 ms |
5112 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
4 ms |
1792 KB |
Output is correct |
19 |
Correct |
2 ms |
1792 KB |
Output is correct |
20 |
Correct |
36 ms |
4472 KB |
Output is correct |
21 |
Correct |
40 ms |
4344 KB |
Output is correct |
22 |
Correct |
40 ms |
4856 KB |
Output is correct |
23 |
Correct |
45 ms |
4728 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 |
1 ms |
768 KB |
Output is correct |
5 |
Correct |
1 ms |
1664 KB |
Output is correct |
6 |
Correct |
6 ms |
6912 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 |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
896 KB |
Output is correct |
11 |
Correct |
31 ms |
3704 KB |
Output is correct |
12 |
Correct |
743 ms |
57720 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
0 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
896 KB |
Output is correct |
17 |
Correct |
32 ms |
4344 KB |
Output is correct |
18 |
Correct |
827 ms |
73592 KB |
Output is correct |
19 |
Correct |
891 ms |
79608 KB |
Output is correct |
20 |
Correct |
5 ms |
1152 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 |
416 KB |
Output is correct |
24 |
Correct |
9 ms |
1792 KB |
Output is correct |
25 |
Correct |
28 ms |
4864 KB |
Output is correct |
26 |
Correct |
28 ms |
3576 KB |
Output is correct |
27 |
Correct |
949 ms |
81368 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 |
4 ms |
896 KB |
Output is correct |
32 |
Correct |
47 ms |
5112 KB |
Output is correct |
33 |
Correct |
8 ms |
896 KB |
Output is correct |
34 |
Correct |
15 ms |
7296 KB |
Output is correct |
35 |
Correct |
1269 ms |
84492 KB |
Output is correct |
36 |
Correct |
1183 ms |
80632 KB |
Output is correct |
37 |
Correct |
1177 ms |
78976 KB |
Output is correct |
38 |
Correct |
1256 ms |
84144 KB |
Output is correct |
39 |
Correct |
1 ms |
384 KB |
Output is correct |
40 |
Correct |
3 ms |
896 KB |
Output is correct |
41 |
Correct |
3 ms |
896 KB |
Output is correct |
42 |
Correct |
3 ms |
896 KB |
Output is correct |
43 |
Correct |
3 ms |
896 KB |
Output is correct |
44 |
Correct |
4 ms |
896 KB |
Output is correct |
45 |
Correct |
1 ms |
512 KB |
Output is correct |
46 |
Correct |
1 ms |
768 KB |
Output is correct |
47 |
Correct |
3 ms |
896 KB |
Output is correct |
48 |
Correct |
4 ms |
896 KB |
Output is correct |
49 |
Correct |
3 ms |
896 KB |
Output is correct |
50 |
Correct |
4 ms |
896 KB |
Output is correct |
51 |
Correct |
32 ms |
3704 KB |
Output is correct |
52 |
Correct |
32 ms |
3704 KB |
Output is correct |
53 |
Correct |
39 ms |
4416 KB |
Output is correct |
54 |
Correct |
47 ms |
5112 KB |
Output is correct |
55 |
Correct |
2 ms |
512 KB |
Output is correct |
56 |
Correct |
4 ms |
1792 KB |
Output is correct |
57 |
Correct |
2 ms |
1792 KB |
Output is correct |
58 |
Correct |
36 ms |
4472 KB |
Output is correct |
59 |
Correct |
40 ms |
4344 KB |
Output is correct |
60 |
Correct |
40 ms |
4856 KB |
Output is correct |
61 |
Correct |
45 ms |
4728 KB |
Output is correct |
62 |
Correct |
87 ms |
8184 KB |
Output is correct |
63 |
Correct |
99 ms |
8184 KB |
Output is correct |
64 |
Correct |
128 ms |
11640 KB |
Output is correct |
65 |
Correct |
437 ms |
34168 KB |
Output is correct |
66 |
Correct |
538 ms |
40824 KB |
Output is correct |
67 |
Correct |
14 ms |
7296 KB |
Output is correct |
68 |
Correct |
7 ms |
896 KB |
Output is correct |
69 |
Correct |
752 ms |
57976 KB |
Output is correct |
70 |
Correct |
973 ms |
73464 KB |
Output is correct |
71 |
Correct |
1274 ms |
84216 KB |
Output is correct |
72 |
Correct |
1081 ms |
82168 KB |
Output is correct |
73 |
Correct |
1193 ms |
81232 KB |
Output is correct |
74 |
Correct |
835 ms |
72568 KB |
Output is correct |
75 |
Correct |
978 ms |
71800 KB |
Output is correct |