Submission #1870716
Source Code Expand
#include <iostream> #include <algorithm> #include <vector> #include <string> #include <set> #include <stack> #include <queue> using namespace std; long long n,W,v[101],w[101],dp[101][1000001]; long long solve(long long i,long long sum){ if(sum<0)return 0; if(i==n)return 0; if(dp[i][W-sum]!=0)return dp[i][W-sum]; else{ dp[i][W-sum]=solve(i+1,sum); if(sum-w[i]>=0){ dp[i][W-sum]=max(solve(i+1,sum),solve(i+1,sum-w[i])+v[i]); } return dp[i][W-sum]; } } int main(void){ cin>>n>>W; for(int i=0;i<n;i++){ cin>>w[i]>>v[i]; } cout<<solve(0,W)<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Simple Knapsack |
User | Hirosesesese23 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 683 Byte |
Status | RE |
Exec Time | 97 ms |
Memory | 164224 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 400 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2, example3 |
All | antigreedy0, antigreedy1, antigreedy2, example0, example1, example2, example3, quarter0, quarter1, quarter2, rand0, rand1, rand2, smallw0, smallw1, smallw2 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
antigreedy0 | RE | 97 ms | 4352 KB |
antigreedy1 | RE | 97 ms | 4352 KB |
antigreedy2 | RE | 97 ms | 4352 KB |
example0 | AC | 2 ms | 6400 KB |
example1 | AC | 2 ms | 6400 KB |
example2 | AC | 2 ms | 6400 KB |
example3 | AC | 2 ms | 6400 KB |
quarter0 | AC | 60 ms | 162304 KB |
quarter1 | AC | 35 ms | 162304 KB |
quarter2 | AC | 34 ms | 162304 KB |
rand0 | AC | 3 ms | 10496 KB |
rand1 | AC | 20 ms | 100608 KB |
rand2 | RE | 97 ms | 4352 KB |
smallw0 | AC | 33 ms | 162176 KB |
smallw1 | AC | 32 ms | 162176 KB |
smallw2 | AC | 37 ms | 164224 KB |