#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define dbg(x) cout << #x << " = " << (x) << endl;
//const int INF = 1e18;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
int n = p.size();
vector<pair<int, int>> p1, p2;
for(int i = 0; i < n; ++i){
if(t[i] == 1) p1.emplace_back(p[i], i);
else p2.emplace_back(p[i], i);
}
sort(p1.begin(), p1.end());
sort(p2.begin(), p2.end());
int i = 0, j = 0;
vector<int> ans;
while (true) {
bool picked = false;
if (i < (int)p1.size() && a >= p1[i].first) {
//pick t=1 coupon
if (j < (int)p2.size() && a >= p2[j].first) {
//pick t=2 coupon
int after1 = a - p1[i].first;
int after2 = (a - p2[j].first) * 2;
if (after1 > after2) {
// pick T=1
a = after1;
ans.push_back(p1[i].second);
++i;
picked = true;
} else {
// pick T=2
a = after2;
ans.push_back(p2[j].second);
++j;
picked = true;
}
} else {
// Only t=1 is affordable
a = a - p1[i].first;
ans.push_back(p1[i].second);
++i;
picked = true;
}
} else if (j < (int)p2.size() && a >= p2[j].first) {
// Only t=2 is affordable
a = (a - p2[j].first) * 2;
ans.push_back(p2[j].second);
++j;
picked = true;
}
if (!picked) break;
}
return ans;
}
/*int32_t main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("input.in", "r", stdin);
//freopen("input.out", "w", stdout);
vector<int> ans = max_coupons(13, {4, 500, 8, 14}, {1, 1, 1, 1});
for(auto x : ans) cout<<x<<endl;
return 0;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |