Typical DP Contest

Submission #5888838

Source codeソースコード

#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

template<typename T>
bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}

template<typename T>
bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

int dp[110][10100];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N=in();
	vector<int> A(N);
	REP(i,N){
		A[i]=in();
	}
	int sum = accumulate(ALL(A),0);
	dp[0][0] = 1;

	for(int i=0;i<N;i++){
		for(int k=0;k<10100;k++){
			if(dp[i][k]==1 && k+A[i]<10100) chmax(dp[i+1][k+A[i]],1);
			chmax(dp[i+1][k],dp[i][k]);
		}
	}

	cout << count(dp[N],dp[N]+sum+1,1) << endl;
	return 0;
}

Submission

Task問題 A - コンテスト
User nameユーザ名 zelosace
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 2
Source lengthソースコード長 872 Byte
File nameファイル名
Exec time実行時間 3 ms
Memory usageメモリ使用量 2816 KB

Test case

Set

Set name Score得点 / Max score Cases
All 2 / 2 00,01,02,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 1 ms 256 KB
01 AC 2 ms 768 KB
02 AC 3 ms 2816 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB