提交记录 6959


用户 题目 状态 得分 用时 内存 语言 代码长度
Wallbreaker5th noip18b. 【NOIP2018】货币系统 Accepted 100 19.747 ms 132 KB C++ 805 B
提交时间 评测时间
2018-11-24 14:11:33 2020-08-01 00:55:16
#include<bits/stdc++.h>
using namespace std;
inline int getint(){
    int ans=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        //if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans;
}

const int M=25010,N=110;

int f[M],a[N];

int main(){
    int t=getint(),n,mx=0;
    while(t--){
        n=getint();
        for(register int i=0;i<n;++i)mx=max(a[i]=getint(),mx);
        sort(a,a+n);
        memset(f,0,sizeof(f));
        f[0]=1;
        int ans=n;
        for(register int i=0;i<n;++i){
            if(f[a[i]]){
                --ans;
                continue;
            }
            for(register int j=a[i];j<=mx;j++)if(f[j-a[i]])f[j]=1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1105.11 us132 KBAcceptedScore: 5

Testcase #2108.89 us132 KBAcceptedScore: 5

Testcase #3111.07 us132 KBAcceptedScore: 5

Testcase #4129.25 us132 KBAcceptedScore: 5

Testcase #5115.51 us132 KBAcceptedScore: 5

Testcase #6107.64 us132 KBAcceptedScore: 5

Testcase #7117.72 us132 KBAcceptedScore: 5

Testcase #8117.96 us132 KBAcceptedScore: 5

Testcase #9128.17 us132 KBAcceptedScore: 5

Testcase #10133.77 us132 KBAcceptedScore: 5

Testcase #1194.24 us132 KBAcceptedScore: 5

Testcase #1293.7 us132 KBAcceptedScore: 5

Testcase #1395.38 us132 KBAcceptedScore: 5

Testcase #14104.05 us132 KBAcceptedScore: 5

Testcase #15106.7 us132 KBAcceptedScore: 5

Testcase #16106.91 us132 KBAcceptedScore: 5

Testcase #1719.51 ms132 KBAcceptedScore: 5

Testcase #1819.037 ms132 KBAcceptedScore: 5

Testcase #1919.425 ms132 KBAcceptedScore: 5

Testcase #2019.747 ms132 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 20:24:48 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用