QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #30903 | #3632. Izvanredna Isplata | DoorKickers | AC ✓ | 434ms | 3804kb | C++20 | 1.5kb | 2022-05-02 00:33:25 | 2022-05-02 00:33:28 |
Judging History
answer
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=20005;
int n,f[N],a[N],t;
int main()
{
// freopen("a3.in", "r", stdin);
// freopen("a3.out", "w", stdout);
for(cin>>t;t;t--)
{
cin>>n;
int mx=0;
for(int i=1;i<=n;i++)cin>>a[i],mx=max(mx,a[i]);
for(int i=0;i<=2*mx;i++)f[i]=0x3f3f3f3f;
sort(a+1,a+1+n);
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=a[i];j<=2*mx;j++)f[j]=min(f[j],f[j-a[i]]+1);
bool fl=true;
for(int i=2*mx;i>=1;i--)
{
fl=true;
int pos=upper_bound(a+1,a+1+n,i)-a-1;
int j=i;
int res=0;
while(j&&pos>=1)
{
res+=j/a[pos];
j-=j/a[pos]*a[pos];
pos--;
}
if(res>f[i])
{
fl=false;
break;
}
}
puts(fl?"DA":"NE");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 3632kb
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: 5ms
memory: 3568kb
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: 6ms
memory: 3664kb
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: 0ms
memory: 3804kb
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: 382ms
memory: 3704kb
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: 15ms
memory: 3724kb
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: 341ms
memory: 3688kb
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: 6ms
memory: 3528kb
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: 34ms
memory: 3640kb
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: 434ms
memory: 3708kb
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: 3532kb
input:
1 3 1 9999 10000
output:
NE
result:
ok single line: 'NE'
Extra Test:
score: 0
Extra Test Passed