Hello guys.
I keep getting WA in this problem, I tried to solved it using backtracking and Memoization. The idea as follows: for each subject, you can choose to study certain amount of hours and jump right to the next subject, or you can choose no to study and ignore this current hour, this would lead to study the current subject but with some additional hours. You only study a subject this hour if you are assured that the score you will obtain for that exam is greater or equal to 5. I don't know what I'm doing wrong.
#include <stdio.h>
#include <string.h>
#define EPS 1e-9
int T, N, M, board[15][110], i, j;
int memo[110][15][110];
int max(int a, int b) {
return a > b ? a : b;
}
int solve(int h_left, int id, int hour) {
if (h_left <= 0 || id >= N || hour > M)
return 0;
if (h_left < hour)
return 0;
if (memo[h_left][id][hour] != -1) return memo[h_left][id][hour];
int ans = solve(h_left, id, hour+1);
if (board[id][hour] >= 5)
ans = max(ans, board[id][hour] + solve(h_left - hour, id+1, 1));
return memo[h_left][id][hour] = ans;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d", &N, &M);
for (i=0 ; i<N ; i++) {
for (j=1 ; j<=M ; j++)
scanf("%d", &board[i][j]);
}
memset(memo, -1, sizeof memo);
int res = solve(M, 0, 1);
if (res >= 5 * N)
printf("Maximal possible average mark - %.2lf.\n", (res / (double)N));
else
printf("Peter, you shouldn't have played billiard that much.\n");
}
}
Maximal possible average mark - 9.75.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.80.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.30.
Maximal possible average mark - 9.25.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.14.
Maximal possible average mark - 9.29.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 7.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.67.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.67.
Maximal possible average mark - 9.00.
Maximal possible average mark - 6.50.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.50.
Maximal possible average mark - 7.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.33.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.75.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.60.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 7.75.
Maximal possible average mark - 8.00.
Maximal possible average mark - 8.67.
Maximal possible average mark - 9.14.
Maximal possible average mark - 8.57.
Maximal possible average mark - 7.50.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.50.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.75.
Maximal possible average mark - 9.50.
Maximal possible average mark - 9.50.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.33.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.11.
Maximal possible average mark - 9.14.
Maximal possible average mark - 9.56.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.50.
Maximal possible average mark - 9.80.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.14.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Check input and AC output for thousands of problems on uDebug!
[quote="brianfry713"][/quote]
NICE TO MEET YOU AGAIN
I really got trouble with 11341
i try every in put i could found here and got same
then i also try 1e-9
but i still keep getting WA
i really don't know why
plz help
3ks
#include<stdio.h>
#include<stdlib.h>
#define max(a,b) a>b?a:b
int main(){
// freopen("out.txt","w",stdout);
int cost[15][11];
int map[15][110];
int k,z;
scanf("%d",&z);
for(k=1;k<=z;k++){
int m,n;
scanf("%d%d",&m,&n);
int i,j;
for(i=1;i<=m;i++){for(j=1;j<=n;j++)scanf("%d",&map[i][j]);map[i][0]=0;}
for(i=1;i<=m;i++)for(j=0;j<=6;j++)cost[i][j]=999;
for(i=1;i<=m;i++){
int pcost=0;
for(j=1;j<=n-m+1;j++){
if(map[i][j]>=5+pcost){
cost[i][pcost]=j;
j--;
pcost++;
}
}
}
int time=n,score=0;
for(i=1;i<=m;i++){
time-=cost[i][0];
score+=5;
}
if(time<0){printf("Peter, you shouldn't have played billiard that much.\n");continue;}
int dp[11][110];
for(i=1;i<=10;i++)for(j=1;j<=100;j++)dp[i][j]=0;
for(i=0;i<=n;i++){
dp[1][i]=map[1][i];
}
int s=cost[1][0];
for(i=2;i<=m;i++){
for(j=s+cost[i][0];j<=n;j++){
int d=cost[i][0];
dp[i][j]=dp[i-1][j-d]+map[i][d];
for(;d<=j;d++){
dp[i][j]=max(dp[i][j],dp[i-1][j-d]+map[i][d]);
}
}
s+=cost[i][0];
}
double res=(double)dp[m][n]/(double)m;
if(dp[m][n]>=5*m)printf("Maximal possible average mark - %.2lf.\n",res);
else printf("Peter, you shouldn't have played billiard that much.\n");
}
return 0;
}
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.80.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 8.25.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.60.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.17.
Maximal possible average mark - 7.86.
Maximal possible average mark - 8.50.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.63.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 8.80.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 8.50.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.29.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 7.50.
Maximal possible average mark - 8.71.
Maximal possible average mark - 8.83.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.83.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 5.50.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.75.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.70.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.43.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 8.80.
Maximal possible average mark - 9.00.
Maximal possible average mark - 8.25.
Maximal possible average mark - 6.43.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.43.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.00.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.86.
Maximal possible average mark - 7.75.
Maximal possible average mark - 9.40.
Maximal possible average mark - 9.40.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 8.50.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 9.20.
Maximal possible average mark - 9.22.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 7.00.
Maximal possible average mark - 8.25.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.67.
Maximal possible average mark - 9.14.
Maximal possible average mark - 7.00.
Maximal possible average mark - 6.88.
Maximal possible average mark - 10.00.
Peter, you shouldn't have played billiard that much.
Peter, you shouldn't have played billiard that much.
Maximal possible average mark - 10.00.
Maximal possible average mark - 9.25.
Check input and AC output for thousands of problems on uDebug!