Submission #1337159


Source Code Expand

#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF (long long)1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int dh[4] = {1, 0, -1, 0};
int dw[4] = {0, 1, 0, -1};

vector<ll> dp;
vector<vector<ll> > dp2(2);

ll rec(int d, int roc, int s) {
	if(dp2[d][roc] != -1) return dp2[d][roc];
	if(roc < s) {
		if(d == 0) return dp2[0][roc] = 0;
		else return dp2[1][roc] = dp[roc];
	} else {
		if(d == 0) return dp2[0][roc] = rec(1, roc - s, s);
		else return dp2[1][roc] = dp[roc] - rec(1, roc - s, s);
	}
}

int main(void) {
	int n, k;
	cin>>n>>k;
	vector<ll> a(n);
	REP(i, n) cin>>a[i];
	dp.resize(k);
	dp[0] = 1;
	REP(i, n) {
		REP(j, k) {
			if((k - 1 - j) - a[i] >= 0) dp[(k - 1 - j)] += dp[(k - 1 - j) - a[i]];
		}
	}
	ll cnt = 0;
	REP(i, n) {
		if(a[i] >= k) {
			++cnt;
			continue;
		}
		dp2[0].resize(0);
		dp2[0].resize(k);
		dp2[1].resize(0);
		dp2[1].resize(k);
		REP(j, k) dp2[0][j] = dp2[1][j] = -1;
		FOR(j, k - a[i], k) {
			if(rec(1, (int)j, (int)a[i]) != 0) {
				++cnt;
				break;
			}
		}
	}
	cout<<n - cnt<<endl;
}

Submission Info

Submission Time
Task D - No Need
User gazelle
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1459 Byte
Status AC
Exec Time 175 ms
Memory 512 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 1 ms 256 KB
1_022.txt AC 1 ms 256 KB
1_023.txt AC 1 ms 256 KB
1_024.txt AC 1 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 175 ms 512 KB
2_030.txt AC 173 ms 512 KB
2_031.txt AC 20 ms 384 KB
2_032.txt AC 3 ms 256 KB
2_033.txt AC 19 ms 384 KB
2_034.txt AC 2 ms 256 KB
2_035.txt AC 2 ms 256 KB
2_036.txt AC 89 ms 512 KB
2_037.txt AC 2 ms 512 KB
2_038.txt AC 1 ms 512 KB
2_039.txt AC 2 ms 512 KB
2_040.txt AC 16 ms 512 KB
2_041.txt AC 38 ms 384 KB
2_042.txt AC 67 ms 512 KB
2_043.txt AC 41 ms 512 KB
2_044.txt AC 36 ms 384 KB
2_045.txt AC 14 ms 384 KB
2_046.txt AC 44 ms 384 KB
2_047.txt AC 70 ms 512 KB
2_048.txt AC 90 ms 512 KB
2_049.txt AC 77 ms 512 KB
2_050.txt AC 69 ms 512 KB