problem:CSES - Coin Combinations II
My solution:
int main()
for(ll j=0;j<=s;j++)
{
if(j!=0 and i==0)
{
dp[i][j]=0;
}
if(j==0)
{
dp[i][j]=1;
}
else
{
break;
}
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=s;j++)
{
if(j-arr[i-1]>=0)
{
dp[i][j]=(dp[i][j-arr[i-1]]%p+dp[i-1][j]%p)%p;
}
else
{
dp[i][j]=dp[i-1][j]%p;
}
}
}
cout<<dp[n][s];
}
Didn’t you ask this before as well?Dp problem help(Coin Combinations) - #7 by vaibhavgadag )
And use ``` for formatting the code.
#include <iostream>
using namespace std;
int main() {
// your code goes here
return 0;
}
This is how it looks when you use ```.
3 Likes
pst10
August 26, 2020, 10:41am
3
long long dp[ 101 ][ 1000001 ]
It allocates the memory from the stack. Stack memory is limited so you can’t do too big allocations.
Just change long long int into int , it will work fine , as values won’t exceed pow( 10 , 9 ) + 7
But if you want to declare it as long long then do it dynamically.
long long **dp ;
dp = new ( long long* )[ 101 ] ;
for( int i = 0 ; i < 101 ; i++ )
dp[ i ] = new long long[ 1000001 ] ;
It allocates the memory from the heap. Heap allocations can be big.
5 Likes
i have one more problem…https://cses.fi/problemset/task/1158/
const ll mod=pow(10,9)+7;
int main()
ll n,x;
ll price[1001],pages[1001];
ll **dp ;
dp = new long long* [ 1001 ] ;
for( int i = 0 ; i < 1001 ; i++ )
{
dp[i]=new long long[ 1000001 ];
}
cin>>n>>x;
for(int i=0;i<n;i++)
{
cin>>price[i];
}
for(int i=0;i<n;i++)
{
cin>>pages[i];
}
for(ll i=0;i<=n;i++)
{
for(ll j=0;j<=x;j++)
{
if(i==0 || j==0)
{
dp[i][j]=0;
}
else
{
break;
}
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=x;j++)
{
if(j-price[i-1]>=0)
{
dp[i][j]=max(dp[i-1][j-price[i-1]]+pages[i-1],dp[i-1][j]);
}
else
{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<dp[n][x];
return 0;
}
Again run time error!!
Op:99999
code of codeforces guy:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x;
cin >> n >> x;
vector<int> price(n), pages(n);
for (int&v : price) cin >> v;
for (int&v : pages) cin >> v;
vector<vector<int>> dp(n+1,vector<int>(x+1,0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= x; j++) {
dp[i][j] = dp[i-1][j];
int left = j-price[i-1];
if (left >= 0) {
dp[i][j] = max(dp[i][j], dp[i-1][left]+pages[i-1]);
}
}
}
cout << dp[n][x] << endl;
}
