#include using namespace std; struct Item { string name; long long q, v, m, l; }; struct Solution { vector x; long long value; long long remM, remL; }; static const long long CAP_M = 20LL * 1000000LL; // mg static const long long CAP_L = 25LL * 1000000LL; // uL void skipSpaces(const string& s, size_t& i){ while(i < s.size() && isspace((unsigned char)s[i])) i++; } bool parseString(const string& s, size_t& i, string& out){ skipSpaces(s, i); if(i >= s.size() || s[i] != '"') return false; i++; string res; while(i < s.size() && s[i] != '"'){ // no escape handling needed for given problem res.push_back(s[i]); i++; } if(i >= s.size() || s[i] != '"') return false; i++; out = res; return true; } bool parseInt(const string& s, size_t& i, long long& val){ skipSpaces(s, i); bool neg = false; if(i < s.size() && (s[i] == '-' || s[i] == '+')){ neg = (s[i]=='-'); i++; } skipSpaces(s, i); if(i >= s.size() || !isdigit((unsigned char)s[i])) return false; long long v = 0; while(i < s.size() && isdigit((unsigned char)s[i])){ v = v*10 + (s[i]-'0'); i++; } val = neg ? -v : v; return true; } bool parseArray4(const string& s, size_t& i, array& arr){ skipSpaces(s, i); if(i >= s.size() || s[i] != '[') return false; i++; for(int k=0;k<4;k++){ skipSpaces(s, i); // potential newlines/commas long long x; if(!parseInt(s, i, x)) return false; arr[k]=x; skipSpaces(s, i); if(k<3){ if(i >= s.size()) return false; // allow trailing commas and newlines/spaces if(s[i] == ','){ i++; } } } skipSpaces(s, i); // allow trailing commas/newlines inside array while(i < s.size() && s[i] != ']'){ // consume potential commas or spaces/newlines if(s[i]==','){ i++; } else if(isspace((unsigned char)s[i])) i++; else break; } if(i >= s.size() || s[i] != ']') return false; i++; return true; } vector parseInput(const string& s){ vector items; size_t i=0; skipSpaces(s,i); if(i= s.size() || s[i] != ':') break; i++; array arr; if(!parseArray4(s,i,arr)) break; items.push_back({key, arr[0], arr[1], arr[2], arr[3]}); skipSpaces(s,i); if(i < s.size() && s[i]==','){ i++; continue; } } return items; } long long ceil_div(long long a, long long b){ if (a <= 0) return 0; return (a + b - 1) / b; } Solution greedyFill(const vector& items, const vector& order){ int n = items.size(); Solution sol; sol.x.assign(n,0); sol.remM = CAP_M; sol.remL = CAP_L; sol.value = 0; for(int idx : order){ const auto& it = items[idx]; if (it.m > CAP_M || it.l > CAP_L) continue; long long byM = sol.remM / it.m; long long byL = sol.remL / it.l; long long take = min({it.q, byM, byL}); if(take <= 0) continue; sol.x[idx] += take; sol.remM -= take * it.m; sol.remL -= take * it.l; sol.value += take * it.v; } return sol; } void tryDirectFill(const vector& items, const vector& order, Solution& sol){ for(int idx : order){ const auto& it = items[idx]; if (it.m > CAP_M || it.l > CAP_L) continue; long long canq = it.q - sol.x[idx]; if(canq <= 0) continue; long long byM = sol.remM / it.m; long long byL = sol.remL / it.l; long long take = min({canq, byM, byL}); if(take <= 0) continue; sol.x[idx] += take; sol.remM -= take * it.m; sol.remL -= take * it.l; sol.value += take * it.v; } } bool improveOneSwap(const vector& items, Solution& sol){ int n = items.size(); // attempt adding one of item a, removing t of item b for(int a=0;a= ia.q) continue; if (ia.m > CAP_M || ia.l > CAP_L) continue; long long needM = max(0LL, ia.m - sol.remM); long long needL = max(0LL, ia.l - sol.remL); if(needM==0 && needL==0){ // can add directly sol.x[a] += 1; sol.remM -= ia.m; sol.remL -= ia.l; sol.value += ia.v; return true; } // try remove one type b for(int b=0;b sol.x[b]) continue; long long deltaV = ia.v - t * ib.v; if(deltaV <= 0) continue; // apply sol.x[a] += 1; sol.x[b] -= t; sol.remM = sol.remM - ia.m + t * ib.m; sol.remL = sol.remL - ia.l + t * ib.l; sol.value += deltaV; return true; } } return false; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); string input, line; { ostringstream oss; oss << cin.rdbuf(); input = oss.str(); } vector items = parseInput(input); int n = items.size(); if(n==0){ cout << "{\n}\n"; return 0; } // Prepare multiple orderings (strategies) vector> strategies; // weights alpha from 0..10 on normalized m,l for(int a=0;a<=10;a++){ vector> score; for(int i=0;i ord; for(auto &p:score) ord.push_back(p.second); strategies.push_back(ord); } // v per mass { vector> score; for(int i=0;i ord; for(auto &p:score) ord.push_back(p.second); strategies.push_back(ord); } // v per volume { vector> score; for(int i=0;i ord; for(auto &p:score) ord.push_back(p.second); strategies.push_back(ord); } // v per max normalized dimension { vector> score; for(int i=0;i ord; for(auto &p:score) ord.push_back(p.second); strategies.push_back(ord); } Solution best; best.x.assign(n,0); best.value = 0; best.remM = CAP_M; best.remL = CAP_L; for(auto &ord : strategies){ Solution sol = greedyFill(items, ord); // local improvements // First try to fill more directly following same order repeatedly tryDirectFill(items, ord, sol); // hill-climb with single-type removal int iter=0; const int MAX_ITERS = 2000; while(iter < MAX_ITERS){ bool improved = improveOneSwap(items, sol); if(!improved) break; // after a successful swap, try direct fill again tryDirectFill(items, ord, sol); iter++; } if(sol.value > best.value){ best = sol; } } // Output JSON with same keys as input order cout << "{\n"; for(int i=0;i