| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 124910 |
2019-07-04T06:34:09 Z |
박상수(#3055) |
Olympiads (BOI19_olympiads) |
C++14 |
|
7 ms |
1272 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;
int N, K, C;
int A[510][10];
ll Bind(int p[], int rk = K) {
ll res = 0;
for(int i=1;i<=rk;i++) res = (res << 10 | p[i]);
return res;
}
void Unbind(ll x, int p[]) {
for(int i=K;i;i--) p[i] = (x & 1023), x >>= 10;
}
ll CR[2020][10];
int ord[10][510], iv[10][510];
ll calc(int temp[]) {
ll ans = 0;
for(int a=1;a<=K;a++) ans += A[ord[a][temp[a]]][a];
return ans;
}
int main() {
rep(i, 2020) {
CR[i][0] = 1;
for(int j=1;j<=i && j<10;j++) {
CR[i][j] = CR[i-1][j-1] + CR[i-1][j];
}
}
scanf("%d%d%d", &N, &K, &C);
for(int i=1;i<=N;i++) for(int j=1;j<=K;j++) scanf("%d", A[i] + j);
for(int i=1;i<=K;i++) {
for(int j=1;j<=N;j++) ord[i][j] = j;
sort(ord[i]+1, ord[i]+1+N, [&](int x, int y) { return A[x][i] > A[y][i]; });
for(int j=1;j<=N;j++) iv[i][ord[i][j]] = j;
}
int temp[10];
for(int i=1;i<=K;i++) temp[i] = 1;
ll ST = Bind(temp);
priority_queue <pll> pq;
pq.push(pll(calc(temp), ST));
set <ll> Sx2; Sx2.insert(ST);
while(!pq.empty()) {
pll tt = pq.top(); pq.pop();
ll me = tt.Se;
int t[10];
Unbind(me, t);
int rt[10], tp = 0;
for(int a=1;a<=K;a++) rt[tp++] = ord[a][t[a]];
sort(rt, rt+tp); tp = (int)(unique(rt, rt+tp) - rt);
bitset <520> tv; tv.reset();
for(int a=1;a<=K;a++) for(int b=1;b<t[a];b++) tv[ord[a][b]] = 1;
vector <int> w;
for(int a=1;a<=K;a++) if(tv[ord[a][t[a]]]) w.pb(a);
int cn = N - tv.count();
if(cn < K) continue;
if(szz(w) == 0) {
ll cnt = CR[cn - tp][K - tp];
if (cnt >= C) {
printf("%lld\n", tt.Fi);
break;
}
C -= cnt;
}
auto upd = [&]() {
ll v = Bind(t);
if(Sx2.find(v) == Sx2.end()) {
Sx2.insert(v);
pq.push(pll(calc(t), v));
}
};
if(szz(w)) {
for(int e : w) while(t[e] <= N && tv[t[e]] == 1) t[e]++;
int can = 1;
for(int a=1;a<=K;a++) if(t[a] > N) can = 0;
if(can) upd();
}
else {
for(int a=1;a<=K;a++) if(t[a] != N) {
++t[a];
upd();
--t[a];
}
}
}
return 0;
}
Compilation message
olympiads.cpp: In function 'int main()':
olympiads.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &K, &C);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:59:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=N;i++) for(int j=1;j<=K;j++) scanf("%d", A[i] + j);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1272 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
3 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
