Submission #606952


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
 
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; }
template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; }
template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; }

#define reps(i, j, n) for(int i = j; i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
#define UNQ(s) { sort(ALL(s)); (s).erase(unique( ALL(s)), (s).end());}

typedef long long int64;
const int64 INF = 1LL << 55;
typedef pair< int , int > Pi;
typedef pair< int , Pi > Pii;


int64 S[200], V[200], N, U;

pair<int64, int64> ps[1<<(30/2)];

int64 type1(){
  int n1=N/2;
  int n2=N-n1;
  for (int i=0; i< 1<<n1; i++) {
    int64 w2=0,v2=0;
    for (int j=0; j<n1; j++) {
      if (i>>j&1) {
        w2+=S[j];
        v2+=V[j];
      }
    }
    ps[i]=make_pair(w2, v2);
  }
  sort(ps, ps+ (1<<n1));
  int m=1;
  for (int i=0; i< 1<<n1; i++) {
    if (ps[m-1].second<ps[i].second) {
      ps[m++]=ps[i];
    }
  }
  int64 res=0;
  for (int i=0; i< 1<<n2; i++) {
    int64 w2=0,v2=0;
    for (int j=0; j<n2; j++) {
      if (i>>j&1) {
        w2+=S[n1+j];
        v2+=V[n1+j];
      }
    }
    if (w2<=U) {
      int64 v=(upper_bound(ps, ps+m, make_pair(U-w2, INF))-1)->second;
      res=max(res, v2+v);
    }
  }
  return(res);
}

int64 type2()
{
  int64 dp[1004 * 200];
  fill_n(dp, 1004 * 200, -1);
  dp[0] = 0;
  for(int i = 0; i < N; i++){
    for(int j = U; j >= S[i]; j--){
      dp[j] = max(dp[j], dp[j - S[i]] + V[i]);
    }
  }
  return(*max_element(dp, dp + U + 1));
}

int64 type3()
{
  int64 dp[1004 * 200];
  fill_n(dp, 1004 * 200, INF);
  dp[0] = 0;
  for(int i = 0; i < N; i++) {
    for(int j = 1003 * 200 - S[i]; j >= 0; j--) {
      dp[j + S[i]] = min(dp[j + S[i]], dp[j] + V[i]);
    }
  }
  int ret = 0;
  for(int i = 0; i < 1003 * 200; i++) {
    if(dp[i] <= U) ret = max(ret, i);
  }
  return(ret);
}


int main()
{
  cin >> N >> U;
  for(int i = 0; i < N; i++) {
    cin >> V[i] >> S[i];
  }
  if(N <= 30) cout << type1() << endl;
  else if(*max_element(S, S + N) <= 1000) cout << type2() << endl;
  else cout << type3() << endl;
}

Submission Info

Submission Time
Task D - ナップサック問題
User ei13333
Language C++ (GCC 4.9.2)
Score 67
Code Size 2561 Byte
Status
Exec Time 87 ms
Memory 2976 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask1 34 / 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 33 / 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
Case Name Status Exec Time Memory
subtask00_sample_1.txt 28 ms 1316 KB
subtask00_sample_2.txt 37 ms 1188 KB
subtask00_sample_3.txt 27 ms 1188 KB
subtask00_sample_4.txt 27 ms 1192 KB
subtask01_0.txt 37 ms 1312 KB
subtask01_1.txt 37 ms 1320 KB
subtask01_10.txt 37 ms 1236 KB
subtask01_11.txt 36 ms 1188 KB
subtask01_12.txt 39 ms 1312 KB
subtask01_13.txt 39 ms 1312 KB
subtask01_14.txt 37 ms 1192 KB
subtask01_2.txt 39 ms 1312 KB
subtask01_3.txt 38 ms 1316 KB
subtask01_4.txt 37 ms 1248 KB
subtask01_5.txt 36 ms 1312 KB
subtask01_6.txt 36 ms 1308 KB
subtask01_7.txt 37 ms 1312 KB
subtask01_8.txt 37 ms 1308 KB
subtask01_9.txt 37 ms 1308 KB
subtask02_0.txt 73 ms 2852 KB
subtask02_1.txt 37 ms 2868 KB
subtask02_10.txt 36 ms 2848 KB
subtask02_11.txt 45 ms 2848 KB
subtask02_12.txt 51 ms 2856 KB
subtask02_13.txt 33 ms 2848 KB
subtask02_14.txt 35 ms 2852 KB
subtask02_2.txt 66 ms 2776 KB
subtask02_3.txt 39 ms 2852 KB
subtask02_4.txt 64 ms 2976 KB
subtask02_5.txt 34 ms 2852 KB
subtask02_6.txt 87 ms 2784 KB
subtask02_7.txt 51 ms 2776 KB
subtask02_8.txt 37 ms 2848 KB
subtask02_9.txt 60 ms 2844 KB
subtask03_0.txt 33 ms 2848 KB
subtask03_1.txt 34 ms 2848 KB
subtask03_10.txt 33 ms 2784 KB
subtask03_11.txt 31 ms 2848 KB
subtask03_2.txt 32 ms 2848 KB
subtask03_3.txt 32 ms 2840 KB
subtask03_4.txt 31 ms 2836 KB
subtask03_5.txt 31 ms 2968 KB
subtask03_6.txt 31 ms 2848 KB
subtask03_7.txt 41 ms 2964 KB
subtask03_8.txt 41 ms 2964 KB
subtask03_9.txt 36 ms 2964 KB