10130 - SuperSale

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

nayon31
New poster
Posts: 2
Joined: Tue Nov 24, 2015 12:41 am

Re: 10130 - SuperSale

why this get wrong answer..im getting right output for all input case
here is my code

Code: Select all

#include<bits/stdc++.h>
using namespace std;
int n,profit1,profit2;
int dpi[101][101],cost[1000],weight[1000],cap;
int dp(int i,int w)
{
if(i==n+1)
return 0;
if(dpi[i][w]!=-1)
return dpi[i][w];
int profit1=0,profit2=0;
if(w+weight[i]<=cap)
profit1=cost[i]+dp(i+1,w+weight[i]);
profit2=dp(i+1,w);
dpi[i][w]=max(profit1,profit2);
return dpi[i][w];
}
int main()
{
int t;
scanf("%d",&t);
for(int m=1;m<=t;m++)
{
int sum=0;
scanf("%d ",&n);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&cost[i],&weight[i]);
}
int g;
scanf("%d",&g);
for(int k=0;k<g;k++)
{
memset(dpi,-1,sizeof(dpi));
scanf("%d",&cap);
sum+=dp(1,0);
}
printf("%d\n",sum);
}

return 0;
}

anjan.anoup
New poster
Posts: 2
Joined: Thu Jan 22, 2015 12:07 pm

Re: 10130 - SuperSale

Hi, I don't understand why I got wrong ans? I match with udebug input given by Morass (666 input case). And all the ans is match with this. Though got wrong ans. Need help :

Code: Select all

#include <stdio.h>

int N, dp[1005][35], v[1005], w[1005], hist[105];

int solve(int i, int capital){
int left, right;
if(i == N)
return 0;
if(dp[i+1][capital] >= 0) {
return dp[i+1][capital];
}
left = solve(i+1, capital);
if(capital >= w[i]) {
right = v[i] + solve(i+1, capital - w[i]);
} else {
right = 0;
}
return dp[i+1][capital] = (left > right) ? left : right;
}

int main() {
int tC, per, sum, i, j, k, person;
scanf("%d", &tC);
while(tC--) {
scanf("%d", &N);
for(i = 0; i < N; i++){
scanf("%d %d", &v[i], &w[i]);
}
scanf("%d", &per);
sum = 0;

for(i = 0; i < 1005; i++){
hist[i] = -1;
}

for(i = 0; i < per; i++){
scanf("%d", &person);
if(hist[person] < 0) {
for(j = 0; j < 1005; j++){
for(k = 0; k < 35; k++){
dp[j][k] = -1;
}
}
hist[person] = solve(0, person);
}
sum+= hist[person];
}

printf("%d\n", sum);
}
return 0;
}