Submission #3733290


Source Code Expand

/*
    Question link: https://cf17-final.contest.atcoder.jp/tasks/cf17_final_d
*/

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cstring>
#include<limits>
#include<cmath>

#define LL long long
#define mp make_pair 
#define pb push_back
#define f first
#define s second


using namespace std;

const LL MX = numeric_limits<LL>::max();

struct par{
    int h;
    int p;
}v[5005];


bool cmp(par a, par b){
          return a.h + a.p < b.h + b.p; 
       }

LL dp[5005][5005];



int main(){
    
    int n, ans = 0;
    cin >> n;

    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
                 dp[i][j] = MX;


    for(int i = 1; i <= n; i++){
         cin >> v[i].h >> v[i].p;
      }
    
    sort(v + 1, v + n + 1, cmp);

    for(int i = 0; i <= n; i++) dp[i][0] = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
             
               dp[i][j] = dp[i-1][j];
               
               if(dp[i-1][j-1] <= v[i].h){
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + v[i].p);
                 }
           }
        } 

    
    for(int j = 1; j <= n; j++) if(dp[n][j] != MX) ans = j;

    
    cout << ans;
    
   
  
    return 0;
  }

Submission Info

Submission Time
Task D - Zabuton
User SpFxy
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1366 Byte
Status AC
Exec Time 91 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 1 ms 256 KB
01-02.txt AC 2 ms 512 KB
01-03.txt AC 16 ms 48128 KB
01-04.txt AC 36 ms 95616 KB
01-05.txt AC 87 ms 195840 KB
01-06.txt AC 88 ms 195840 KB
01-07.txt AC 87 ms 195840 KB
01-08.txt AC 87 ms 195840 KB
01-09.txt AC 87 ms 195840 KB
01-10.txt AC 1 ms 256 KB
01-11.txt AC 12 ms 35712 KB
01-12.txt AC 45 ms 116352 KB
01-13.txt AC 84 ms 190720 KB
01-14.txt AC 87 ms 195840 KB
01-15.txt AC 88 ms 195840 KB
01-16.txt AC 88 ms 195840 KB
01-17.txt AC 88 ms 195840 KB
01-18.txt AC 88 ms 195840 KB
01-19.txt AC 1 ms 384 KB
01-20.txt AC 10 ms 29440 KB
01-21.txt AC 55 ms 137088 KB
01-22.txt AC 89 ms 195328 KB
01-23.txt AC 90 ms 195840 KB
01-24.txt AC 89 ms 195840 KB
01-25.txt AC 90 ms 195840 KB
01-26.txt AC 89 ms 195840 KB
01-27.txt AC 90 ms 195840 KB
01-28.txt AC 85 ms 195840 KB
01-29.txt AC 85 ms 195840 KB
01-30.txt AC 85 ms 195840 KB
01-31.txt AC 85 ms 195840 KB
01-32.txt AC 85 ms 195840 KB
01-33.txt AC 88 ms 195840 KB
01-34.txt AC 87 ms 195840 KB
01-35.txt AC 91 ms 195840 KB
01-36.txt AC 91 ms 195840 KB
01-37.txt AC 91 ms 195840 KB
01-38.txt AC 91 ms 195840 KB
01-39.txt AC 91 ms 195840 KB
01-40.txt AC 87 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