Submission #1966286


Source Code Expand

/*  ***  In The Name of God ... ***  */ 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;


//#define int long long
#define all(v) v.begin() , v.end()
#define pb push_back
#define endl '\n' 
template<typename T> inline bool smin(T &a, const T &b){ return b < a ? a = b,1:0;}
template<typename T> inline bool smax(T &a, const T &b){ return a < b ? a = b,1:0;}

const int N = 5000 + 10 ;

int n , a [ N ] , k ; 
bool dp [ N ] ;

bool chk ( int mid ) {
	memset ( dp , 0 , sizeof dp ) ;
	dp [ 0 ] = 1 ;
	for ( int i = 1 ; i <= n ; i++ ) {
		if ( i == mid )
			continue ; 
		for ( int j = N - 1 ; j >= a [ i ] ; j-- ) {
			dp [ j ] |= dp [ j - a [ i ] ] ; 
		}
	}
	bool isFound = 0 ;
	for ( int i = max ( 0 , k - a [ mid ] ) ; i < k ; i++ )
		isFound |= dp [ i ] ;
	return !isFound ; 
}

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k ; 
	for ( int i = 1 ; i <= n ; i++ )
		cin >> a [ i ] ;
	sort ( a + 1 , a + n + 1 ) ; 
	int lo = -1 , hi = n + 1 ;
	while ( hi - lo > 1 ) {
		int mid = ( hi + lo ) >> 1 ; 
		( chk ( mid ) ? lo : hi ) = mid ; 
	}
	cout << lo << '\n' ; 
}

Submission Info

Submission Time
Task D - No Need
User Nima10Khodaveisi
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1208 Byte
Status AC
Exec Time 214 ms
Memory 384 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 300 / 300 300 / 300
Status
AC × 3
AC × 26
AC × 51
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 13 ms 256 KB
1_009.txt AC 13 ms 256 KB
1_010.txt AC 1 ms 256 KB
1_011.txt AC 1 ms 256 KB
1_012.txt AC 12 ms 256 KB
1_013.txt AC 12 ms 256 KB
1_014.txt AC 13 ms 256 KB
1_015.txt AC 13 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 11 ms 256 KB
1_020.txt AC 13 ms 256 KB
1_021.txt AC 13 ms 256 KB
1_022.txt AC 4 ms 256 KB
1_023.txt AC 3 ms 256 KB
1_024.txt AC 13 ms 256 KB
1_025.txt AC 13 ms 256 KB
2_026.txt AC 1 ms 256 KB
2_027.txt AC 1 ms 256 KB
2_028.txt AC 1 ms 256 KB
2_029.txt AC 198 ms 256 KB
2_030.txt AC 214 ms 256 KB
2_031.txt AC 2 ms 256 KB
2_032.txt AC 2 ms 256 KB
2_033.txt AC 2 ms 256 KB
2_034.txt AC 2 ms 256 KB
2_035.txt AC 101 ms 256 KB
2_036.txt AC 101 ms 256 KB
2_037.txt AC 1 ms 256 KB
2_038.txt AC 1 ms 256 KB
2_039.txt AC 1 ms 256 KB
2_040.txt AC 3 ms 256 KB
2_041.txt AC 148 ms 256 KB
2_042.txt AC 121 ms 256 KB
2_043.txt AC 66 ms 256 KB
2_044.txt AC 96 ms 256 KB
2_045.txt AC 100 ms 256 KB
2_046.txt AC 108 ms 256 KB
2_047.txt AC 102 ms 256 KB
2_048.txt AC 100 ms 384 KB
2_049.txt AC 80 ms 256 KB
2_050.txt AC 73 ms 256 KB