#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define pip pair<int, pii>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
void make_tickets(vector<vector<int>> nids, vector<vector<int>> pids, int k, int m){
int n = SZ(nids);
vector<vector<int>> ans(n);
REP(i, n){
ans[i] = vector<int> (m);
REP(j, m) ans[i][j] = -1;
}
REP(t, k){
vector<bool> tmp(n);
int cnt = 0;
REP(i, n) {
if (cnt >= n/2) break;
if (SZ(nids[i]) == 0){
ans[i][pids[i].back()] = t;
pids[i].pop_back();
cnt++;
tmp[i] = 1;
}
}
REP(i, n){
if (cnt >= n/2) break;
if (SZ(pids[i]) > 0 && !tmp[i]){
ans[i][pids[i].back()] = t;
pids[i].pop_back();
cnt++;
tmp[i] = 1;
}
}
REP(i, n){
if (!tmp[i]){
ans[i][nids[i].back()] = t;
nids[i].pop_back();
}
}
}
allocate_tickets(ans);
}
const ll maxn = 1505;
static ll dp[maxn][maxn];
static int pre[maxn][maxn];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> tick(n); // -1 if neg, +1 if pos, 0 if nothing
REP(i, n) tick[i] = vector<int> (m);
ll sm = 0;
priority_queue<pip> pq;
REP(i, n){
REP(j, k){
sm -= x[i][j];
tick[i][j] = -1;
}
pq.push({x[i][k-1 + (m-k)] + x[i][k-1], {i, k-1}});
}
REP(t, n/2*k){
pip tp = pq.top(); pq.pop();
sm += tp.f;
tick[tp.s.f][tp.s.s] = 0;
tick[tp.s.f][tp.s.s+(m-k)] = 1;
if (tp.s.s > 0){
pq.push({x[tp.s.f][tp.s.s-1 + (m-k)] + x[tp.s.f][tp.s.s-1], {tp.s.f, tp.s.s-1}});
}
}
vector<vector<int>> poo1(n), poo2(n);
REP(i, n){
vector<int> t1, t2;
REP(j, m){
if (tick[i][j] == -1) t1.pb(j);
if (tick[i][j] == 1) t2.pb(j);
}
poo1[i] = t1; poo2[i] = t2;
}
make_tickets(poo1, poo2, k, m);
return sm;
}
/*
2 3 2
0 2 5
1 1 3
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |