oj.uz

답안 #134237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134237 2019-07-22T08:56:23 Z dvdg6566 Olympiads (BOI19_olympiads) C++14
0 / 100
 561 ms 24312 KB 
#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];
int benson[3000001];
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){
        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;
        }
        ++benson[ans];
        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, int t){
    if (SZ(cur) == en-stt+1){
        int ans = 0;
        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;
        }
        if (ans<t)return;
        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,t);
        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);
    int run=0;int ix=0;
    while(run<C){
        run += benson[ix];
        ++ix;
    }
    // cout<<ind<<'\n';
    rec3(0,K/2,1,ix);
    // cerr<<l<<' '<<u<<'\n';
    memset(benson,0,sizeof(benson));
    rec2(K/2,K);
    ind=0;ix=0;run=0;
    while(run<C){
        run += benson[ix];
        ++ix;
    }
    // cerr<<l<<' '<<u<<'\n';
    rec3(K/2,K,0,ix);
    // cout<<ind<<'\n';
    // for (int i=0;i<C+2;++i)cout<<lefts[i][0]<<' '<<lefts[i][1]<<' '<<lefts[i][2]<<'\n';
    // for (int i=0;i<C+2;++i)cout<<rights[i][0]<<' '<<rights[i][1]<<' '<<rights[i][2]<<'\n';
    for (int i=0;i<C*2;++i){
        if (lefts[i][0] == 0)break;
        for (int j=0;j<C*2;++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];
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 37 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 6136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 561 ms 552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 37 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -