Submission #3732512


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 int MX = numeric_limits<int>::max();

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


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

int dp[5005][5005];



int main(){
    
    int n;
    cin >> n;

    memset(dp, MX, sizeof dp);

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


    dp[1][1] = v[1].p;

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

    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= i; 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);
                 } 

           }
      
      }
    

    int ans = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
             if(dp[i][j] < MX){
                  ans = max(ans, j);
               }
         }
       }
    

    cout << ans;
 

     
    return 0;
  }

Submission Info

Submission Time
Task D - Zabuton
User SpFxy
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1462 Byte
Status WA
Exec Time 80 ms
Memory 98176 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 1
WA × 2
AC × 8
WA × 38
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 31 ms 98048 KB
01-02.txt WA 31 ms 98048 KB
01-03.txt WA 35 ms 98048 KB
01-04.txt WA 44 ms 98176 KB
01-05.txt WA 79 ms 98176 KB
01-06.txt WA 80 ms 98176 KB
01-07.txt WA 79 ms 98176 KB
01-08.txt WA 79 ms 98176 KB
01-09.txt WA 79 ms 98176 KB
01-10.txt AC 31 ms 98048 KB
01-11.txt WA 33 ms 98048 KB
01-12.txt WA 50 ms 98176 KB
01-13.txt WA 76 ms 98176 KB
01-14.txt WA 79 ms 98176 KB
01-15.txt WA 79 ms 98176 KB
01-16.txt WA 79 ms 98176 KB
01-17.txt WA 79 ms 98176 KB
01-18.txt WA 79 ms 98176 KB
01-19.txt AC 31 ms 98048 KB
01-20.txt AC 33 ms 98048 KB
01-21.txt WA 55 ms 98176 KB
01-22.txt WA 79 ms 98176 KB
01-23.txt WA 79 ms 98176 KB
01-24.txt WA 79 ms 98176 KB
01-25.txt WA 79 ms 98176 KB
01-26.txt WA 79 ms 98176 KB
01-27.txt WA 79 ms 98176 KB
01-28.txt WA 77 ms 98176 KB
01-29.txt WA 77 ms 98176 KB
01-30.txt WA 77 ms 98176 KB
01-31.txt WA 77 ms 98176 KB
01-32.txt WA 77 ms 98176 KB
01-33.txt WA 80 ms 98176 KB
01-34.txt WA 80 ms 98176 KB
01-35.txt AC 79 ms 98176 KB
01-36.txt AC 79 ms 98176 KB
01-37.txt WA 78 ms 98176 KB
01-38.txt WA 79 ms 98176 KB
01-39.txt WA 78 ms 98176 KB
01-40.txt WA 79 ms 98176 KB
sample-01.txt WA 31 ms 98048 KB
sample-02.txt AC 31 ms 98048 KB
sample-03.txt WA 31 ms 98048 KB