Submission #1349411
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define each(itr,v) for(auto itr:v) #define pb(s) push_back(s) #define mp(a,b) make_pair(a,b) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<x<<endl #define maxch(x,y) x=max(x,y) #define minch(x,y) x=min(x,y) #define uni(x) x.erase(unique(all(x)),x.end()) #define exist(x,y) (find(all(x),y)!=x.end()) #define bcnt(x) bitset<32>(x).count() typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> P; typedef pair<P, int> PPI; typedef pair<ll, ll> PL; typedef pair<P, ll> PPL; #define INF INT_MAX/3 #define MAX_N 1000 ll n,k,a[5005]; bool dp[5005]; bool ok(ll x){ memset(dp,0,sizeof(dp)); dp[0]=true; rep(i,n)for(ll j=k;j>=0;j--){ if(i==x)continue; if(j+a[i]<=k&&dp[j])dp[j+a[i]]=true; } repl(i,max(0LL,k-a[x]),k){ if(dp[i])return true; } return false; } int main(){ cin.sync_with_stdio(false); cin>>n>>k; rep(i,n)cin>>a[i]; sort(a,a+n); ll lb=-1,ub=n; rep(hoge,13){ ll mid=(lb+ub)/2; if(ok(mid))ub=mid; else lb=mid; } cout<<ub<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - No Need |
User | yamad |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1268 Byte |
Status | AC |
Exec Time | 425 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | 300 / 300 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt |
Subtask | 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 2_026.txt, 2_027.txt, 2_028.txt, 2_029.txt, 2_030.txt, 2_031.txt, 2_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 1 ms | 256 KB |
0_001.txt | AC | 1 ms | 256 KB |
0_002.txt | AC | 1 ms | 256 KB |
1_003.txt | AC | 1 ms | 256 KB |
1_004.txt | AC | 1 ms | 256 KB |
1_005.txt | AC | 1 ms | 256 KB |
1_006.txt | AC | 1 ms | 256 KB |
1_007.txt | AC | 1 ms | 256 KB |
1_008.txt | AC | 4 ms | 256 KB |
1_009.txt | AC | 4 ms | 256 KB |
1_010.txt | AC | 3 ms | 256 KB |
1_011.txt | AC | 1 ms | 256 KB |
1_012.txt | AC | 3 ms | 256 KB |
1_013.txt | AC | 1 ms | 256 KB |
1_014.txt | AC | 1 ms | 256 KB |
1_015.txt | AC | 4 ms | 256 KB |
1_016.txt | AC | 1 ms | 256 KB |
1_017.txt | AC | 1 ms | 256 KB |
1_018.txt | AC | 1 ms | 256 KB |
1_019.txt | AC | 3 ms | 256 KB |
1_020.txt | AC | 1 ms | 256 KB |
1_021.txt | AC | 3 ms | 256 KB |
1_022.txt | AC | 2 ms | 256 KB |
1_023.txt | AC | 1 ms | 256 KB |
1_024.txt | AC | 3 ms | 256 KB |
1_025.txt | AC | 3 ms | 256 KB |
2_026.txt | AC | 1 ms | 256 KB |
2_027.txt | AC | 2 ms | 256 KB |
2_028.txt | AC | 2 ms | 256 KB |
2_029.txt | AC | 425 ms | 256 KB |
2_030.txt | AC | 425 ms | 256 KB |
2_031.txt | AC | 319 ms | 256 KB |
2_032.txt | AC | 2 ms | 256 KB |
2_033.txt | AC | 319 ms | 256 KB |
2_034.txt | AC | 2 ms | 256 KB |
2_035.txt | AC | 2 ms | 256 KB |
2_036.txt | AC | 373 ms | 256 KB |
2_037.txt | AC | 2 ms | 256 KB |
2_038.txt | AC | 2 ms | 256 KB |
2_039.txt | AC | 2 ms | 256 KB |
2_040.txt | AC | 262 ms | 256 KB |
2_041.txt | AC | 197 ms | 256 KB |
2_042.txt | AC | 300 ms | 384 KB |
2_043.txt | AC | 181 ms | 256 KB |
2_044.txt | AC | 200 ms | 256 KB |
2_045.txt | AC | 101 ms | 256 KB |
2_046.txt | AC | 186 ms | 256 KB |
2_047.txt | AC | 284 ms | 256 KB |
2_048.txt | AC | 365 ms | 256 KB |
2_049.txt | AC | 353 ms | 256 KB |
2_050.txt | AC | 347 ms | 256 KB |