### viggibear's blog

By viggibear, history, 9 months ago, From what I know, the problem can be solved by greedy since ceil(n) = 100000 so even O(n^2) might fail but my greedy solution has been failing due to various different reasons. Any insights appreciated! Comments (3)
 » Solved using a Greedy that sorts {buy, sell} pairs by ascending order based on buy + sell price. Subtract price of buying first K and add price of selling next T-K and return from this sorted list of pairs. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef pair pii; typedef pair pll; typedef pair pss; typedef map mii; typedef map mib; typedef map msi; typedef vector vi; typedef vector vvi; typedef vector vii; typedef vector vl; typedef vector vvl; // Use these constants so you don't need to define your own const int SZ = 1E6; const int INF = (1 << 29); const double EPS = 1E-9; const double PI = 2 * acos(0.0); const ll MOD = 1000000007; int dirx = {-1, 0, 0, 1, -1, -1, 1, 1}; int diry = {0, 1, -1, 0, -1, 1, -1, 1}; #define VALUE(x) cout << "The value of " << #x << " is " << x << endl #define NL cout << endl; #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a)) #define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a)) #define FORD(a, b, c) for (int(a) = (b); (a) >= (c); --(a)) #define FORSQ(a, b, c) for (int(a) = (b); (a) * (a) <= (c); ++(a)) #define FORC(a, b, c) for (char(a) = (b); (a) <= (c); ++(a)) #define FOREACH(a, b) for (auto &(a) : (b)) #define REP(i, n) FOR(i, 0, n) // for (int i = 0; i < n; i++) #define REPN(i, n) FORN(i, 1, n) // for (int i = 1; i <= n; i++) #define MAX(a, b) a = max(a, b) #define MIN(a, b) a = min(a, b) #define SQR(x) ((ll)(x) * (x)) #define RESET(a, b) memset(a, b, sizeof(a)) // reset an array before using #define RESET2D(a, b) fill_n(*a, sizeof a / sizeof **a, b) #define fi first #define se second #define mp make_pair #define pb push_back #define ALL(v) v.begin(), v.end() #define ALLA(arr, sz) arr, arr + sz #define SIZE(v) (int)v.size() #define SORT(v) sort(ALL(v)) // sort an array faster #define REVERSE(v) reverse(ALL(v)) #define SORTA(arr, sz) sort(ALLA(arr, sz)) #define REVERSEA(arr, sz) reverse(ALLA(arr, sz)) #define PERMUTE next_permutation #define TC(t) while (t--) int N, T, K, bp, sp, h; ll p = 0; vii n; int main(void) { cin >> N >> T >> K; RESET(h, 0); // histogram REP(i, N) { cin >> bp; h[bp]++; } // place into net as {buy price, sell price} REPN(i, T) { cin >> bp >> sp; n.pb(mp(max(2 - h[i], 0) * bp, h[i] * sp)); } sort(begin(n), end(n), // Sort all pairs based on sum of buy + sell [](const pii &a, const pii &b) { return a.fi + a.se < b.fi + b.se; }); REP(i, K) p -= n[i].fi; // For first K --> subtract buy from profits FOR(i, K, n.size()) p += n[i].se; // For remaining T-K --> add sell price to profits cout << p << endl; } 
•  » » Hi, do you mind explaining what is the rationale of sorting by sum of buy + sell?
•  » » » For each card type, the "net cost" of making it up to a combo is the cost for buying missing card(s) plus the loss of profit for not selling card(s) of that type.