Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

thefourtheye's blog

SPOJ — 181 — SCUBADIV — WA
By thefourtheye, 11 years ago, In English

Hi, Can anyone please tell me a test case for which this code might fail? It gives WA.

    short DPTable [1001][100][100], OxyArr [1024], NitArr[1024], WeightArr [1024], SumOxy, SumNit;
    int main()
    {
       int Total, Oxy, Nit, CyCount;
       scanf ("%d", &Total);
       while (Total--)
       {
          scanf ("%d%d%d", &Oxy, &Nit, &CyCount);
          for (int i = 0; i < CyCount; i++) scanf ("%d%d%d", &OxyArr[i], &NitArr[i], &WeightArr[i]);
          memset (DPTable, -1, sizeof DPTable);
          int Solution = numeric_limits <int>::max();
          for (int i = 1; i <= CyCount; i++)
          {
             DPTable [i-1][0][0] = 0;
             for (int j = 0; j <= Oxy; j++)
             {
                for (int k = 0; k <= Nit; k++)
                {
                   DPTable [i][j][k] = DPTable [i-1][j][k];
                   if (DPTable [i-1][max(0, j-OxyArr[i-1])][max(0, k-NitArr[i-1])] != -1)
                   {
                      if (DPTable [i][j][k] < DPTable [i-1][max(0, j-OxyArr[i-1])][max(0, k-NitArr[i-1])] + WeightArr[i-1])
                         DPTable [i][j][k] = DPTable [i-1][max(0, j-OxyArr[i-1])][max(0, k-NitArr[i-1])] + WeightArr[i-1];
                      if (j >= Oxy && k >= Nit && Solution > DPTable [i][j][k]) Solution = DPTable [i][j][k];
                   }
                }
             }
          }
          printf ("%d\n", Solution);
       }
    }
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try this, 1 2 2 2 1 1 1 2 2 50

The answer should be 50. You are not getting this...I hope this will help you.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try finding out dp[i][j][k] where dp[i][j][k] denotes minimum cylinders required from first k cylinders such that i litre of Oxygen and j Litre of Nitrogen is satisfied. dp[i][j][k]=min(dp[i][j][k-1],dp[max(0,i-array[k][0])][max(0,j-array[k][1])][k-1]+array[k][2]),where array[k] stores the cylinder parameters as stated in problem statement clearly.

Take i litre oxygen and j litre nitrogen from k-1 cylinders or take the kth cylinder..

Base Case: dp[i][j][0]=INF for all i<=Oxygen and j<=Nitrogen dp[0][0][i]=0 fro all i<=Number of Cylinders.

Hope this Helps.

→ Reply