Submission #1187037

#TimeUsernameProblemLanguageResultExecution timeMemory
1187037kl0989eOlympiads (BOI19_olympiads)C++20
0 / 100
2090 ms52556 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back #define vi vector<int> #define vl vector<ll> #define pi pair<int, int> #define pl pair<ll,ll> #define all(x) (x).begin(),(x).end() vector<vi> have; vector<vi> peop; int clc(vi& goal) { vector<vi> dp(goal.size()+1,vi(1<<goal.size(),0)); dp[0][0]=1; for (int i=0; i<peop.size(); i++) { for (int l=goal.size()-1; l>=0; l--) { for (int j=dp[0].size()-1; j>=0; j--) { int newj=j; for (int k=0; k<goal.size(); k++) { if (goal[k]<peop[i][k]) { newj=-1; break; } if (goal[k]==peop[i][k]) { newj|=(1<<k); } } if (newj==-1) { break; } dp[l+1][newj]+=dp[l][j]; if (dp[l+1][newj]>10000) { dp[l+1][newj]=10000; } } } } return dp.back().back(); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,k,c; cin >> n >> k >> c; have.resize(k); peop.resize(n,vi(k,0)); for (int i=0; i<n; i++) { for (int j=0; j<k; j++) { cin >> peop[i][j]; have[j].pb(peop[i][j]); } } int mx=0; array<int,6> inds; for (int i=k-1; i>=0; i--) { sort(all(have[i])); have[i].erase(unique(all(have[i])),have[i].end()); mx+=have[i].back(); inds[i]=have[i].size()-1; } priority_queue<pair<int,array<int,6>>,vector<pair<int,array<int,6>>>,greater<pair<int,array<int,6>>>> q; q.push({mx,inds}); set<array<int,6>> seen; while (1) { auto [s,inds]=q.top(); q.pop(); vi nums; for (int i=0; i<k; i++) { nums.pb(have[i][inds[i]]); } c-=clc(nums); if (c<=0) { cout << s << '\n'; break; } for (int i=0; i<k; i++) { if (inds[i]==0) { continue; } inds[i]--; if (seen.count(inds)) { inds[i]++; continue; } s-=have[i][inds[i]+1]-have[i][inds[i]]; q.push({s,inds}); seen.insert(inds); s+=have[i][inds[i]+1]-have[i][inds[i]]; inds[i]++; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...