fork download 
  1. /* paiza POH! Lite
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/2959acee6047853ff7548df7517425e3
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. import java.io.*;
  7. import java.lang.*;
  8. import java.util.*;
  9.  
  10. class Main
  11. {
  12. 	static byte[] buf = new byte[2000];
  13. 	static int bufindex = 0;
  14.  
  15. 	static int nextInt() {
  16. 		int n = 0;
  17. 		int b = (int)buf[bufindex];
  18. 		while (b < '0' || b > '9') {
  19. 			b = (int)buf[++bufindex];
  20. 		}
  21. 		while (b >= '0' && b <= '9') {
  22. 			n = n * 10 + (int)(b) - '0';
  23. 			b = (int)buf[++bufindex];
  24. 		}
  25. 		return n;
  26. 	}
  27.  
  28. 	static int[][] a = new int[51][500001];
  29. 	static int[] q = new int[51];
  30. 	static int[] r = new int[51];
  31.  
  32. 	public static void main (String[] args) throws java.lang.Exception
  33. 	{
  34.  
  35. 		int m;
  36. 		int n;
  37.  
  38. 		int w = 0, p = 0;
  39.  
  40. 		int i, j, x, y;
  41. 		int[] t0, t1;
  42.  
  43. 		System.in.read(buf);
  44.  
  45. 		m = nextInt();
  46. 		n = nextInt();
  47.  
  48. 		for (i = 0; i < n; i++) {
  49. 			q[i] = nextInt();
  50. 			r[i] = nextInt();
  51. 			w += q[i];
  52. 			p += r[i];
  53. 		}
  54. 		w -= m;
  55.  
  56. 		for (i = 0; i < n; i++) {
  57. 			t0 = a[i];
  58. 			t1 = a[i + 1];
  59. 			for (j = 0; j <= w; j++) {
  60. 				if (q[i] <= j) {
  61. 					x = t0[j];
  62. 					y = t0[j - q[i]] + r[i];
  63. 					t1[j] = (x > y) ? x : y;
  64. 				} else {
  65. 					t1[j] = t0[j];
  66. 				}
  67. 			}
  68. 		}
  69.  
  70. 		System.out.println(p - a[n][w]);
  71.  
  72. 	}
  73. }
Success #stdin #stdout 0.22s 381248KB
comments (?)
stdin 
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
stdout 
23072
https://ideone.com/yFzGLU
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!