fork(1) download 
  1. /* paiza POH! Lite
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/196d3049d791ab74388a4566b13dd881
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8.  
  9. typedef struct _data {
  10. 	int q;
  11. 	int r;
  12. } DATA, *PDATA;
  13.  
  14. int a[51][500001];
  15. DATA data[51];
  16.  
  17. int main(void) {
  18.  
  19. 	int m;
  20. 	int n;
  21.  
  22. 	int w = 0, p = 0;
  23.  
  24. 	int i, j, x, y;
  25.  
  26. 	scanf("%d", &m);
  27. 	scanf("%d", &n);
  28.  
  29. 	for (i = 0; i < n; i++) {
  30. 		scanf("%d %d", &data[i].q, &data[i].r);
  31. 		w += data[i].q;
  32. 		p += data[i].r;
  33. 	}
  34. 	w -= m;
  35.  
  36. 	for (i = 0; i < n; i++) {
  37. 		for (j = 0; j <= w; j++) {
  38. 			if (data[i].q <= j) {
  39. 				x = a[i][j];
  40. 				y = a[i][j - data[i].q] + data[i].r;
  41. 				a[i + 1][j] = (x > y) ? x : y;
  42. 			} else {
  43. 				a[i + 1][j] = a[i][j];
  44. 			}
  45. 		}
  46. 	}
  47.  
  48. 	printf("%d\n", p - a[n][w]);
  49.  
  50. 	return 0;	
  51. }
Success #stdin #stdout 0s 101888KB
comments (?)
stdin 
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
stdout 
23072
https://ideone.com/KvRv3d
language:
C (gcc 8.3)
created:
11 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!