Submission #1603950


Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define MP(a,b) make_pair(a,b)
typedef long long LL;
typedef pair<int, int> PI;
typedef vector<int> VI;
typedef pair<double, int> P;
const LL MOD = 1000000007LL;
int a[5000];
int dp[5000][5000];
bool check(int N,int K,int x) {
	vector<int> v;
	rep(i, N) {
		if (i != x) v.push_back(a[i]);
	}
	fill((int*)dp, (int*)(dp + 5000), 0);
	dp[0][0] = 1;
	if (v[0] < K) dp[0][v[0]] = 1;
	REP(i, 1, N - 1) {
		rep(j, K) {
			dp[i][j] = dp[i - 1][j];
			if (v[i] < j) dp[i][j] |= dp[i - 1][j - v[i]];
		}
	}
	bool OK = 0;
	REP(i, K - a[x], K) {
		OK |= dp[N - 2][i];
	}
	return OK;
}
int main() {
	int N, K;
	cin >> N >> K;
	rep(i, N) cin >> a[i];
	if (N == 1) {
		if (a[0] < K) cout << 1 << endl;
		else cout << 0 << endl;
		return 0;
	}
	sort(a, a + N);
	int l = -1, r = N; //(l,r]
	while (r - l > 1) {
		int m = (l + r) / 2;
		if (check(N,K,m)) r = m;
		else l = m;
	}
	if (check(N, K, r)) {
		cout << r << endl;
	}
	else {
		cout << N << endl;
	}
}

Submission Info

Submission Time
Task D - No Need
User Div9851
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1157 Byte
Status RE
Exec Time 631 ms
Memory 98048 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 0 / 300 0 / 300
Status
AC × 3
AC × 24
RE × 2
AC × 47
RE × 4
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 52 ms 97920 KB
0_001.txt AC 62 ms 97920 KB
0_002.txt AC 62 ms 97920 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 73 ms 97920 KB
1_007.txt AC 62 ms 97920 KB
1_008.txt AC 119 ms 97920 KB
1_009.txt AC 131 ms 97920 KB
1_010.txt RE 123 ms 97920 KB
1_011.txt RE 124 ms 97920 KB
1_012.txt AC 119 ms 97920 KB
1_013.txt AC 118 ms 97920 KB
1_014.txt AC 118 ms 97920 KB
1_015.txt AC 119 ms 97920 KB
1_016.txt AC 74 ms 97920 KB
1_017.txt AC 62 ms 97920 KB
1_018.txt AC 74 ms 97920 KB
1_019.txt AC 130 ms 97920 KB
1_020.txt AC 118 ms 97920 KB
1_021.txt AC 119 ms 97920 KB
1_022.txt AC 107 ms 97920 KB
1_023.txt AC 107 ms 97920 KB
1_024.txt AC 130 ms 97920 KB
1_025.txt AC 130 ms 97920 KB
2_026.txt AC 1 ms 256 KB
2_027.txt AC 85 ms 97920 KB
2_028.txt AC 73 ms 97920 KB
2_029.txt AC 588 ms 97920 KB
2_030.txt AC 631 ms 97920 KB
2_031.txt RE 141 ms 97920 KB
2_032.txt RE 126 ms 97920 KB
2_033.txt AC 385 ms 97920 KB
2_034.txt AC 164 ms 97920 KB
2_035.txt AC 164 ms 97920 KB
2_036.txt AC 487 ms 97920 KB
2_037.txt AC 74 ms 97920 KB
2_038.txt AC 63 ms 97920 KB
2_039.txt AC 74 ms 97920 KB
2_040.txt AC 371 ms 97920 KB
2_041.txt AC 336 ms 97920 KB
2_042.txt AC 423 ms 97920 KB
2_043.txt AC 295 ms 97920 KB
2_044.txt AC 336 ms 97920 KB
2_045.txt AC 233 ms 97920 KB
2_046.txt AC 347 ms 97920 KB
2_047.txt AC 408 ms 97920 KB
2_048.txt AC 479 ms 98048 KB
2_049.txt AC 458 ms 97920 KB
2_050.txt AC 446 ms 97920 KB