When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ianlim224's blog

By ianlim224, history, 3 years 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!

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

| Write comment?
»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Either you make the array 1D instead of 2D by reducing the dp states (second state can be removed)

Or just swap the dimensions of the dp so you will have vector dp(n + 1, vi(x + 1)) instead of vector dp(x + 1, vi(n + 1))

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How does swapping the dimensions reduce computation time? How should I store the dp states using 1d array? Thanks

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, I also faced this problem. Strangely enough, swapping the dimensions helped me to get AC. Did you figure out the reason behind swapping the dimensions ?