提出詳細

ソースコード

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <fstream>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define sz size()
#define endl "\n"
#define print(X) cout << (X) << "\n"
// #define input(X) getline(cin,X)
static const ll  INF = 1e9+7;
static const ll INFL = 1e18+7;
ll n,m,l, p;
string s,t;
int d[200010],w[200010],dp[5001][5001];
char field[501][501];

int money[5001][5001];

int func(){
  int W;
  cin >> n;
  cin >> W;
  rep(i,0,n)cin >> w[i] >> d[i];
  for (int j = 0; j <= W; j++) dp[n][j] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= W; ++j) {
      if (j >= w[i]){
        if(dp[i][j-w[i]] + d[i] >= dp[i][j]){
          dp[i+1][j] = dp[i][j-w[i]] + d[i];
          money[i+1][j] = money[i][j-w[i]] + w[i];
        }else{
          dp[i+1][j] = dp[i][j];
          money[i+1][j] = money[i][j];
        }
      }
      else {
        dp[i+1][j] = dp[i][j];
        money[i+1][j] = money[i][j];
      }
    }
  }

  cout << money[n][W] << " " << dp[n][W] << endl;
  return 0;
}

void init(){
  rep(i,0,5001){
    rep(j,0,5001){
      dp[i][j] = money[i][j] = 0;
    }
  }
}

int main(){
  int p;
  cin >> p;
  rep(i,0,p){
    printf("Case #%lld\n", i+1);
    init();
    func();
  }
}

提出情報

提出時間 2019-11-30 15:52:49
問題 J - 質より量 (large)
ユーザ名 miyajima
状態 形式違反
正解率 N/A
提出出力結果

テストケース情報

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