QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #809473 | #3632. Izvanredna Isplata | rlc202204 | AC ✓ | 854ms | 4828kb | C++17 | 1.0kb | 2024-12-11 15:19:45 | 2024-12-11 15:19:47 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 5;
const int m = 1e5 + 5;
const int M = m + 5;
const int inf = 0x3f3f3f3f;
int n;
int c[N] = {0};
int d[M] = {0};
void bfs() {
memset(d, 0x3f, sizeof d);
queue<int> q;
q.push(0), d[0] = 0;
while (!q.empty()) {
int h = q.front();
q.pop();
for (int i = 1; i <= n; i++)
if (h + c[i] <= m && d[h + c[i]] > d[h] + 1)
d[h + c[i]] = d[h] + 1, q.push(h + c[i]);
}
}
int f[M] = {0};
void slv() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
bfs();
f[0] = 0;
for (int i = 1, j = 1; i <= m; i++) {
while (j < n && c[j + 1] <= i)
j++;
f[i] = f[i - c[j]] + 1;
}
for (int i = 1; i <= m; i++)
if (f[i] != d[i]) {
// cout << i << " " << f[i] << " " << d[i] << endl;
printf("NE\n");
return;
}
printf("DA\n");
}
int main() {
int T;
scanf("%d", &T);
while (T--)
slv();
return 0;
}
/*
3
3
1 2 5
4
1 3 8 13
4
1 3 4 10
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 120ms
memory: 4488kb
input:
100 10 1 2 3 12 13 22 23 33 43 53 10 1 6 15 20 23 29 30 39 40 45 10 1 2 3 4 6 8 14 18 28 38 10 1 2 4 5 8 11 14 23 32 41 10 1 2 3 4 7 11 16 20 29 38 10 1 2 3 5 6 7 11 16 25 34 10 1 2 3 4 5 6 7 9 10 15 10 1 7 16 21 28 38 47 53 62 67 10 1 4 5 12 17 19 29 30 33 36 10 1 2 3 4 5 7 9 11 13 19 10 1 2 3 4 5 ...
output:
DA NE DA DA DA DA DA NE NE DA DA NE DA DA DA NE DA NE DA NE NE NE DA DA DA NE NE NE DA NE DA NE DA DA DA NE DA NE DA DA NE DA NE NE NE DA NE NE NE DA NE DA NE DA DA DA DA NE NE DA DA DA DA NE NE NE NE NE DA DA DA DA NE NE NE NE DA NE NE NE DA DA NE DA NE NE NE NE NE DA NE NE NE NE DA DA DA DA DA DA
result:
ok 100 lines
Test #2:
score: 0
Accepted
time: 121ms
memory: 4524kb
input:
100 10 1 2 3 4 5 6 7 8 9 11 10 1 7 14 21 28 35 42 49 56 63 10 1 10 17 22 26 29 36 38 45 46 10 1 6 12 15 19 26 33 39 43 49 10 1 5 14 18 26 35 42 47 56 59 10 1 2 4 6 10 12 20 22 30 40 10 1 2 3 5 7 9 11 13 17 25 10 1 5 9 18 27 36 45 54 63 72 10 1 7 10 13 18 26 33 43 46 54 10 1 2 3 4 6 7 8 13 22 31 10 1...
output:
DA DA NE NE NE DA DA DA NE DA NE DA DA DA NE NE NE DA DA DA DA DA NE DA DA DA DA NE NE DA DA DA DA NE DA NE NE NE DA NE DA DA DA NE NE DA NE NE NE DA DA NE NE DA NE NE DA DA NE NE DA NE DA DA DA DA NE NE NE NE DA NE NE DA DA NE DA NE DA DA DA NE DA DA NE NE NE NE DA NE DA DA NE DA NE NE NE NE NE NE
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 121ms
memory: 4488kb
input:
100 10 1 2 3 5 6 9 12 15 18 27 10 1 2 4 5 8 11 12 15 22 32 10 1 9 19 20 23 26 30 36 37 44 10 1 3 10 19 24 27 29 31 33 36 10 1 3 5 13 23 33 43 53 63 73 10 1 2 3 4 5 7 12 22 32 42 10 1 2 3 5 13 23 33 43 53 63 10 1 6 7 17 20 25 31 36 39 47 10 1 6 11 16 18 23 33 37 43 45 10 1 10 14 20 24 34 35 44 47 49 ...
output:
DA DA NE NE DA DA DA NE NE NE DA NE NE NE NE NE DA DA NE DA NE DA DA NE NE NE NE NE DA NE DA DA DA NE DA DA NE DA DA DA NE DA NE DA DA NE NE DA NE DA NE NE DA DA DA DA NE DA DA DA NE DA DA DA DA DA DA NE NE NE DA NE DA DA NE NE DA DA DA NE DA DA NE DA DA DA NE DA NE NE NE NE NE NE DA DA NE NE DA DA
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 10ms
memory: 4520kb
input:
12 1 1 2 1 2 2 1 3 2 1 4 2 1 5 2 1 100 2 1 10000 3 1 5 18 3 1 10 100 5 1 2 10 11 20 5 1 2 5000 5001 10000 19 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
output:
DA DA DA DA DA DA DA DA DA DA DA DA
result:
ok 12 lines
Test #5:
score: 0
Accepted
time: 848ms
memory: 4628kb
input:
8 9367 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
DA NE NE NE NE NE NE DA
result:
ok 8 lines
Test #6:
score: 0
Accepted
time: 854ms
memory: 4620kb
input:
11 2279 1 4 6 8 11 13 17 21 22 26 29 31 33 35 37 38 39 40 41 44 48 52 53 55 57 58 59 61 65 69 73 75 78 79 82 84 88 89 92 95 98 99 101 103 104 106 110 112 113 117 119 123 124 128 130 134 136 139 140 141 145 146 147 148 150 152 153 155 157 161 164 165 169 170 171 172 173 176 178 180 181 182 185 187 19...
output:
NE NE NE NE NE NE NE NE NE NE DA
result:
ok 11 lines
Test #7:
score: 0
Accepted
time: 854ms
memory: 4828kb
input:
13 8878 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
DA NE NE NE NE NE NE NE DA NE DA DA DA
result:
ok 13 lines
Test #8:
score: 0
Accepted
time: 70ms
memory: 4440kb
input:
10 59 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 80 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100 103 106 109 112 115 118...
output:
DA DA DA DA DA DA DA DA DA DA
result:
ok 10 lines
Test #9:
score: 0
Accepted
time: 92ms
memory: 4528kb
input:
100 6 1 9 54 270 1620 6480 5 1 9 81 891 6237 5 1 9 99 990 2970 6 1 3 30 120 1080 9720 6 1 9 36 216 432 1296 5 1 7 63 630 6300 6 1 2 10 80 880 7920 5 1 10 80 720 7200 5 1 6 24 144 1584 5 1 11 88 704 4224 6 1 6 12 108 756 7560 5 1 10 80 800 3200 5 1 4 36 216 2376 5 1 8 88 616 3080 5 1 8 80 800 6400 5 ...
output:
DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA DA
result:
ok 100 lines
Test #10:
score: 0
Accepted
time: 840ms
memory: 4572kb
input:
1 10000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
DA
result:
ok single line: 'DA'
Test #11:
score: 0
Accepted
time: 1ms
memory: 4776kb
input:
1 3 1 9999 10000
output:
NE
result:
ok single line: 'NE'
Extra Test:
score: 0
Extra Test Passed