Submission #418888

#TimeUsernameProblemLanguageResultExecution timeMemory
418888usachevd0Carnival Tickets (IOI20_tickets)C++17
39 / 100
3094 ms2097156 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "tickets.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() #define Time (clock() * 1.0 / CLOCKS_PER_SEC) using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& e : v) stream << e << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } const ll INF64 = 1e18; const int maxN = 1503; void allocate_tickets(vector<vector<int>> cert); ll find_maximum(int k, vector<vector<int>> X) { int n = X.size(), m = X[0].size(); vector<pii> vals[n]; vector<ll> pref[n], suff[n]; for (int i = 0; i < n; ++i) { vals[i].resize(m); for (int j = 0; j < m; ++j) vals[i][j] = {X[i][j], j}; sort(all(vals[i])); pref[i].assign(m + 1, 0); for (int j = 0; j < m; ++j) pref[i][j + 1] = pref[i][j] + vals[i][j].fi; suff[i].assign(m + 1, 0); for (int j = m - 1; j >= 0; --j) suff[i][j] = suff[i][j + 1] + vals[i][j].fi; } int need = n / 2 * k; vector<vector<ll>> dp(n + 1, vector<ll>(need + 1, -INF64)); vector<vector<int>> p(n + 1, vector<int>(need + 1, -1)); dp[0][0] = 0; for (int i = 0; i < n; ++i) { for (int l = 0; l <= k; ++l) { ll delta = suff[i][m - (k - l)] - pref[i][l]; for (int s = l; s <= need; ++s) { if (chkmax(dp[i + 1][s], delta + dp[i][s - l])) { p[i + 1][s] = l; } } } } ll ans = dp[n][need]; int i = n - 1, s = need; vector<int> L(n); while (i != -1) { L[i] = p[i + 1][s]; s -= L[i]; --i; } vector<int> S(n); for (int i = 0; i < n; ++i) S[i] = k - L[i]; vector<vector<int>> cert(n, vector<int>(m, -1)); multiset<pii> pq; for (int i = 0; i < n; ++i) pq.insert({-L[i], i}); for (int d = 0; d < k; ++d) { vector<int> small(n, 0); for (int t = 0; t < n / 2; ++t) { int i = pq.begin()->se; pq.erase(pq.begin()); small[i] = 1; } for (int i = 0; i < n; ++i) if (small[i]) { int j = vals[i][--L[i]].se; cert[i][j] = d; pq.insert({-L[i], i}); } else { int j = vals[i][m - S[i]].se; --S[i]; cert[i][j] = d; } } allocate_tickets(cert); return ans; } #ifdef LOCAL static int n; static int m; static int k; static std::vector<std::vector<int>> d; static std::vector<std::vector<int>> x; static int called = 0; static void check(bool cond, std::string message) { if (!cond) { printf("%s\n", message.c_str()); exit(0); } } void allocate_tickets( std::vector<std::vector<int>> _d) { check(!called, "allocate_tickets called more than once"); d = _d; check((int)d.size() == n, "allocate_tickets called with parameter of wrong size"); for (int i = 0; i < n; i++) { check((int)d[i].size() == m, "allocate_tickets called with parameter of wrong size"); } called = 1; } int main() { freopen("in", "r", stdin); assert(scanf("%d %d %d", &n, &m, &k) == 3); x.resize(n); for (int i = 0; i < n; i++) { x[i].resize(m); for (int j=0; j < m; j++) { assert(scanf("%d", &x[i][j]) == 1); } } fclose(stdin); long long answer = find_maximum(k, x); check(called, "failure to call allocate_tickets"); printf("%lld\n", answer); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (j) printf(" "); printf("%d", d[i][j]); } printf("\n"); } fclose(stdout); return 0; } // int32_t main() { // #ifdef LOCAL // freopen("in", "r", stdin); // #endif // ios::sync_with_stdio(0); // cin.tie(0); // return 0; // } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...