Submission #503396

#	Time	Username	Problem	Language	Result	Execution time	Memory
503396		albertkang	Knapsack (NOI18_knapsack)	Java	73 / 100	677 ms	262144 KiB

knapsack

import java.io.*;
import java.util.*;
public class knapsack
{
   public static void main(String[] args) throws IOException
   {
      FastReader infile = new FastReader();
      int s = infile.nextInt();
      int n = infile.nextInt();
      int[][] items = new int[n+1][3]; //price weight copies
      for(int x = 1; x <= n; x++){
         items[x][0] = infile.nextInt();
         items[x][1] = infile.nextInt();
         items[x][2] = infile.nextInt();
      }
      int[][] dp = new int[n+1][s+1];
      for(int x = 0; x <= n; x++){
         Arrays.fill(dp[x],-1);
      }
      dp[0][0] = 0;
      for(int i = 0; i < n; i++){
         for(int j = 0; j <= s; j++){
            if(dp[i][j] == -1)
               continue;
            int price = items[i+1][0];
            int weight = items[i+1][1];
            int copies = items[i+1][2];
            int limiter = Math.min((int)(s-j)/weight,copies);
            for(int x = 0; x <= limiter; x++){
               dp[i+1][j+x*weight] = Math.max(dp[i+1][j+x*weight],dp[i][j]+price*x);
            }
         }
      }
      int solution = 0;
      for(int x = 0; x <= s; x++){
         solution = Math.max(dp[n][x],solution);
      }
      System.out.print(solution);
   }
}
class FastReader
{
   BufferedReader br;
   StringTokenizer st;

   public FastReader() throws FileNotFoundException
   {
      br = new BufferedReader(new InputStreamReader(System.in));
   }

   public FastReader(String file) throws FileNotFoundException
   {
      br = new BufferedReader(new FileReader(file));
   }
 
   boolean hasNext()
   {
      while (st == null || !st.hasMoreElements())
      {
         try
         {
            st = new StringTokenizer(br.readLine());
         }
         catch (Exception  e)
         {
            return false;
         }
      }
      return true;
   }
 
   String next()
   {
      while (st == null || !st.hasMoreElements())
      {
         try
         {
            st = new StringTokenizer(br.readLine());
         }
         catch (IOException  e)
         {
            e.printStackTrace();
         }
      }
      return st.nextToken();
   }
 
   int nextInt()
   {
      return Integer.parseInt(next());
   }
 
   long nextLong()
   {
      return Long.parseLong(next());
   }
 
   double nextDouble()
   {
      return Double.parseDouble(next());
   }
 
   String nextLine()
   {
      String str = "";
      try
      {
         str = br.readLine();
      }
      catch (IOException e)
      {
         e.printStackTrace();
      }
      return str;
   }
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27