QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #30863 | #3632. Izvanredna Isplata | zyy | AC ✓ | 444ms | 3680kb | C++11 | 1.4kb | 2022-05-01 18:31:30 | 2022-05-01 18:31:33 |
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()
{
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: 1ms
memory: 3564kb
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: 3ms
memory: 3664kb
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: 3456kb
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: 3ms
memory: 3680kb
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: 413ms
memory: 3672kb
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: 24ms
memory: 3652kb
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: 353ms
memory: 3648kb
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: 5ms
memory: 3580kb
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: 35ms
memory: 3532kb
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: 444ms
memory: 3568kb
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: 3ms
memory: 3680kb
input:
1 3 1 9999 10000
output:
NE
result:
ok single line: 'NE'
Extra Test:
score: 0
Extra Test Passed