Submission #1167860


Source Code Expand

#include<bits/stdc++.h>
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define sci(x) scanf("%d",&x)
#define scs(s) scanf("%s",s)
#define scc(c) scanf("%c",c)
#define scd(d) scanf("%lf",&d)
#define scld(ld) scanf("%Lf",&ld)
using namespace std;

//********************************************
//Error tracking
#define show(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }

vector<string> split(const string& s, char c) {
    vector<string> v;
    stringstream ss(s);
    string x;
    while (getline(ss, x, c))
        v.emplace_back(x);
    return move(v);
}

void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
    cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
    err(++it, args...);
}
//********************************************

const int NMAX = 5005;

int n, k, a[NMAX];
bitset<NMAX>pref[NMAX], suf[NMAX];
int sum[2][NMAX];

void Knapsack()
{
	int i, j;

	//prefix
	pref[0][0] = 1;
	for (i = 1; i <= n; i++)
		for (j = 0; j < NMAX; j++)
		{
			pref[i][j] = pref[i - 1][j];
			if (j >= a[i] && pref[i - 1][j - a[i]])
				pref[i][j] = 1;
		}

	//sufix
	suf[n + 1][0] = 1;
	for (i = n ; i >= 1; i--)
		for (j = 0; j < NMAX; j++)
		{
			suf[i][j] = suf[i + 1][j];
			if (j >= a[i] && suf[i + 1][j - a[i]])
				suf[i][j] = 1;
		}
}

int main()
{
  //  freopen("input","r",stdin);
  //  freopen("output","w",stdout);
    cin.sync_with_stdio(false);
	
	int i;
	cin >> n >> k;
	for (i = 1; i <= n; i++) cin >> a[i];

	Knapsack();
	
	//answer
	int j, ans = 0;
	for (i = 1; i <= n; i++)
	{
		int st = max(0, k - a[i]), dr = k - 1; //the interval to search

		//partial sums
		for (j = 0; j < NMAX; j++) 
			{
				sum[0][j] = pref[i - 1][j];
				sum[1][j] = suf[i + 1][j];
			}

		for (j = 1; j < NMAX; j++)
			for (int l = 0; l <= 1; l++)
				sum[l][j] += sum[l][j - 1];


		bool ok = 0;
		for (j = 0; j <= dr; j++)
			if (pref[i - 1][j] != 0) //search for other
			{
				int left = max(0, st - j), right = dr - j;

				int minus = 0;
				if (left > 0) minus = sum[1][left - 1];
				if (sum[1][right] - minus > 0) ok = 1;
			}

		if (!ok) ans++;
	}	
	cout << ans << "\n";
	
    return 0;   
}

Submission Info

Submission Time
Task D - No Need
User Archazey
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2483 Byte
Status AC
Exec Time 306 ms
Memory 6528 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 2 ms 2304 KB
0_001.txt AC 2 ms 2304 KB
0_002.txt AC 2 ms 2304 KB
1_003.txt AC 2 ms 2304 KB
1_004.txt AC 2 ms 2304 KB
1_005.txt AC 2 ms 2304 KB
1_006.txt AC 2 ms 2304 KB
1_007.txt AC 2 ms 2304 KB
1_008.txt AC 21 ms 2560 KB
1_009.txt AC 21 ms 2560 KB
1_010.txt AC 18 ms 2560 KB
1_011.txt AC 18 ms 2560 KB
1_012.txt AC 21 ms 2560 KB
1_013.txt AC 21 ms 2560 KB
1_014.txt AC 25 ms 2560 KB
1_015.txt AC 26 ms 2560 KB
1_016.txt AC 2 ms 2304 KB
1_017.txt AC 2 ms 2304 KB
1_018.txt AC 2 ms 2304 KB
1_019.txt AC 22 ms 2560 KB
1_020.txt AC 22 ms 2560 KB
1_021.txt AC 25 ms 2560 KB
1_022.txt AC 11 ms 2432 KB
1_023.txt AC 8 ms 2432 KB
1_024.txt AC 23 ms 2560 KB
1_025.txt AC 23 ms 2560 KB
2_026.txt AC 2 ms 2304 KB
2_027.txt AC 3 ms 2304 KB
2_028.txt AC 3 ms 2432 KB
2_029.txt AC 306 ms 6528 KB
2_030.txt AC 306 ms 6528 KB
2_031.txt AC 232 ms 6528 KB
2_032.txt AC 208 ms 6528 KB
2_033.txt AC 232 ms 6528 KB
2_034.txt AC 208 ms 6528 KB
2_035.txt AC 254 ms 6528 KB
2_036.txt AC 303 ms 6528 KB
2_037.txt AC 2 ms 2304 KB
2_038.txt AC 2 ms 2304 KB
2_039.txt AC 2 ms 2304 KB
2_040.txt AC 234 ms 6528 KB
2_041.txt AC 302 ms 6528 KB
2_042.txt AC 303 ms 6528 KB
2_043.txt AC 184 ms 6272 KB
2_044.txt AC 247 ms 6400 KB
2_045.txt AC 227 ms 6400 KB
2_046.txt AC 250 ms 6528 KB
2_047.txt AC 264 ms 6528 KB
2_048.txt AC 275 ms 6528 KB
2_049.txt AC 269 ms 6528 KB
2_050.txt AC 265 ms 6528 KB