Submission #1178076

#TimeUsernameProblemLanguageResultExecution timeMemory
1178076browntoadCarnival Tickets (IOI20_tickets)C++20
100 / 100
444 ms81540 KiB
#include <bits/stdc++.h> #include "tickets.h" using namespace std; #define ll long long // #define int ll #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define REP1(i, n) FOR(i, 1, n+1) #define RREP(i, n) for (int i = (n)-1; i >= 0; i--) #define pii pair<int, int> #define pip pair<int, pii> #define f first #define s second #define pb push_back #define ALL(x) (x).begin(), (x).end() #define SZ(x) (int)((x).size()) void make_tickets(vector<vector<int>> nids, vector<vector<int>> pids, int k, int m){ int n = SZ(nids); vector<vector<int>> ans(n); REP(i, n){ ans[i] = vector<int> (m); REP(j, m) ans[i][j] = -1; } REP(t, k){ vector<bool> tmp(n); int cnt = 0; REP(i, n) { if (cnt >= n/2) break; if (SZ(nids[i]) == 0){ ans[i][pids[i].back()] = t; pids[i].pop_back(); cnt++; tmp[i] = 1; } } REP(i, n){ if (cnt >= n/2) break; if (SZ(pids[i]) > 0 && !tmp[i]){ ans[i][pids[i].back()] = t; pids[i].pop_back(); cnt++; tmp[i] = 1; } } REP(i, n){ if (!tmp[i]){ ans[i][nids[i].back()] = t; nids[i].pop_back(); } } } allocate_tickets(ans); } const ll maxn = 1505; static ll dp[maxn][maxn]; static int pre[maxn][maxn]; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); std::vector<std::vector<int>> tick(n); // -1 if neg, +1 if pos, 0 if nothing REP(i, n) tick[i] = vector<int> (m); ll sm = 0; priority_queue<pip> pq; REP(i, n){ REP(j, k){ sm -= x[i][j]; tick[i][j] = -1; } pq.push({x[i][k-1 + (m-k)] + x[i][k-1], {i, k-1}}); } REP(t, n/2*k){ pip tp = pq.top(); pq.pop(); sm += tp.f; tick[tp.s.f][tp.s.s] = 0; tick[tp.s.f][tp.s.s+(m-k)] = 1; if (tp.s.s > 0){ pq.push({x[tp.s.f][tp.s.s-1 + (m-k)] + x[tp.s.f][tp.s.s-1], {tp.s.f, tp.s.s-1}}); } } vector<vector<int>> poo1(n), poo2(n); REP(i, n){ vector<int> t1, t2; REP(j, m){ if (tick[i][j] == -1) t1.pb(j); if (tick[i][j] == 1) t2.pb(j); } poo1[i] = t1; poo2[i] = t2; } make_tickets(poo1, poo2, k, m); return sm; } /* 2 3 2 0 2 5 1 1 3 */
#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...