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 — 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!↵
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 — 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!↵