QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#525122 | #7523. Partially Free Meal | rxzfn639 | RE | 0ms | 0kb | C++23 | 1.2kb | 2024-08-20 13:07:29 | 2024-08-20 13:07:29 |
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 P = 998244353;
void solve() {
int n;
cin >> n;
vector<i64> a(n), b(n), ans(n);
i64 res = 0, mxb = 0;
set<pair<i64, i64>> sa, sb;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
sa.insert({a[i], i});
sb.insert({b[i], i});
res += a[i];
mxb = max(mxb, b[i]);
}
res += mxb;
ans[n - 1] = res;
for (int i = n - 2; i >= 0; i--) {
auto tmp1 = *sa.rbegin();
auto tmp2 = *sb.rbegin();
auto tmp3 = *prev(sb.rbegin());
i64 res1 = tmp1.first, res2 = a[tmp2.second] + b[tmp2.second] - b[tmp3.second];
if (res1 > res2) {
ans[i] = ans[i + 1] - res1;
sa.erase(tmp1);
sb.erase({b[tmp1.second], tmp1.second});
} else {
ans[i] = ans[i + 1] - res2;
sb.erase(tmp2);
sa.erase({a[tmp2.second], tmp2.second});
}
}
for (int i = 0; i < n; i++) {
cout << ans[i] << '\n';
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
/*
3
2 5
4 3
3 7
*/
詳細信息
Test #1:
score: 0
Runtime Error
input:
3 2 5 4 3 3 7