fork(1) download 
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. #define MAX 1000000000
  5. int value[105];
  6. int val[105][105][105],n,k;
  7. bool b_val[105][105][105];
  8.  
  9. int func( int i, int j, int count)
  10. {	//printf("%d %d %d\n",i,j,count);
  11. 	if ( i == 0 && count <= n )
  12. 	{	//printf("return 0\n");
  13. 		return 0;
  14. 	}
  15. 	if ( j == 0 || count > n )
  16. 	{	//printf("return MIN\n");
  17. 		return MAX;
  18. 	}
  19. 	int q1,q2;
  20. 	if ( value[j] == -1 )
  21. 	{	if ( b_val[i][j-1][count] == 1 )		//skipped here so count-> count only. no +1 here!
  22. 			val[i][j][count]= val[i][j-1][count];
  23. 		else
  24. 			val[i][j][count]= func(i,j-1,count);
  25. 		b_val[i][j][count]=1;
  26. 		//printf("Return %d\n", val[i][j][count]);
  27. 		return val[i][j][count];
  28. 	}
  29. 	else if ( value[j] > 0 )
  30. 	{	if ( b_val[i][j-1][count] == 1 )
  31. 			q1=val[i][j-1][count];
  32. 		else
  33. 			q1= func(i,j-1,count);
  34. 		if ( i-j >= 0 )
  35. 		{	if ( b_val[i-j][j-1][count+1] == 1 )
  36. 				q2= val[i-j][j-1][count+1];
  37. 			else
  38. 				q2= func(i-j, j-1, count+1)+ value[j];
  39. 		}
  40. 		else
  41. 			q2=MAX;
  42. 		//printf("Return %d\n", min(q1,q2));
  43. 		b_val[i][j][count]=1;
  44. 		return val[i][j][count]= min(q1,q2);
  45. 	}
  46. 	else if ( value[j] == 0 )			//free so it doesnt need to be bought!
  47. 	{	if ( b_val[i][j-1][count] == 1 )
  48. 			q1=val[i][j-1][count];
  49. 		else
  50. 			q1= func(i,j-1,count);
  51. 		if ( i- j >= 0 )
  52. 		{	if ( b_val[i-j][j-1][count] == 1 )
  53. 				q2= val[i-j][j-1][count];
  54. 			else
  55. 				q2= func(i-j, j-1, count);
  56. 		}
  57. 		else
  58. 			q2=MAX;
  59. 		//printf("return %d\n",min(q1,q2));
  60. 		b_val[i][j][count]=1;
  61. 		return val[i][j][count]= min(q1,q2);
  62. 	}
  63. }
  64.  
  65. int main()
  66. {	int t;
  67. 	scanf("%d",&t);
  68. 	while(t-- > 0 )
  69. 	{	//n= rand()%10;
  70. 		//k= rand()%10;
  71. 		scanf("%d %d",&n,&k);
  72. 		//printf("%d %d\n",n,k);
  73. 		for ( int i=0; i<105; i++)
  74. 			for ( int j=0; j<105; j++)
  75. 				for ( int k1=0; k1<105; k1++)
  76. 					b_val[i][j][k1]=0;
  77. 		for ( int i=1; i<=k; i++)
  78. 		{	value[i]= rand()%1000;
  79. 			scanf("%d",&value[i]);
  80. 			//printf("%d\n",value[i]);
  81. 			//value[i]*=-1;
  82. 		}
  83. 		int p1= func(k,k,0);
  84. 		if ( p1 == MAX )
  85. 			printf("-1\n");
  86. 		else
  87. 			printf("%d\n",p1);
  88. 	}
  89. 	return 0;
  90. }
  91.  
Success #stdin #stdout 0s 8552KB
comments (?)
stdin 
1
83 86
777
915
793
335
386
492
649
421
362
27
690
59
763
926
540
426
172
736
211
368
567
429
782
530
862
123
67
135
929
802
22
58
69
167
393
456
11
42
229
373
421
919
784
537
198
324
315
370
413
526
91
980
956
873
862
170
996
281
305
925
84
327
336
505
846
729
313
857
124
895
582
545
814
367
434
364
43
750
87
808
276
178
788
584
403
651
stdout 
38
https://ideone.com/w8Ek7V
language:
C++ (gcc 8.3)
created:
13 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!