QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #30861 | #3632. Izvanredna Isplata | zyy | WA | 2ms | 3688kb | C++ | 1.4kb | 2022-05-01 18:30:16 | 2022-05-01 18:30:16 |
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=10005;
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?"YES":"NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3688kb
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:
YES NO YES YES YES YES YES NO NO YES YES NO YES YES YES NO YES NO YES NO NO NO YES YES YES NO NO NO YES NO YES NO YES YES YES NO YES NO YES YES NO YES NO NO NO YES NO NO NO YES NO YES NO YES YES YES YES NO NO YES YES YES YES NO NO NO NO NO YES YES YES YES NO NO NO NO YES NO NO NO YES YES NO YES NO N...
result:
wrong answer 1st lines differ - expected: 'DA', found: 'YES'