CSES Book Shop TLE despite Bottom Up O(NX)

Revision en1, by ianlim224, 2021-04-26 16:07:32

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 FOR(i, a) for (int i = 0; i < (a); i++)

typedef pair<int, int> ii; typedef long long ll; typedef vector vi; typedef vector vii; typedef tuple<int, int, int> iii; typedef vector 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 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 — 1]; else dp[i][j] = max(dp[i][j — 1], pages[j] + dp[i — prices[j]][j — 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 ianlim224 2021-04-26 16:08:32 8
en1 ianlim224 2021-04-26 16:07:32 1402 Initial revision (published)