Submission #3769421


Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define MAX 1000000007
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define zoom ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

bool cmp(pair<ll, ll> a, pair<ll, ll> b) {
    return (b.ff + b.ss > a.ff + a.ss);
}

int main() {


    zoom;
    ll n, i, j;
    cin>>n;
    vector<pair<ll, ll> >A(n);
    for(i = 0; i < n; i += 1)
        cin>>A[i].ff>>A[i].ss;
    sort(A.begin(), A.end(), cmp);
    vector<vector<ll> > dp(n, vector<ll>());
    dp[0].pb(0);
    dp[0].pb(A[0].ss);
    for(i = 1; i < n; i += 1) {
        dp[i].pb(0);
        for(j = 1; j <= i; j += 1) {
            ll temp1 = dp[i - 1][j];
            ll temp2 = -1;
            if(dp[i - 1][j - 1] != -1 && dp[i - 1][j - 1] <= A[i].ff)
                temp2 = dp[i - 1][j - 1] + A[i].ss;            
            if((temp1 == -1 && temp2 == - 1))
                dp[i].pb(-1);
            else if(temp1 == -1)
                dp[i].pb(temp2);
            else if(temp2 == -1)
                dp[i].pb(temp1);
            else
                dp[i].pb(min(temp1, temp2));
        }
        if(dp[i - 1][j - 1] != -1 && dp[i - 1][j - 1] <= A[i].ff)
            dp[i].pb(dp[i - 1][j - 1] + A[i].ss);
        else
            dp[i].pb(-1); 
    }
    ll ans = -1;
    for(i = n - 1; i >= 0; i -= 1) {
        for(j = i; j >= 1; j -= 1) {
            if(dp[i][j] != -1)
            ans = max(ans, j); 
        }
    }
    cout<<ans;
    return 0;
}

Submission Info

Submission Time
Task A - AKIBA
User pchail
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1590 Byte
Status RE
Exec Time 104 ms
Memory 256 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 300
Status
RE × 3
RE × 24
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, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt RE 101 ms 256 KB
01-02.txt RE 101 ms 256 KB
01-03.txt RE 101 ms 256 KB
01-04.txt RE 101 ms 256 KB
01-05.txt RE 102 ms 256 KB
01-06.txt RE 103 ms 256 KB
01-07.txt RE 101 ms 256 KB
01-08.txt RE 101 ms 256 KB
01-09.txt RE 101 ms 256 KB
01-10.txt RE 101 ms 256 KB
01-11.txt RE 103 ms 256 KB
01-12.txt RE 101 ms 256 KB
01-13.txt RE 100 ms 256 KB
01-14.txt RE 100 ms 256 KB
01-15.txt RE 101 ms 256 KB
01-16.txt RE 102 ms 256 KB
01-17.txt RE 101 ms 256 KB
01-18.txt RE 101 ms 256 KB
sample-01.txt RE 104 ms 256 KB
sample-02.txt RE 101 ms 256 KB
sample-03.txt RE 100 ms 256 KB