ianlim224's blog

By ianlim224, history, 7 weeks 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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ianlim224 (previous revision, new revision, compare).

»
7 weeks 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))

»
7 weeks 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

  • »
    »
    4 weeks 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 ?