fork(2) download 
  1. /* paiza POH! Lite
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/4ec50eb3fb1e6df0bb15a95138db642f
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. import java.lang.*;
  7. import java.util.*;
  8.  
  9. class Main
  10. {
  11.  
  12. 	static int[][] a = new int[51][500001];
  13. 	static int[] q = new int[51];
  14. 	static int[] r = new int[51];
  15.  
  16. 	public static void main (String[] args) throws java.lang.Exception
  17. 	{
  18.  
  19. 		int m;
  20. 		int n;
  21.  
  22. 		int w = 0, p = 0;
  23.  
  24. 		int i, j, x, y;
  25. 		int[] t0, t1;
  26.  
  27. 		Scanner sc = new Scanner(System.in);
  28. 		m = sc.nextInt();
  29. 		n = sc.nextInt();
  30.  
  31. 		for (i = 0; i < n; i++) {
  32. 			q[i] = sc.nextInt();
  33. 			r[i] = sc.nextInt();
  34. 			w += q[i];
  35. 			p += r[i];
  36. 		}
  37. 		w -= m;
  38.  
  39. 		for (i = 0; i < n; i++) {
  40. 			t0 = a[i];
  41. 			t1 = a[i + 1];
  42. 			for (j = 0; j <= w; j++) {
  43. 				if (q[i] <= j) {
  44. 					x = t0[j];
  45. 					y = t0[j - q[i]] + r[i];
  46. 					t1[j] = (x > y) ? x : y;
  47. 				} else {
  48. 					t1[j] = t0[j];
  49. 				}
  50. 			}
  51. 		}
  52.  
  53. 		System.out.println(p - a[n][w]);
  54.  
  55. 	}
  56. }
Success #stdin #stdout 0.25s 380672KB
comments (?)
stdin 
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
stdout 
23072
https://ideone.com/HNztMM
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!