fork(4) download
copy 
  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.     // Dynamic programming solution based on the following relation:
  6.     // Optimal solution for N students and M balls is: X balls given to Nth student
  7.     // combined with optimal solution for N-1 students and M-X balls
  8.     public static void main(String[] args) {
  9.     	Scanner in = new Scanner(System.in);
  10.         int m = in.nextInt();
  11.         int n = in.nextInt();
  12.         int[] a = new int[n];
  13.         int[] b = new int[n];
  14.         int[] c = new int[n];
  15.         for(int i = 0; i < n; i++) {
  16.         	a[i] = in.nextInt();
  17.         	b[i] = in.nextInt();
  18.         	c[i] = in.nextInt();
  19.         }
  20.  
  21.  
  22.         int[] currentColumn = new int[m+1];
  23.         int[] nextColumn = new int[m+1];
  24.         Arrays.fill(nextColumn, Integer.MAX_VALUE);
  25.  
  26.         // First column
  27.         for (int i = 0; i <= m; i++) {
  28.             currentColumn[i] = a[0]*i + c[0]*((i-1)/b[0]);
  29.         }
  30.  
  31.         // Dynamic programming
  32.         // Columns of DP table
  33.         for(int stud=1; stud < n; stud++) {
  34.             // Cells of the column
  35.             for (int ball = 0; ball <= m; ball++) {
  36.                 // X is the number of balls given to the new student
  37.                 for (int x = 0; x <= ball; x++) {
  38.                     int timeStud = a[stud]*x + c[stud]*((x-1)/b[stud]);
  39.                     int timeOthers = currentColumn[ball - x];
  40.                     nextColumn[ball] = Math.min(nextColumn[ball], Math.max(timeStud, timeOthers));
  41.                     // Shortcut: if current student is the bottleneck, it doesn't make sense to give him more balls
  42.                     if(timeStud > timeOthers) {
  43.                         break;
  44.                     }
  45.                 }
  46.             }
  47.             // Proceed to next column
  48.             int[] tmp = currentColumn;
  49.             currentColumn = nextColumn;
  50.             nextColumn = tmp;
  51.             Arrays.fill(nextColumn, Integer.MAX_VALUE);
  52.         }
  53.  
  54.         System.out.println(currentColumn[m]);
  55.     }
  56. }
  57.  
Success #stdin #stdout 0.14s 321280KB
comments (?)
stdin
copy 
10 3
1 2 3
3 10 3
2 4 3
stdout
copy 
8
https://ideone.com/hpdwsV
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!