fork download
copy 
  1. /* 
  2. 	Pranshul Agarwal
  3. 	B.tech CSE Graduate
  4. 	MNNIT Allahabad
  5. */
  6.  
  7.  
  8. #include <algorithm>
  9. #include <cstdio>
  10. #include <cstring>
  11. using namespace std;
  12.  
  13. #define inc(i,a,n) for(int i=a;i<=n;i++)
  14.  
  15. #define in(n) scanf("%d",&n)
  16. #define in2(n,m) scanf("%d%d",&n,&m)
  17.  
  18. int dp[1445][725][2];
  19.  
  20. bool hash1[2][1445];
  21. bool is_valid(int cur, int cam, int duty){
  22. 	int jam = cur - cam;
  23. 	return (hash1[duty][cur] && cam<=720 && jam<=720);
  24. }
  25. int fun(int cur, int cam, int duty){
  26. 	if(cur == 1441)return 0;
  27. 	if(!is_valid(cur, cam, duty)) return 1000000;
  28. 	if(dp[cur][cam][duty]!=-1)return dp[cur][cam][duty];
  29. 	int	ans = fun(cur+1,cam + (duty == 0), duty);
  30. 	ans = min(ans, 1+ fun(cur+1, cam + (1-duty == 0), 1-duty));
  31. 	return dp[cur][cam][duty]=ans;
  32. }
  33. int main()
  34. {
  35. 	int a,b,t,start,end;
  36. 	in(t);
  37. 	inc(d,1,t)
  38. 	{
  39. 		in2(a,b);
  40. 		inc(i,0,1441){
  41. 			hash1[0][i] = hash1[1][i] = true;
  42. 		}
  43. 		memset(dp,-1,sizeof(dp));
  44. 		while(a--){
  45. 			in2(start,end);
  46. 			start++,end++;
  47. 			inc(i,start,end-1)
  48. 				hash1[0][i] = false;
  49. 		}
  50. 		while(b--){
  51. 			in2(start,end);
  52. 			start++,end++;
  53. 			inc(i,start,end-1){
  54. 				hash1[1][i] = false;
  55. 			}
  56. 		}
  57. 		int ans = fun(1,1,0);
  58. 		ans = min(ans,fun(1,0,1));
  59. 		printf("Case #%d: %d\n",d,ans);
  60. 	}
  61. 	return 0;
  62. }
Success #stdin #stdout 0.04s 24248KB
comments (?)
stdin
copy 
5
1 1
540 600
840 900
2 0
900 1260
180 540
1 1
1439 1440
0 1
2 2
0 1
1439 1440
1438 1439
1 2
3 4
0 10
1420 1440
90 100
550 600
900 950
100 150
1050 1400
stdout
copy 
Case #1: 1
Case #2: 4
Case #3: 1
Case #4: 4
Case #5: 6
https://ideone.com/JiT8bW
language:
C++ (gcc 8.3)
created:
7 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!