Submission #898357

#	Time	Username	Problem	Language	Result	Execution time	Memory
898357		dong_gas	Olympiads (BOI19_olympiads)	C++17	100 / 100	58 ms	1704 KiB

olympiads

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

struct state {
    int score;
    vector<int> selected, forced; //선택된 거, 강제된 거
    vector<bool> forbidden; //금지된 거
    bool can; //가능한 상태? (==k개가 온전히 선택 되었는지)
};

bool operator<(state x, state y) {return x.score<y.score;}

int n,k,c;
int a[500][6];

bool is_in(vector<int>& v, int x)  {
    for(int i:v) if(i==x) return true;
    return false;
}

state go(state bef) {
    state ret=bef;
    ret.selected=bef.forced;
    ret.can=false;
    //selected는 각각 순서대로 best점수 유지할 거임
    for(int i=ret.selected.size();i<k;i++) {
        //k개까지 선택할 거임.
        ret.selected.push_back(-1);
        for(int j=0;j<n;j++) {
            //금지된 것 아니고
            //이미 선택된 것 아니고
            if(ret.forbidden[j]) continue;
            if(is_in(ret.selected,j)) continue;

            //아직 선택 안 했거나
            //방금 추가한 학생보다 이벤트 점수 높으면 바꿀 거임.
            if(ret.selected[i]==-1 || a[j][i]>a[ret.selected[i]][i]) ret.selected.back()=j;
        }        
    }
    if(ret.selected.back()==-1) return ret;
    ret.can=true;
    vector<int> val(k,0);
    ret.score=0;
    for(int i=0;i<k;i++) for(int j=0;j<k;j++) val[j]=max(val[j],a[ret.selected[i]][j]);
    for(int i=0;i<k;i++) ret.score+=val[i];
    return ret;
}

void solve() {
    cin>>n>>k>>c;
    c--;
    for(int i=0;i<n;i++) for(int j=0;j<k;j++) cin>>a[i][j];
    std::priority_queue<state> pq;
    pq.push(go({0,{},{},vector<bool>(n,false),1}));
    while(c--) {
        state now=pq.top(); pq.pop();      
        for(int i=now.forced.size();i<k;i++) {
            //selected[i]는 선택된 것 중 강제 안 된거..
            //강제 안 된거 하나씩 금지 시키면서 가야 함
            now.forbidden[now.selected[i]]=true;
            state nxt=go(now);
            if(nxt.can) pq.push(nxt);
            now.forbidden[now.selected[i]]=false;
            now.forced.push_back(now.selected[i]);
        }
    }
    cout<<pq.top().score;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc=1; //cin>>tc;
    while(tc--) solve();
}

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32