QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#644689 | #2541. Coins and Boxes | proven# | WA | 34ms | 15916kb | C++20 | 1.9kb | 2024-10-16 15:07:33 | 2024-10-16 15:07:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int, int>
const int N = 4e5 + 5;
const int mod = 1e9 + 7;
int n, top, b[N], c[N], a[N], dp[N];
vector<PII> tr;
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> b[i], a[++top] = b[i];
for (int i = 1; i <= n; i++)
cin >> c[i], c[i] = max(c[i], b[i]), a[++top] = c[i];
sort(a + 1, a + 1 + top);
top = unique(a + 1, a + 1 + top) - a - 1;
for (int i = 1; i <= n; i++)
{
b[i] = lower_bound(a + 1, a + 1 + top, b[i]) - a;
c[i] = lower_bound(a + 1, a + 1 + top, c[i]) - a;
}
tr.push_back({0, 0});
for (int i = 1; i <= n; i++)
tr.push_back({b[i], c[i]});
fill(dp + 1, dp + 1 + n, 1e18);
dp[0] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, 0});
sort(tr.begin(), tr.end());
// for (int i = 1; i <= n; i++)
// {
// auto [l, r] = tr[i]; // 从一个盒子转移过来//pre//dp[i]=min{dp[pre]+tr[i].r-tr[pre].l+tr[i].r-tr[pre].l}
// int pre = q.top().second;
// dp[i] = dp[pre] + 2 * a[tr[i].second] - 2 * a[tr[pre].first] + a[tr[i].first] - a[tr[pre].first] - a[tr[pre].second] + a[tr[pre].first];
// q.push({dp[i] - a[tr[i].second] - a[tr[i].first] - a[tr[i].first], i});
// }
for (int i = 1; i <= n; i++)
{
dp[i] = dp[i - 1] + a[tr[i].first] - a[tr[i - 1].first] + 2 * (a[tr[i].second] - a[tr[i].first]);
}
int ans = 1e18, mx = a[top];
for (int i = 1; i <= n; i++)
{
ans = min(dp[i - 1] + 2 * mx - 2 * a[tr[i].first] + a[tr[i].first] - a[tr[i - 1].first], ans);
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 9712kb
input:
4 1 6 7 12 3 5 10 11
output:
21
result:
ok answer is '21'
Test #2:
score: 0
Accepted
time: 1ms
memory: 10008kb
input:
2 1 2 1 1000000000
output:
1999999998
result:
ok answer is '1999999998'
Test #3:
score: -100
Wrong Answer
time: 34ms
memory: 15916kb
input:
100000 967 3246 9492 10300 15195 16650 26911 54855 83695 112841 125511 137160 153051 155859 177924 187843 214838 219388 247276 249612 250188 253873 257830 261805 281312 297030 298332 325904 333218 339683 374111 387794 396645 403705 426710 436137 463368 481801 501933 509267 511332 515225 515629 51686...
output:
1999994467
result:
wrong answer expected '1722240547', found '1999994467'