QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398141 | #6531. Base Station Construction | iwew | WA | 50ms | 7992kb | C++20 | 1.0kb | 2024-04-24 23:18:04 | 2024-04-24 23:18:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int n, m;
int a[N];
ll dp[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T -- ) {
cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
cin >> m;
vector<pair<int, int>> seq(m + 1);
for(int i = 0; i < m; i ++ ) {
cin >> seq[i].first >> seq[i].second;
}
seq[m] = {n + 1, n + 1};
sort(seq.begin(), seq.end());
vector<bool> has(n + 1, false);
for(int i = 0; i <= n + 1; i ++ ) dp[i] = 0;
for(int i = 0; i < m; i ++ ) {
has[seq[i].second] = true;
}
for(int i = n; i >= 1; i -- ) {
if(has[i]) {
dp[i] = dp[i + 1] + a[i];
} else {
dp[i] = dp[i + 1];
}
int l = 0, r = m;
while(l < r) {
int mid = (l + r) >> 1;
if(seq[mid].first > i) r = mid;
else l = mid + 1;
}
int pos = seq[l].first;
dp[i] = min(dp[i], dp[pos] + a[i]);
}
cout << dp[1] << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5660kb
input:
2 5 3 2 4 1 100 3 1 3 2 4 5 5 5 7 3 4 2 2 3 1 4 2 3 4 5
output:
102 5
result:
ok 2 number(s): "102 5"
Test #2:
score: -100
Wrong Answer
time: 50ms
memory: 7992kb
input:
6201 12 88 78 46 95 84 98 55 3 68 42 6 18 19 6 9 10 11 12 12 8 11 8 12 2 3 2 3 1 5 9 9 7 8 6 11 2 4 12 12 2 4 2 9 7 10 8 8 1 7 6 11 5 76 27 48 66 61 2 1 4 3 5 8 64 81 20 6 86 9 4 55 1 7 7 9 1 43 18 81 11 22 9 61 83 14 5 6 2 6 5 8 1 4 9 9 9 9 7 7 2 5 8 9 5 6 4 8 5 8 9 9 6 6 10 66 41 84 7 80 31 22 96 ...
output:
232 48 4 267 303 141 23 170 159 192 265 243 267 127 268 93 411 89 138 130 294 27 1 193 359 93 239 312 378 150 177 57 46 18 91 79 83 160 196 62 35 122 285 275 115 277 61 394 252 306 383 86 399 244 288 87 302 81 223 173 30 129 145 128 126 179 81 312 142 277 143 111 235 247 211 53 91 17 213 101 482 176...
result:
wrong answer 1st numbers differ - expected: '141', found: '232'