QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398141#6531. Base Station ConstructioniwewWA 50ms7992kbC++201.0kb2024-04-24 23:18:042024-04-24 23:18:05

Judging History

你现在查看的是最新测评结果

  • [2024-04-24 23:18:05]
  • 评测
  • 测评结果:WA
  • 用时:50ms
  • 内存:7992kb
  • [2024-04-24 23:18:04]
  • 提交

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'