AtCoder Beginner Contest 032

Submission #6912618

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;

int main() {
  ll N,W;
  cin >> N >> W;
  ll INF = 100000000000000;
  vector<ll> weight(110);
  vector<ll> value(110);
  vector<vector<ll>> dp(110, vector<ll>(100100,INF));
  
  for(ll i = 0;i<N;i++){
    cin >> value[i];
    cin >> weight[i];
  }
dp[0][0] = 0;
  rep(i,N){
    rep(sum_v,100100){
      if(sum_v-value[i] >=0){
        chmin(dp[i+1][sum_v],dp[i][sum_v-value[i]]+weight[i]);
      }
      chmin(dp[i+1][sum_v],dp[i][sum_v]);
    }
  }
    ll res = 0;
  for(ll sum_v = 0;sum_v<100100;sum_v++){
    if(dp[N][sum_v]<=W){
      res = max(res,sum_v);
    }
  }
  
cout << res << endl;
  
}

Submission

Task問題 D - ナップサック問題
User nameユーザ名 ysdYSD
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 0
Source lengthソースコード長 974 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask00_sample_1.txt,subtask00_sample_2.txt,subtask00_sample_3.txt,subtask00_sample_4.txt
Subtask1 0 / 34 subtask01_0.txt,subtask01_1.txt,subtask01_10.txt,subtask01_11.txt,subtask01_12.txt,subtask01_13.txt,subtask01_14.txt,subtask01_2.txt,subtask01_3.txt,subtask01_4.txt,subtask01_5.txt,subtask01_6.txt,subtask01_7.txt,subtask01_8.txt,subtask01_9.txt,subtask00_sample_1.txt,subtask00_sample_2.txt,subtask00_sample_3.txt,subtask00_sample_4.txt
Subtask2 0 / 33 subtask02_0.txt,subtask02_1.txt,subtask02_10.txt,subtask02_11.txt,subtask02_12.txt,subtask02_13.txt,subtask02_14.txt,subtask02_2.txt,subtask02_3.txt,subtask02_4.txt,subtask02_5.txt,subtask02_6.txt,subtask02_7.txt,subtask02_8.txt,subtask02_9.txt,subtask00_sample_1.txt,subtask00_sample_3.txt
Subtask3 0 / 33 subtask03_0.txt,subtask03_1.txt,subtask03_10.txt,subtask03_11.txt,subtask03_2.txt,subtask03_3.txt,subtask03_4.txt,subtask03_5.txt,subtask03_6.txt,subtask03_7.txt,subtask03_8.txt,subtask03_9.txt,subtask00_sample_1.txt,subtask00_sample_4.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask00_sample_1.txt AC 39 ms 87296 KB
subtask00_sample_2.txt WA
subtask00_sample_3.txt WA
subtask00_sample_4.txt AC 40 ms 87296 KB
subtask01_0.txt WA
subtask01_1.txt WA
subtask01_10.txt WA
subtask01_11.txt WA
subtask01_12.txt WA
subtask01_13.txt WA
subtask01_14.txt WA
subtask01_2.txt WA
subtask01_3.txt WA
subtask01_4.txt WA
subtask01_5.txt WA
subtask01_6.txt AC 43 ms 87296 KB
subtask01_7.txt WA
subtask01_8.txt WA
subtask01_9.txt WA
subtask02_0.txt RE
subtask02_1.txt RE
subtask02_10.txt RE
subtask02_11.txt RE
subtask02_12.txt RE
subtask02_13.txt RE
subtask02_14.txt RE
subtask02_2.txt RE
subtask02_3.txt RE
subtask02_4.txt RE
subtask02_5.txt RE
subtask02_6.txt RE
subtask02_7.txt RE
subtask02_8.txt RE
subtask02_9.txt RE
subtask03_0.txt RE
subtask03_1.txt RE
subtask03_10.txt RE
subtask03_11.txt RE
subtask03_2.txt RE
subtask03_3.txt RE
subtask03_4.txt RE
subtask03_5.txt RE
subtask03_6.txt RE
subtask03_7.txt RE
subtask03_8.txt RE
subtask03_9.txt RE