This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf = 1e9;
const ll INF = 1e18;
vector<int> l[1510];
vector<int> s[1510];
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>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row(m, 0);
answer.push_back(row);
}
ll ret = 0;
int cnt[1510] = {};
priority_queue<pii> pq;
for(int i=0; i<n; i++) {
for(int j=0; j<k; j++) {
ret -= x[i][j];
answer[i][j] = -1;
}
cnt[i] = k;
pq.em(x[i][cnt[i]-1] + x[i][m - 1 - k + cnt[i]] , i);
}
int T = n/2 * k;
while(T--) {
int i = pq.top().se;
ret += pq.top().fi;
answer[i][cnt[i]-1]++;
answer[i][m - 1 - k + cnt[i]]++;
cnt[i]--;
pq.pop();
if(cnt[i]) pq.em(x[i][cnt[i]-1] + x[i][m - 1 - k + cnt[i]], i);
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(answer[i][j] == 1) l[i].eb(j);
else if(answer[i][j] == -1) s[i].eb(j);
answer[i][j] = -1;
}
}
for(int i=0; i<k; i++) {
vector<int> t;
for(int j=0; j<n; j++) t.eb(j);
sort(all(t), [&] (int a, int b) {
return l[a].size() < l[b].size();
});
for(int j=0; j<n/2; j++) {
answer[t.back()][l[t.back()].back()] = i;
l[t.back()].pop_back();
t.pop_back();
}
sort(all(t), [&] (int a, int b) {
return s[a].size() < s[b].size();
});
for(int j=0; j<n/2; j++) {
answer[t.back()][s[t.back()].back()] = i;
s[t.back()].pop_back();
t.pop_back();
}
}
allocate_tickets(answer);
return ret;
}
# | 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... |