fork download
copy 
  1. // D (compile time)
  2. //   $ dmd -J`pwd` -o- B.d 2> out.txt
  3. import std.algorithm;
  4. import std.array;
  5. import std.conv;
  6. import std.string;
  7.  
  8. string solveAll(string s)
  9. {
  10. 	return s.splitLines().solveEach(1);
  11. }
  12.  
  13. string solveEach(string[] lines, int i)
  14. {
  15. 	if( i == lines.length )
  16. 		return "";
  17.  
  18. 	// std.algorithm.map doesn't work in compile time yet.
  19. 	int[] t;
  20. 	foreach(s; lines[i].split())
  21. 		t ~= s.to!int();
  22. 	return text("Case #", i, ": ", solve(t[0], t[1], t[2], t[3..$]), "\n", lines.solveEach(i+1));
  23. }
  24.  
  25. int solve(int N, int S, int P, int[] T)
  26. {
  27. 	int[] dp = new int[S+1];
  28. 	dp[0] = 0;
  29. 	foreach(x; 1..S+1) dp[x] = int.min;
  30.  
  31. 	foreach(t; T) {
  32. 		bool non, sup;
  33. 		if(t%3==0){
  34. 			non = (t/3)>=P;
  35. 			sup = t>=3 && (t/3+1)>=P;
  36. 		}
  37. 		else if(t%3==1){
  38. 			non = (t/3+1)>=P;
  39. 			sup = t>=4 && (t/3+1)>=P;
  40. 		}
  41. 		else{
  42. 			non = (t/3+1)>=P;
  43. 			sup = (t/3+2)>=P;
  44. 		}
  45.  
  46. 		int[] dp2 = new int[S+1];
  47. 		foreach(x; 0..S+1)
  48. 			dp2[x] = dp[x] + (non ? 1 : 0);
  49. 		foreach(x; 0..S)
  50. 			dp2[x+1] = max(dp2[x+1], dp[x] + (sup ? 1 : 0));
  51. 		dp = dp2;
  52. 	}
  53.  
  54. 	return dp[S];
  55. }
  56.  
  57. immutable inputFileName = "B.in";
  58.  
  59. version(RunTime)
  60. {
  61. 	import std.file, std.stdio;
  62. 	void main() { inputFileName.readText().solveAll().write(); }
  63. }
  64. else
  65. {
  66. 	pragma(msg, import(inputFileName).solveAll());
  67. }
  68.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2OTqE
language:
D (dmd 2.085.0)
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!