QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #30865 | #3632. Izvanredna Isplata | zyy | WA | 6ms | 3576kb | C++11 | 1.4kb | 2022-05-01 18:36:41 | 2022-05-01 18:36:42 |
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<=mx+1;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<=mx+1;j++)f[j]=min(f[j],f[j-a[i]]+1);
bool fl=true;
for(int i=mx+1;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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 3576kb
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: 6ms
memory: 3576kb
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: -100
Wrong Answer
time: 1ms
memory: 3572kb
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 DA 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 DA NE DA DA NE NE DA DA
result:
wrong answer 4th lines differ - expected: 'NE', found: 'DA'