Блог пользователя Gaurav678

Автор Gaurav678, история, 5 лет назад, По-английски

on some large test cases I am getting runtime error . please help

Your text to link here... https://cses.fi/problemset/task/1158/

Your code here...
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll n,b;
    cin>>n>>b;
    vector<ll>v(n+1) , vv(n+1);
    for(ll i=1 ; i<=n ; i++)
    {
        cin>>v[i];
    }
    for(ll i=1 ; i<=n ; i++)
    {
        cin>>vv[i];
    }
    vector<vector<ll>>dp(n+1 , vector<ll>(b+1,0));
    for(ll i=1 ; i<=b ; i++)
    {
        for(ll j=1 ; j<=n ; j++)
        {
            dp[j][i]=dp[j-1][i];
            ll left = i-v[j];
            if(left>=0)
            {
                dp[j][i] = max(dp[j-1][left] + vv[j] , dp[j][i]);
            }
        }
    }
    cout<<dp[n][b]<<endl;
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Your DP array is allocating up to 1000 * 10^5 numbers, which is too big for the memory limits. This causes RE instead of MLE because the allocation happens inside main.