| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 134211 | dvdg6566 | Olympiads (BOI19_olympiads) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define ALL(X) X.begin(),X.end()
#define SZ(X) (int)X.size()
#define MAXN 1001000
#define INF 1e9
int N,K,C;
int mem[510][10];
vi cur;
set<pi> st;
vi out;
int cntr;
int lefts[2010][4];
int rights[2010][4];
bitset<21000000> safe;
int ind;
map<ll,int> M;
ll hh(){
ll ans=0;ll mult = 1;
while(SZ(cur)){
ans += mult * cur.back();
cur.pop_back();
mult *= N;
}
return ans;
}
void rec2(int stt, int en){
if (SZ(cur) == en-stt+1){
++cntr;
int ans = 0;
// for (auto i : cur)cout<<i<<' ';cout<<'\n';
for (int i=stt;i<en;++i){
int t=0;
for (int j=1;j<SZ(cur);++j)t=max(t,mem[cur[j]][i]);
ans += t;
}
// cout<<ans<<'\n';
st.insert(mp(ans,cntr));
if (SZ(st) > C)st.erase(st.begin());
return;
}
int lst = cur.back()+1;
for (int i=lst;i<=N;++i){
cur.pb(i);
rec2(stt,en);
cur.pop_back();
}
}
void rec3(int stt, int en, bool flag){
if (SZ(cur) == en-stt+1){
++cntr;
// cout<<cntr<<' '<<safe[cntr]<<'\n';
if (safe[cntr] == 0)return;
int ans = 0;
for (int i=1;i<SZ(cur);++i){
if (flag)lefts[ind][i-1] = cur[i];
else rights[ind][i-1] = cur[i];
}
++ind;
return;
}
int lst = cur.back()+1;
for (int i=lst;i<=N;++i){
cur.pb(i);
rec3(stt,en,flag);
cur.pop_back();
}
}
int main(){
// freopen("in.txt","r",stdin);
cin>>N>>K>>C;
for (int i=1;i<=N;++i)for (int j=0;j<K;++j)cin>>mem[i][j];
cur.pb(0);
rec2(0,K/2);
for (auto i :st)safe[i.s]=1;
cntr=0;
rec3(0,K/2,1);
cntr=ind=0;
while(SZ(st))st.erase(st.begin());
safe.reset();
// cout<<K/2<<' '<<K<<'\n';
rec2(K/2,K);
// for (auto i : st)cout<<i.f<<' '<<i.s<<'\n';
for (auto i :st)safe[i.s]=1;
cntr=0;
rec3(K/2,K,0);
// return 0;
// for (int i=0;i<C;++i)cout<<lefts[i][0]<<' '<<lefts[i][1]<<' '<<lefts[i][2]<<'\n';
for (int i=0;i<C;++i){
if (lefts[i][0] == 0)break;
for (int j=0;j<C;++j){
if (rights[j][0] ==0)break;
cur.clear();
cur.pb(lefts[i][0]);
if (lefts[i][1] != 0)cur.pb(lefts[i][1]);
if (lefts[i][2] != 0)cur.pb(lefts[i][2]);
cur.pb(rights[j][0]);
if (rights[j][1] != 0)cur.pb(rights[j][1]);
if (rights[j][2] != 0)cur.pb(rights[j][2]);
sort(ALL(cur));
cur.resize(unique(ALL(cur)) - cur.begin());
if (SZ(cur) < K)continue;
// for (auto x:cur)cout<<x<<' ';cout<<'\n';
int ans=0;
for (int i=0;i<K;++i){
int t=0;
for (int j=0;j<SZ(cur);++j)t=max(t,mem[cur[j]][i]);
ans += t;
}
M[hh()]=ans;
}
}
for (auto i : M)out.pb(i.s);
sort(ALL(out));
cout<<out[SZ(out) - C];
}#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define ALL(X) X.begin(),X.end()
#define SZ(X) (int)X.size()
#define MAXN 1001000
#define INF 1e9
int N,K,C;
int mem[510][10];
vi cur;
set<pi> st;
vi out;
int cntr;
int lefts[2010][4];
int rights[2010][4];
bitset<21000000> safe;
int ind;
map<ll,int> M;
ll hh(){
ll ans=0;ll mult = 1;
while(SZ(cur)){
ans += mult * cur.back();
cur.pop_back();
mult *= N;
}
return ans;
}
void rec2(int stt, int en){
if (SZ(cur) == en-stt+1){
++cntr;
int ans = 0;
// for (auto i : cur)cout<<i<<' ';cout<<'\n';
for (int i=stt;i<en;++i){
int t=0;
for (int j=1;j<SZ(cur);++j)t=max(t,mem[cur[j]][i]);
ans += t;
}
// cout<<ans<<'\n';
st.insert(mp(ans,cntr));
if (SZ(st) > C)st.erase(st.begin());
return;
}
int lst = cur.back()+1;
for (int i=lst;i<=N;++i){
cur.pb(i);
rec2(stt,en);
cur.pop_back();
}
}
void rec3(int stt, int en, bool flag){
if (SZ(cur) == en-stt+1){
++cntr;
// cout<<cntr<<' '<<safe[cntr]<<'\n';
if (safe[cntr] == 0)return;
int ans = 0;
for (int i=1;i<SZ(cur);++i){
if (flag)lefts[ind][i-1] = cur[i];
else rights[ind][i-1] = cur[i];
}
++ind;
return;
}
int lst = cur.back()+1;
for (int i=lst;i<=N;++i){
cur.pb(i);
rec3(stt,en,flag);
cur.pop_back();
}
}
int main(){
// freopen("in.txt","r",stdin);
cin>>N>>K>>C;
for (int i=1;i<=N;++i)for (int j=0;j<K;++j)cin>>mem[i][j];
cur.pb(0);
rec2(0,K/2);
for (auto i :st)safe[i.s]=1;
cntr=0;
rec3(0,K/2,1);
cntr=ind=0;
while(SZ(st))st.erase(st.begin());
safe.reset();
// cout<<K/2<<' '<<K<<'\n';
rec2(K/2,K);
// for (auto i : st)cout<<i.f<<' '<<i.s<<'\n';
for (auto i :st)safe[i.s]=1;
cntr=0;
rec3(K/2,K,0);
// return 0;
// for (int i=0;i<C;++i)cout<<lefts[i][0]<<' '<<lefts[i][1]<<' '<<lefts[i][2]<<'\n';
for (int i=0;i<C;++i){
if (lefts[i][0] == 0)break;
for (int j=0;j<C;++j){
if (rights[j][0] ==0)break;
cur.clear();
cur.pb(lefts[i][0]);
if (lefts[i][1] != 0)cur.pb(lefts[i][1]);
if (lefts[i][2] != 0)cur.pb(lefts[i][2]);
cur.pb(rights[j][0]);
if (rights[j][1] != 0)cur.pb(rights[j][1]);
if (rights[j][2] != 0)cur.pb(rights[j][2]);
sort(ALL(cur));
cur.resize(unique(ALL(cur)) - cur.begin());
if (SZ(cur) < K)continue;
// for (auto x:cur)cout<<x<<' ';cout<<'\n';
int ans=0;
for (int i=0;i<K;++i){
int t=0;
for (int j=0;j<SZ(cur);++j)t=max(t,mem[cur[j]][i]);
ans += t;
}
M[hh()]=ans;
}
}
for (auto i : M)out.pb(i.s);
sort(ALL(out));
cout<<out[SZ(out) - C];
}