#include "tickets.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppp=pair<pii,pii>;
using ppi=pair<int,ppp>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
_print(H);
if(sizeof...(T)) cerr<<",";
else cerr<<"\"]";
dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n=x.size(),m=x[0].size();
vector<vector<int>> t(n,vector<int>(m,-1));
priority_queue<ppi,vector<ppi>,greater<ppi>> pq;
ll ans=0;
for(int i=0;i<n;i++) {
for(int j=m-1,cnt=0;cnt<k;cnt++,j--) {
ans+=x[i][j]; t[i][j]=1;
int temp=x[i][j]+x[i][k-cnt-1];
pq.push({temp,{{i,j},{i,k-cnt-1}}});
}
}
int cntt=k*n/2;
vector<tuple<int,int,int>> ar0,ar1; //i,j,type
while(cntt--) {
ppi cur=pq.top(); pq.pop();
ans-=cur.first;
pii p1=cur.second.first; pii p2=cur.second.second;
t[p1.first][p1.second]=-1;
t[p2.first][p2.second]=0;
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(t[i][j]==0) ar0.push_back(tie(i,j,t[i][j]));
else if(t[i][j]==1) ar1.push_back(tie(i,j,t[i][j]));
}
}
set<int> unused[n];
for(int i=0;i<n;i++) {
for(int j=0;j<k;j++) unused[i].insert(j);
}
vector<int> cnt(k,0);
vector<vector<int>> s(n,vector<int>(m,-1));
sort(all(ar0),[&](const tuple<int,int,int> &l,const tuple<int,int,int> &r) {
return get<1>(l)<get<1>(r);
});
sort(all(ar1),[&](const tuple<int,int,int> &l,const tuple<int,int,int> &r) {
return get<1>(l)<get<1>(r);
});
for(auto e:ar1) {
int i,j,type; tie(i,j,type)=e;
if(!type) assert(false);
int select=-1;
//debug("idx",i);
//for(auto f:unused[i]) debug(f);
for(auto f:unused[i]) {
if(cnt[f]<n/2) {
select=f; break;
}
}
assert(select!=-1);
cnt[select]++; s[i][j]=select; unused[i].erase(select);
}
for(auto e:ar0) {
int i,j,type; tie(i,j,type)=e;
if(type) assert(false);
int select=-1;
for(auto f:unused[i]) {
if(cnt[f]<n) {
select=f; break;
}
}
assert(select!=-1);
cnt[select]++; s[i][j]=select; unused[i].erase(select);
}
allocate_tickets(s);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
2 ms |
876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
2 ms |
492 KB |
Output is correct |
5 |
Correct |
28 ms |
2796 KB |
Output is correct |
6 |
Correct |
652 ms |
60624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
4 ms |
748 KB |
Output is correct |
5 |
Correct |
45 ms |
5472 KB |
Output is correct |
6 |
Correct |
1271 ms |
128324 KB |
Output is correct |
7 |
Execution timed out |
3061 ms |
157700 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
5 ms |
972 KB |
Output is correct |
5 |
Correct |
112 ms |
10076 KB |
Output is correct |
6 |
Correct |
38 ms |
1840 KB |
Output is correct |
7 |
Correct |
11 ms |
2088 KB |
Output is correct |
8 |
Execution timed out |
3084 ms |
233780 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
620 KB |
Output is correct |
3 |
Correct |
3 ms |
620 KB |
Output is correct |
4 |
Correct |
3 ms |
620 KB |
Output is correct |
5 |
Correct |
4 ms |
748 KB |
Output is correct |
6 |
Correct |
4 ms |
876 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
508 KB |
Output is correct |
9 |
Correct |
4 ms |
748 KB |
Output is correct |
10 |
Correct |
4 ms |
900 KB |
Output is correct |
11 |
Correct |
5 ms |
860 KB |
Output is correct |
12 |
Correct |
6 ms |
972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
620 KB |
Output is correct |
3 |
Correct |
3 ms |
620 KB |
Output is correct |
4 |
Correct |
3 ms |
620 KB |
Output is correct |
5 |
Correct |
4 ms |
748 KB |
Output is correct |
6 |
Correct |
4 ms |
876 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
508 KB |
Output is correct |
9 |
Correct |
4 ms |
748 KB |
Output is correct |
10 |
Correct |
4 ms |
900 KB |
Output is correct |
11 |
Correct |
5 ms |
860 KB |
Output is correct |
12 |
Correct |
6 ms |
972 KB |
Output is correct |
13 |
Correct |
31 ms |
3692 KB |
Output is correct |
14 |
Correct |
32 ms |
3820 KB |
Output is correct |
15 |
Correct |
55 ms |
6496 KB |
Output is correct |
16 |
Correct |
123 ms |
9948 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
3 ms |
748 KB |
Output is correct |
19 |
Correct |
2 ms |
620 KB |
Output is correct |
20 |
Correct |
60 ms |
6752 KB |
Output is correct |
21 |
Correct |
64 ms |
7136 KB |
Output is correct |
22 |
Correct |
88 ms |
8924 KB |
Output is correct |
23 |
Correct |
100 ms |
8924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
2 ms |
876 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
2 ms |
492 KB |
Output is correct |
11 |
Correct |
28 ms |
2796 KB |
Output is correct |
12 |
Correct |
652 ms |
60624 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
4 ms |
748 KB |
Output is correct |
17 |
Correct |
45 ms |
5472 KB |
Output is correct |
18 |
Correct |
1271 ms |
128324 KB |
Output is correct |
19 |
Execution timed out |
3061 ms |
157700 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |