Submission #1593561

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#pragma comment(linker, "/STACK:336777216")  

using namespace std;

const int MAXN = 5000 + 10;
const int MAXK = 5000 + 10;

int N, K;
int A[MAXK];
bool DP1[MAXN][MAXK], DP2[MAXN][MAXK];

const int MAXTREE = MAXK;
const int TREEBASE = 1;
int Tree[MAXTREE];
void Modify(int p, int val)
{
	p += TREEBASE;
	for (; p < MAXTREE; p += p & (-p))
		Tree[p] += val;
}
int GetSum(int p)
{
	p += TREEBASE;
	int Ret = 0;
	for (; p > 0; p -= p & (-p))
		Ret += Tree[p];
	return Ret;
}

void Work()
{
	scanf("%d%d", &N, &K);
	long long Sum = 0;
	for (int i = 1; i <= N; i ++)
		scanf("%d", &A[i]);
	
	DP1[0][0] = 1;
	for (int i = 0; i < N; i ++)
		for (int j = 0; j <= K; j ++)
			if (DP1[i][j])
				DP1[i + 1][j] = DP1[i + 1][min(j + A[i + 1], K)] = 1;
	DP2[N + 1][0] = 1;
	for (int i = N + 1; i > 1; i --)
		for (int j = 0; j <= K; j ++)
			if (DP2[i][j])
				DP2[i - 1][j] = DP2[i - 1][min(j + A[i - 1], K)] = 1;
	int Ans = 0;
	for (int i = 1; i <= N; i ++)
	{
		if (A[i] >= K)
			continue;
		int L = K - A[i];
		int R = K - 1;

		for (int j = 0; j <= K; j ++)
			if (DP1[i - 1][j])
				Modify(j, 1);
		
		int unnecessary = 1;
		for (int j = 0; j < K; j ++)
			if (DP2[i + 1][j])
			{
				// [L - j, R - j]
				int l = max(L - j, 0);
				int r = R - j;
				if (GetSum(r) - GetSum(l - 1) != 0)
					unnecessary = 0;
			}
		Ans += unnecessary;

		for (int j = 0; j <= K; j ++)
			if (DP1[i - 1][j])
				Modify(j, -1);
	}
	printf("%d\n", Ans);
}

int main()
{
	Work();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void Work()’:
./Main.cpp:40:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
                       ^
./Main.cpp:43:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
                     ^

Judge Result