CSES Book Shop TLE despite Bottom Up O(NX)
Difference between en1 and en2, changed 8 character(s)
I keep getting a TLE verdict for the CSES Book Shop question https://cses.fi/problemset/task/1158/↵
I've coded an iterative bottom-up DP:↵


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

#define f first↵
#define s second↵
#define pb push_back↵

#define all(x) x.begin(), x.end()↵
#define FOR(i, a) for (int i = 0; i < (a); i++)↵

typedef pair<int, int> ii;↵
typedef long long ll;↵
typedef vector<int> vi;↵
typedef vector<ii> vii;↵
typedef tuple<int, int, int> iii;↵
typedef vector<ll> vll;↵

const int INF = 1e9;↵
const ll INFL = 1e18;↵
const int MOD = 1000000007;↵

int main() {↵
  ios::sync_with_stdio(false);↵
  cin.tie(NULL);↵
  int n, x;↵
  cin >> n >> x;↵
  vector<vi> dp(x + 1, vi(n + 1));↵

  vi prices(n + 1);↵
  vi pages(x + 1);↵
  for (int i = 1; i <= n; ++i) {↵
    cin >> prices[i];↵
  }↵
  ↵
  for (int i = 1; i <= n; ++i) {↵
    cin >> pages[i];↵
  }↵
  ↵
  for (int i = 1; i <= x; ++i) {↵
   for (int j = 1; j <= n; ++j) {↵
   if (i < prices[j]) dp[i][j] = dp[i][j &mdash; 1];↵
   else dp[i][j] = max(dp[i][j &mdash; 1], pages[j] + dp[i &mdash; prices[j]][j &mdash; 1]);↵
   }↵
  }↵
  cout << dp[x][n];↵
}↵
~~~~~↵


The implementation is very similar to the sample codes found on unofficial editorials. Yet I still get TLE... Can anyone help to point out the issue/how to improve on the efficiency of my code? Thanks in advance!↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ianlim224 2021-04-26 16:08:32 8
en1 English ianlim224 2021-04-26 16:07:32 1402 Initial revision (published)