제출 #418778

#제출 시각아이디문제언어결과실행 시간메모리
418778abdzagOlympiads (BOI19_olympiads)C++17
0 / 100
27 ms932 KiB
#include<bits/stdc++.h> //#include"tickets.h" #include<unordered_map> #define rep(i,a,b) for(int i=int(a);i<int(b);i++) #define rrep(i,a,b) for(int i=int(a);i>int(b);i--) #define trav(a,v) for(auto& a: v) #define sz(v) v.size() #define all(v) v.begin(),v.end() #define vi vector<int> typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int inf = 1e9; using namespace std; ll choose(ll n, ll k) { if (n == 0)return 0; if (k == 0)return 1; if (k == n)return 1; ll ans = 1; rrep(i, n, (n - k)) { ll ny = i; ans *= ny; } rep(i, 1, k + 1)ans /= i; return ans; } vector<vector<ll>> choices(501, vector<ll>(7)); int main() { cin.sync_with_stdio(false); ll n, c, k; rep(i, 0, 501) { rep(j, 0, 6) { if (i < j)continue; ll val = choose(i, j); if (val > 1e9)break; choices[i][j] = val; } } cin >> n >> k >> c; vector<vector<ll>> v(n, vector<ll>(k)); rep(i, 0, n)rep(j, 0, k)cin >> v[i][j]; vector < vector<pair<ll, ll>>> vec(k); rep(i, 0, n) { rep(j, 0, k) { vec[j].emplace_back(v[i][j], i); } } trav(a, vec)sort(all(a), greater<>()); map<vector<int>, bool> mp; vector<int> cur(k); ll val = 0; vector<vector<int>> sorted; bitset<501> present; ll mising = k; rep(i, 0, k) { if (!present[vec[i][cur[i]].second]) { mising--; present[vec[i][cur[i]].second] = 1; } } val += choices[n - (k - mising)][mising]; mp[cur] = 1; ll order = 0; while (val < c) { bool done = true; vector<int> cur2 = cur; rep(i, 0, k) { cur2[i]++; done = mp[cur2]; cur2[i]--; } if (done) { cur = sorted[order++]; } vector<int> init(k, inf); pair<ll, vector<int>> best = make_pair(inf, init); rep(i, 0, k) { cur2 = cur; bool bad = false; while (mp[cur2]) { cur2[i]++; if (cur2[i] == n) { bad = true; break; } //rep(j, 0, cur.size()) { // if (i == j)continue; // if(vec[j][cur2[j]].second == vec[i][cur2[i]].second) //} } if (bad)continue; rep(j, 0, k) { if (j == i)continue; if (vec[j][cur[j]].second == vec[i][cur[i]].second) { cur2[j]++; while (mp[cur2]) { cur2[j]++; if (cur2[j] == n) { bad = true; break; } } } if (bad) { break; } } if (bad)continue; pair<ll, vector<int>> local = make_pair(0, cur2); rep(j, 0, k) { local.first += vec[j][cur[j]].first - vec[j][cur2[j]].first; } best = min(best, local); } cur2 = best.second; sorted.push_back(cur2); mp[cur2] = 1; ll howmany = n; bitset<501> visited; bitset<501> present; rep(i, 0, k) { rrep(j, cur2[i], -1) { if (!visited[vec[i][j].second]) { howmany--; visited[vec[i][j].second] = 1; } } } ll mising = k; rep(i, 0, k) { if (!present[vec[i][cur2[i]].second]) { mising--; present[vec[i][cur2[i]].second] = 1; } } val += choices[howmany][mising]; if (val >= c)cur = cur2; } ll ans = 0; rep(i, 0, k) { ans += vec[i][cur[i]].first; } cout << ans << endl; 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...