#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;
};
bool operator<(state x, state y) {return x.score<y.score;}
int n,k,c;
int a[505][11];
bool chk[505];
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=true;
//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(bef.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.pop_back(); ret.selected.push_back(j);
}
}
}
vector<int> val(k,0);
ret.score=0;
for(int i=0;i<k;i++) {
for(int j=0;j<k;j++) if(~ret.selected[i]) val[j]=max(val[j],a[ret.selected[i]][j]);
}
for(int i=0;i<k;i++) ret.score+=val[i];
if(ret.selected.back()==-1) ret.can=false;
return ret;
}
void solve() {
cin>>n>>k>>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({0,{},{},vector<bool>(n,false),1});
int cnt=0;
while(c--) {
state now=pq.top(); pq.pop();
if(!c) cout<<now.score;
for(int i=now.forced.size();i<k;i++) {
//selected[i]는 선택된 것 중 강제 안 된거..
//강제 안 된거 하나씩 금지 시키면서 가야 함
now.forbidden[now.selected[i]]=true;
state nxt=go(now);
if (find(nxt.selected.begin(), nxt.selected.end(), -1) == nxt.selected.end())
pq.push(nxt);
if(nxt.can) pq.push(nxt);
now.forbidden[now.selected[i]]=false;
now.forced.push_back(now.selected[i]);
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tc=1; //cin>>tc;
while(tc--) solve();
}
Compilation message
olympiads.cpp: In function 'void solve()':
olympiads.cpp:71:9: warning: unused variable 'cnt' [-Wunused-variable]
71 | int cnt=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
