| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 863779 | Trisanu_Das | Olympiads (BOI19_olympiads) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
int n, m, k, sMin, sMax;
vector<pair<int, vector<int> > > C;
multiset<int> S;
bool f(int t, int j, int s, vector<int> x){
int xx, sNew, sNewMax;
vector<int> xNew;
if (t == 0) {
S.insert(s);
if (S.size() > c) {
S.erase(S.begin());
sMin = *S.begin();
if (sMin == sMax) return true;
}
}
else {
for (int i = j; i < n; i++) {
sNewMax = 0;
sNew = 0;
mNew = vector<int>(k);
for (int l = 0; l < k; l++) {
x = max(x[l], C[i].second[l]);
sNew += xx;
xNew[l] = xx;
sNewMax += max(xx, C[i].first);
}
if (sNewMax < sMin) return false;
if (f(t - 1, i + 1, sNew, xNew)) return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
int x, xMax;
vector<int> M;
cin >> n >> k >> c;
C = vector<pair<int, vector<int> > >(n, {0, vector<int>(k)});
M = vector<int>(k);
for (int i = 0; i < n; i++) {
xMax = 0;
for (int j = 0; j < k; j++) {
cin >> x;
C[i].second[j] = x;
xMax = max(xMax, x);
M[j] = max(M[j], x);
}
C[i].first = xMax;
}
sort(C.begin(), C.end(), greater<pair<int, vi>>());
sMin = 0;
sMax = 0;
for (int i = 0; i < k; i++) sMax += M[i];
f(k, 0, 0, vi(k));
cout << sMin << '\n';
}