# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
240318 | karma | Olympiads (BOI19_olympiads) | C++14 | 1707 ms | 262148 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb emplace_back
#define ll long long
#define fi first
#define se second
#define mp make_pair
//#define int int64_t
using namespace std;
const int N = int(5e2) + 7;
const int K = 7;
typedef pair<int, int> pii;
int n, k, c, s[N][K], value[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Team {
vector<int> id;
int cost;
Team() {};
Team(vector<int> id, int cost): id(id), cost(cost) {}
bool operator <(const Team& other) const& {
return cost < other.cost;
}
};
priority_queue<Team> pq;
unordered_map<int, bool> vis;
int cost[K][K], mask, ncost, val, has[N];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define Task "test"
if(fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
cin >> n >> k >> c;
for(int i = 1; i <= n; ++i) {
value[i] = uniform_int_distribution<int>(10000000, 100000000)(rng);
for(int j = 0; j < k; ++j) cin >> s[i][j];
}
for(int j = 0; j < k; ++j) s[0][j] = -1;
vector<int> tmp; ncost = mask = 0;
for(int mx, j = 0; j < k; ++j) {
mx = val = 0;
for(int i = 1; i <= n; ++i) {
if(has[i]) {val = max(val, s[i][j]); continue;}
if(s[mx][j] < s[i][j]) mx = i;
}
tmp.pb(mx); ncost += max(val, s[mx][j]), has[mx] = 1;
}
for(int x: tmp) {
mask ^= value[x];
has[x] = 0;
}
vis[mask] = 1;
pq.emplace(tmp, ncost);
for(Team top; pq.size() && c > 0;) {
top = pq.top(); pq.pop();
if(--c == 0) return cout << top.cost, 0;
mask = 0;
for(int x = 0; x < k; ++x) { /// cost[x][i] neu bo id[x]
for(int i = 0; i < k; ++i) {
cost[x][i] = 0;
for(int j = 0; j < k; ++j)
if(j != x) cost[x][i] = max(cost[x][i], s[top.id[j]][i]);
}
has[top.id[x]] = 1;
mask ^= value[top.id[x]];
}
for(int i = 1; i <= n; ++i) {
if(has[i]) {has[i] = 0; continue;}
for(int j = 0; j < k; ++j) {
val = top.id[j]; /// change j
mask ^= value[val] ^ value[i];
if(!vis[mask]) {
vis[mask] = 1; ncost = 0; top.id[j] = i;
for(int x = 0; x < k; ++x) ncost += max(cost[j][x], s[i][x]);
pq.emplace(top.id, ncost); top.id[j] = val;
}
mask ^= value[val] ^ value[i];
}
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |