Submission #773170

#TimeUsernameProblemLanguageResultExecution timeMemory
773170GrindMachineOlympiads (BOI19_olympiads)C++17
100 / 100
22 ms1268 KiB
// Om Namah Shivaya #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x, y) ((x + y - 1) / (y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i, n) for(int i = 0; i < n; ++i) #define rep1(i, n) for(int i = 1; i <= n; ++i) #define rev(i, s, e) for(int i = s; i >= e; --i) #define trav(i, a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: edi => https://boi2019.eio.ee/wp-content/uploads/2019/05/olymp.sol_.en_.pdf fracturing search => https://usaco.guide/adv/fracturing-search?lang=cpp */ const int MOD = 1e9 + 7; const int N = 500 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; const int K = 6; int n,k,c; int a[N][K]; int get_val(vector<int> team){ rep(j,k){ if(team[j] == -1){ return 0; } } int res = 0; rep(j,k){ int mx = 0; trav(i,team){ amax(mx,a[i][j]); } res += mx; } return res; } vector<bool> there(N); struct item { vector<int> team; vector<bool> banned; int cost = 0; int fix = -1; void calc(){ trav(i,team){ if(i != -1){ there[i] = 1; } } rep(j,k){ if(team[j] != -1) conts; int mx = -1, ind = -1; rep(i,n){ if(banned[i] or there[i]) conts; if(a[i][j] > mx){ mx = a[i][j]; ind = i; } } if(ind == -1) break; team[j] = ind; there[ind] = 1; } cost = get_val(team); trav(i,team){ if(i != -1){ there[i] = 0; } } } item(){ team = vector<int>(k,-1); banned = vector<bool>(n); calc(); } item(vector<int> team_, vector<bool> banned_, int fix_){ team = team_; banned = banned_; fix = fix_; calc(); } }; bool operator<(const item &x, const item &y){ return x.cost < y.cost; } void solve(int test_case) { cin >> n >> k >> c; rep(i,n) rep(j,k) cin >> a[i][j]; priority_queue<item> pq; pq.push(item()); rep1(id,c){ if(pq.empty()){ debug(id); break; } auto curr = pq.top(); pq.pop(); if(id == c){ cout << curr.cost << endl; return; } // debug(curr.team); // debug(curr.cost); rep(i,k){ if(curr.team[i] == -1){ return; } } rep(i,k){ if(i <= curr.fix) conts; auto team = curr.team; auto banned = curr.banned; int fix = i-1; banned[team[i]] = 1; team[i] = -1; for(int j = i+1; j < k; ++j){ team[j] = -1; } pq.push(item(team,banned,fix)); } } } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }

Compilation message (stderr)

olympiads.cpp: In function 'void solve(int)':
olympiads.cpp:48:18: warning: statement has no effect [-Wunused-value]
   48 | #define debug(x) 42
      |                  ^~
olympiads.cpp:157:13: note: in expansion of macro 'debug'
  157 |             debug(id);
      |             ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...