Submission #1168358
Source Code Expand
#include <iostream> using ll = long long; int n, k; int a[5010]; bool stat[5010]; ll dp[5010][5100]; ll dfs(int idx, ll sum) { if(sum >= k) { return sum; } if(idx >= n) { return 0; } if(dp[idx][sum] != -1) { return dp[idx][sum]; } ll min = 1e18; for(int i = idx; i < n; ++i) { auto r = dfs(i + 1, sum + a[i]); if(r != 0) { if(r - a[i] < k) { // std::cout << idx << " " << i << " " << sum << " " << r << std::endl; stat[i] = true; } min = std::min(min, r); } } if(min == 1e18) { return dp[idx][sum] = 0; } return dp[idx][sum] = min; } int main() { memset(dp, -1, sizeof(dp)); std::cin >> n >> k; for(int i = 0; i < n; ++i) std::cin >> a[i]; dfs(0, 0); int cnt = 0; for(int i = 0; i < n; ++i) { if(stat[i]) ++cnt; } std::cout << n - cnt << std::endl; }
Submission Info
Submission Time | |
---|---|
Task | D - No Need |
User | tsuzu |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1047 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:41:30: error: ‘memset’ was not declared in this scope memset(dp, -1, sizeof(dp)); ^