Submission #1230110

---

Source Code Expand

/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГИ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define zhfs main
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
#define re return
#define forn(i, n) for (int i = 1; i <= n; i++)
const int MX = 5007;
bool canl[MX][MX], canr[MX][MX];
int a[MX];
int near[MX][MX];
int zhfs()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	canl[0][0] = true;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < MX; j++)
		{
			if (canl[i][j])
			{
				canl[i + 1][j] = true;
				if (j + a[i + 1] < MX)
				{
					canl[i + 1][j + a[i + 1]] = true;
				}
			}
		}
	}
	for (int i = 0; i <= n; i++)
	{
		near[i][MX - 1] = MX * MX;
		for (int j = MX - 2; j >= 0; j--)
		{
			near[i][j] = near[i][j + 1];
			if (canl[i][j]) near[i][j] = j;
		}
	}
	canr[n + 1][0] = true;
	for (int i = n + 1; i >= 1; i--)
	{
		for (int j = 0; j < MX; j++)
		{
			if (canr[i][j])
			{
				canr[i - 1][j] = true;
				if (j + a[i - 1] < MX)
				{
					canr[i - 1][j + a[i - 1]] = true;
				}
			}
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++)
	{
		bool bad = false;
		for (int gor = 0; gor < MX; gor++)
		{
			if (!canr[i + 1][gor]) continue;
			int want = k - a[i] - gor;
			int can = near[i - 1][max(0, want)];
			if (gor + can >= k - a[i] && gor + can <= k - 1)
			{
				bad = true;
			//	cerr << i << " " << can << " " << gor << endl;
			}
		}
		if (!bad) res++;
	}
	printf("%d\n", res);
}

Submission Info

Judge Result