AtCoder Beginner Contest 056

Submission #1337159

Source codeソースコード

#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

Task問題 D - No Need
User nameユーザ名 gazelle
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 600
Source lengthソースコード長 1459 Byte
File nameファイル名
Exec time実行時間 175 ms
Memory usageメモリ使用量 512 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_000.txt,0_001.txt,0_002.txt
Subtask 300 / 300 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 300 / 300 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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