提出詳細

ソースコード

#include <iostream>
#include <sstream>
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
#include <numeric>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<Pll> vp;
typedef vector<bool> vb;
#define rep(i, a, n) for (ll i = (a); i < (n); ++i)
#define rrep(i, a, n) for (ll i = (a); i > (n); --i)
#define erep(i, a, n) for (ll i = (a); i <= (n); ++i)
#define rerep(i, a, n) for (ll i = (a); i >= (n); --i)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define mp make_pair
#define sz(x) ((int)x.size())
#define SORT(x) sort(all(x))
#define RSORT(x) sort(all(x),greater<ll>())
#define vec_max(V) *max_element(all(V))
#define vec_min(V) *min_element(all(V))
#define vec_sum(V) accumulate(all(V), 0LL)
#define print(X) cout << (X) << "\n"
#define sprint(X) printf("%f\n", (X)) // 小数点の出力
#define _ << " " <<
#define Yes print("Yes")
#define No print("No")
#define case(X) cout << "Case #" << (X) + 1 << ":" << "\n"
static const int INF = 1e+9+7;

int main(){

  int T;
  cin >> T;

  for(int t=1; t<=T; t++){
    cout << "Case #" << t + 1 << ":" << "\n";

    int N,B;
    cin >> N >> B;

    vector<int> P(N), V(N);
    int dp[110][5010];
    int pdp[110][5010];

    for(int i=0; i < N; i++){
      cin >> P[i] >> V[i];
    }

    for (int p = 0; p <= B; ++p) dp[0][p] = 0;

    for (int i = 0; i < N; ++i) {
      for (int p = 0; p <= B; ++p) {
        if (p >= P[i] && (dp[i][p-P[i]] + V[i] >= dp[i][p])){
          dp[i+1][p] = dp[i][p-P[i]] + V[i];
          pdp[i+1][p] = pdp[i][p-P[i]] + P[i];
        }
        else{
          dp[i+1][p] = dp[i][p];
          pdp[i+1][p] = pdp[i][p];
        }
      }
    }
    cout << pdp[N][B] << " " << dp[N][B] << endl;    
  }

 return 0;
}

提出情報

提出時間 2019-12-23 23:28:17
問題 J - 質より量 (large)
ユーザ名 neet
状態 形式違反
正解率 N/A
提出出力結果

テストケース情報

# 状態 詳細情報
正解か誤答の場合のみ表示されます．