Submission #2141607


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

const int MAX_N = 5005;
typedef pair<ll, ll> P;
P HP[MAX_N];

const ll INF = 1LL << 58;
ll dp[MAX_N][MAX_N];

void naive(int N) {
  vector<int> ord(N);
  iota(ALL(ord), 0);

  vector<int> best_ord;
  int ans = 0;
  do {
    ll h = 0;
    int job = 0;
    vector<int> jobs;
    REP(i, N) if (HP[ord[i]].first >= h) {
      job++;
      h += HP[ord[i]].second;
      jobs.push_back(i);
    }
    // cout << job << " ";pv(ALL(ord));
    if (ans < job) {
      best_ord = jobs;
    }
    chmax(ans, job);

  } while (next_permutation(ALL(ord)));
  cout << ans << endl;
  REP(i, ans) {
    cout << HP[best_ord[i]];
  }
  cout << endl;
}

int main2() {
  int N; cin >> N;
  REP(i, N) {
    cin >> HP[i].first >> HP[i].second;
  }
  
  // if (N <= 10){
    // naive(N);
    // return 0;
  // }

  sort(HP, HP+N, [](const P& a, const P& b) -> bool {
    if (a.second + a.first != b.second + b.first)
      return a.second + a.first < b.second + b.first;
    return a.first < b.first;
  });

  REP(i, N+1) REP(j, N+1) dp[i][j] = INF;
  dp[0][0] = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= N; j++) chmin(dp[i+1][j], dp[i][j]);
    for (int j = 0; j < N; j++) {
      if (dp[i][j] <= HP[i].first) {
        chmin(dp[i+1][j+1], dp[i][j] + HP[i].second);
      }
    }
  }
  int ans = 0;
  for (int j = 0; j <= N; j++) {
    if (dp[N][j] < INF) ans = j;
  }
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}

Submission Info

Submission Time
Task D - Zabuton
User hs484
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2077 Byte
Status AC
Exec Time 99 ms
Memory 195840 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 46
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
All sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 256 KB
01-02.txt AC 1 ms 512 KB
01-03.txt AC 15 ms 48128 KB
01-04.txt AC 34 ms 95744 KB
01-05.txt AC 92 ms 195840 KB
01-06.txt AC 92 ms 195840 KB
01-07.txt AC 92 ms 195840 KB
01-08.txt AC 92 ms 195840 KB
01-09.txt AC 92 ms 195840 KB
01-10.txt AC 1 ms 256 KB
01-11.txt AC 11 ms 35712 KB
01-12.txt AC 45 ms 116352 KB
01-13.txt AC 90 ms 190720 KB
01-14.txt AC 93 ms 195840 KB
01-15.txt AC 93 ms 195840 KB
01-16.txt AC 93 ms 195840 KB
01-17.txt AC 93 ms 195840 KB
01-18.txt AC 94 ms 195840 KB
01-19.txt AC 1 ms 384 KB
01-20.txt AC 9 ms 29440 KB
01-21.txt AC 57 ms 137088 KB
01-22.txt AC 96 ms 195328 KB
01-23.txt AC 96 ms 195840 KB
01-24.txt AC 97 ms 195840 KB
01-25.txt AC 96 ms 195840 KB
01-26.txt AC 97 ms 195840 KB
01-27.txt AC 96 ms 195840 KB
01-28.txt AC 90 ms 195840 KB
01-29.txt AC 91 ms 195840 KB
01-30.txt AC 90 ms 195840 KB
01-31.txt AC 91 ms 195840 KB
01-32.txt AC 90 ms 195840 KB
01-33.txt AC 91 ms 195840 KB
01-34.txt AC 92 ms 195840 KB
01-35.txt AC 99 ms 195840 KB
01-36.txt AC 99 ms 195840 KB
01-37.txt AC 99 ms 195840 KB
01-38.txt AC 99 ms 195840 KB
01-39.txt AC 99 ms 195840 KB
01-40.txt AC 91 ms 195840 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB