Submission #418605

#TimeUsernameProblemLanguageResultExecution timeMemory
418605abdzagOlympiads (BOI19_olympiads)C++17
0 / 100
2 ms744 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 long long inf = 1e15; 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 cur = k; 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; cout << "hello" << endl; 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(501); 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] == k) { 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] == k) { 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; 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; }

Compilation message (stderr)

olympiads.cpp: In function 'll choose(ll, ll)':
olympiads.cpp:22:5: warning: unused variable 'cur' [-Wunused-variable]
   22 |  ll cur = k;
      |     ^~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:81:23: warning: overflow in conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1000000000000000' to '-1530494976' [-Woverflow]
   81 |   vector<int> init(k, inf);
      |                       ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...