Submission #1757404


Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e9

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll n, k, x, ans;
vector <ll> a;
bool can_reach[5001];

void upper_bound(){
	int lo, mid, hi;
	bool pos;
	lo = 0;
	hi = n-1;
	while(lo<=hi){
		mid=lo+(hi-lo)/2;
		for(int i = 0; i < n; i++){
			if(i!=mid){
				for(int j = k-1; j >= a[i]; j--){
					can_reach[j]=can_reach[j]|can_reach[j-a[i]];
				}
			}
		}
		pos=0;
		for(int i = k-1; i >= k-a[mid] && i >= 0; i--){
			if(can_reach[i]){
				pos=1;
			}
		}
		for(int i = 1; i <= k; i++){
			can_reach[i]=0;
		}
		if(!pos){
			ans=mid;
			lo=mid+1;
		}
		else{
			hi=mid-1;
		}
	}
}

int main()
{
	ans=-1;
	can_reach[0]=1;
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> x;
		a.pb(x);
	}
	sort(a.begin(),a.end());
	upper_bound();
	cout << ans+1;
	return 0;
}

Submission Info

Submission Time
Task D - No Need
User vjudge5
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1366 Byte
Status AC
Exec Time 230 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 2 ms 256 KB
1_009.txt AC 2 ms 256 KB
1_010.txt AC 1 ms 256 KB
1_011.txt AC 1 ms 256 KB
1_012.txt AC 1 ms 256 KB
1_013.txt AC 1 ms 256 KB
1_014.txt AC 1 ms 256 KB
1_015.txt AC 2 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 1 ms 256 KB
1_020.txt AC 1 ms 256 KB
1_021.txt AC 2 ms 256 KB
1_022.txt AC 1 ms 256 KB
1_023.txt AC 1 ms 256 KB
1_024.txt AC 2 ms 256 KB
1_025.txt AC 2 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 212 ms 384 KB
2_030.txt AC 230 ms 384 KB
2_031.txt AC 4 ms 384 KB
2_032.txt AC 4 ms 384 KB
2_033.txt AC 3 ms 384 KB
2_034.txt AC 3 ms 384 KB
2_035.txt AC 3 ms 384 KB
2_036.txt AC 108 ms 384 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 384 KB
2_041.txt AC 58 ms 384 KB
2_042.txt AC 88 ms 384 KB
2_043.txt AC 49 ms 256 KB
2_044.txt AC 60 ms 384 KB
2_045.txt AC 29 ms 256 KB
2_046.txt AC 59 ms 384 KB
2_047.txt AC 83 ms 384 KB
2_048.txt AC 105 ms 384 KB
2_049.txt AC 84 ms 384 KB
2_050.txt AC 71 ms 384 KB