Stalin69's blog

By Stalin69, history, 2 months ago, In English

CSES Problem runtime Error :

Today, I was solving a CSES problem named Book Shop which is a standard DP problem, But I'm getting runtime error on same solution when I'm using long long instead of int. I'm not able to figure the reason, why it is not working.

But working with the same solution when I used int and it got accepted.

Can anybody just tell me the exact reason and when these types of problems can occur ?

Here is the code that gives me runtime error (used long long everywhere)

// A.cpp
 
#include<bits/stdc++.h>
using namespace std;
 
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e17
#define endl "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits(x) __builtin_popcountll(x)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
 
void solve() {
	ll n, x;
	cin >> n >> x;
 
	vector<pair<ll, ll>> arr(n + 1);
	for (ll i = 1; i <= n; i++)
		cin >> arr[i].ff;
	for (ll i = 1; i <= n; i++)
		cin >> arr[i].ss;
 
	vector<vector<ll>> dp(n + 1, vector<ll>(x + 1, 0LL));
 
	for (ll i = 1; i <= n; i++)
		for (ll j = 1; j <= x; j++)
			dp[i][j] = (j >= arr[i].ff ? max(dp[i - 1][j], dp[i - 1][j - arr[i].ff] + arr[i].ss) : dp[i - 1][j]);
 
	cout << dp[n][x] << endl;
}
 
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll tc;
	tc = 1;
	// cin >> tc;
	for (ll i = 1; i <= tc; i++) {
		solve();
	}
 
	return 0;
}

Is it due to strict memory guidelines on CSES ? So I need to use int for most of the problems.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

CSES Book Shop has 512 MB memory limit so when you use 10^8 (worst case) long long (8 bytes), around 800 MB, you will get RTE.