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>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define Inf INT32_MAX
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
int n, k, c, sMin, sMax;
vector<pair<int, vi>> C;
multiset<int> S;
bool f(int t, int j, int s, vi m) {
int x, sNew, sNewMax;
vi mNew;
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 = vi(k);
for (int l = 0; l < k; l++) {
x = max(m[l], C[i].second[l]);
sNew += x;
mNew[l] = x;
sNewMax += max(x, C[i].first);
}
if (sNewMax < sMin) return false;
if (f(t - 1, i + 1, sNew, mNew)) return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
int x, xMax;
vi M;
cin >> n >> k >> c;
C = vector<pair<int, vi>>(n, {0, vi(k)});
M = vi(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 << endl;
return 0;
}
Compilation message (stderr)
olympiads.cpp: In function 'bool f(int, int, int, vi)':
olympiads.cpp:24:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (S.size() > c) {
~~~~~~~~~^~~
# | 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... |