| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 417379 | abdzag | 카니발 티켓 (IOI20_tickets) | C++17 | 0 ms | 0 KiB |
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<bits/stdc++.h>
//#include"tickets.h"
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const long long inf = 1e15;
using namespace std;
vector<bool> visited(1e6);
vector<vector<ll>> g;
vector<ll> v;
//void allocate_tickets(vector<vector<int>> answer) {
// trav(vec, answer) {
// trav(a, vec)cout << a << " ";
// cout << endl;
// }
//}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
set<pair<ll, pair<ll, ll>>> v;
ll n = x.size();
ll m = x[0].size();
vector<vector<int>> answer(n, vector<int>(m, -1));
rep(i, 0, n) {
rep(j, 0, m)v.emplace(x[i][j], make_pair(i, j));
}
ll ans = 0;
vector<ll> counter(n);
ll cur = 0;
auto it = v.begin();
set<pair<ll, ll>> s1;
set<pair<ll, ll>> s2;
while(cur<k*n/2) {
auto it = v.begin();
ans -= it->first;
s1.emplace(it->second.first, it->second.second);
v.erase(it);
cur++;
}
while (cur < k*n) {
auto it = v.begin();
ans += it->first;
s2.emplace(it->second.first, it->second.second);
v.erase(it);
cur++;
}
rep(i, 0, k) {
ll curminus = 0;
rep(j, 0, n) {
auto it = s1.lower_bound(make_pair(j, -inf));
if (it != s1.end() && it->first == j&&curminus<n/2) {
curminus++;
answer[it->first][it->second] = i;
s1.erase(it);
}
else {
it = s2.lower_bound(make_pair(j, -inf));
answer[it->first][it->second] = i;
s2.erase(it);
}
}
}
allocate_tickets(answer);
return ans;
}
//
//int main() {
// ll n, m, k;
// cin >> n >> m >> k;
// vector<vector<int>> x(n, vector<int>(m));
// rep(i, 0, n)rep(j, 0, m)cin >> x[i][j];
// cout << find_maximum(k, x);
//}