ianlim224's blog

By ianlim224, history, 3 months ago, In English

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!

Read more »

Tags dp, cses
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it