이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (int i = s; i <= e; ++i)
#define rrep(i,s,e) for (int i = s; i >= e; --i)
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define len(a) (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
const int mx = 1e6;
map<vi,bool> mp;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k, r; cin >> n >> k >> r;
vi c[k];
int a[n][k], b[k][mx+1] = {};
rep (i,0,n-1) {
rep (j,0,k-1) {
cin >> a[i][j];
if (!b[j][a[i][j]]) {
b[j][a[i][j]] = 1;
c[j].pb(a[i][j]);
}
}
}
priority_queue<pair<int,vi>> pq;
int s = 0, sth = 1;
vi v;
rep (i,0,k-1) {
sort(all(c[i]), greater<int>());
s += c[i][0];
v.pb(0);
sth *= len(c[i]);
}
pq.push({s, v});
int x = 0, cnt = 0;
while (!pq.empty()) {
s = pq.top().fi;
v = pq.top().se;
pq.pop();
++cnt;
int dp[k+1][1<<k] = {};
dp[0][0] = 1;
rep (i,0,n-1) {
int cur = 0, suc = 1;
rep (j,0,k-1) {
if (a[i][j]==c[j][v[j]]) cur += (1<<j);
else if (a[i][j]>c[j][v[j]]) suc = 0;
}
if (suc) rrep (j,k-1,0) rep (mask,0,(1<<k)-1) dp[j+1][mask|cur] += dp[j][mask];
}
x += dp[k][(1<<k)-1];
if (x>=r) {
cout << s << "\n";
return 0;
}
rep (i,0,k-1) {
++v[i];
if (v[i]<len(c[i]) && !mp[v]) {
mp[v] = 1;
pq.push({s + c[i][v[i]] - c[i][v[i]-1], v});
}
--v[i];
}
}
assert(cnt==sth);
cout << "yey\n";
return 0;
}
# | 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... |