Submission #97419
Source Code Expand
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>
#include <bitset>
#include <cassert>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
// adjust problem by problem
const double EPS=1e-8;
const double PI=acos(-1.0);
#define REP(i,n) for(int i=0;i<(int)n;++i)
#ifdef __GNUC__
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
int popcount(int n){return __builtin_popcount(n);}
int popcount(ll n){return __builtin_popcountll(n);}
#endif
#ifndef __GNUC__
template<class T> int popcount(T val){
val = val - ((val >> 1) & 0x55555555);
val = (val & 0x33333333) + ((val >> 2) & 0x33333333);
val = (val + (val >> 4)) & 0x0f0f0f0f;
val += val >> 8;
val += val >> 16;
return (int)(val & 0x0000003f);
}
#endif
template<class T>int SIZE(T a){return a.size();}
template<class T>string IntToString(T num){string res;stringstream ss;ss<<num;return ss.str();}
template<class T>T StringToInt(string str){T res=0;for(int i=0;i<SIZE(str);i++)res=(res*10+str[i]-'0');return res;}
template<class T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<class T>T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> void PrintSeq(T &a,int sz){for(int i=0;i<sz;i++){cout<<a[i];if(sz==i+1)cout<<endl;else cout<<' ';}}
ll getTen(int a){return (a<=0)?1:(getTen(a-1)*10);}
bool EQ(double a,double b){return abs(a-b)<EPS;}
void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}
vector<string> split(string str,char del){
vector<string> res;
for(int i=0,s=0;i<SIZE(str);i++){
if(str[i]==del){if(i-s!=0)res.push_back(str.substr(s,i-s));s=i+1;}
else if(i==SIZE(str)-1){res.push_back(str.substr(s));}
}
return res;
}
struct TimeWatch{
clock_t start_,end_;
void start(){start_=clock();}
double stop(){return (double)(clock()-start_)/CLOCKS_PER_SEC;}
};
int dp[101][10001];
int N;
int ps[101];
int dfs(int pos,int sum){
if(dp[pos][sum]>=0)return dp[pos][sum];
if(pos==N)return sum==0;
else{
int res=0;
if(sum-ps[pos]>=0)
res|=dfs(pos+1,sum-ps[pos]);
res|=dfs(pos+1,sum);
return dp[pos][sum]=res;
}
}
int main(){
memset(dp,-1,sizeof(dp));
cin>>N;
for(int i=0;i<N;i++)cin>>ps[i];
int cnt=0;
for(int i=0;i<=10000;i++)
if(dfs(0,i))cnt++;
cout<<cnt<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - コンテスト |
User |
ishikado |
Language |
C++ (G++ 4.6.4) |
Score |
2 |
Code Size |
2729 Byte |
Status |
AC |
Exec Time |
56 ms |
Memory |
4772 KB |
Judge Result
Set Name |
All |
Score / Max Score |
2 / 2 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
AC |
34 ms |
4660 KB |
01 |
AC |
41 ms |
4676 KB |
02 |
AC |
56 ms |
4668 KB |
90 |
AC |
27 ms |
4672 KB |
91 |
AC |
32 ms |
4772 KB |