fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MOD = 1e9 + 7;
  6. const int N = 2010;
  7.  
  8. int n, m, dp[N][N], kol[N][N], q, l[N][N], u[N][N];
  9.  
  10. inline void solve()
  11. {
  12. 	cin >> n >> m >> q;
  13. 	for (int i = 0; i < n; i++)
  14. 		for (int j = 0; j < m; j++)
  15. 			l[i][j] = j, u[i][j] = i;
  16. 	for (int i = 0; i < q; i++)
  17. 	{
  18. 		int x1, y1, x2, y2;
  19. 		cin >> x1 >> y1 >> x2 >> y2;
  20. 		x1--, x2--, y1--, y2--;
  21. 		if (x1 == x2 || y1 == y2) continue;
  22. 		for (int x = x1 + 1; x <= x2; x++)
  23. 			for (int y = y1 + 1; y <= y2; y++)
  24. 				l[x][y] = min(l[x][y], y1), u[x][y] = min(u[x][y], x1);
  25. 	}
  26. 	for (int s = 0; s <= (n + m - 2); s++)
  27. 		for (int i = 0; i < min(s + 1, n); i++)
  28. 		{
  29. 			int j = (s - i);
  30. 			if (j < 0 || j >= m) continue;
  31. 			dp[i][j] = 1;
  32. 			kol[i][j] = 1;
  33. 			if (i == 0 || j == 0) continue;
  34. 			for (int y = l[i][j]; y < j; y++)
  35. 				if (dp[i][j] <= dp[i - 1][y] + 1)
  36. 				{
  37. 					if (dp[i][j] < dp[i - 1][y] + 1)
  38. 					{	
  39. 						dp[i][j] = dp[i - 1][y] + 1;    
  40. 						kol[i][j] = 0;
  41. 					}
  42. 					kol[i][j] += kol[i - 1][y];
  43. 					if (kol[i][j] >= MOD) kol[i][j] -= MOD;
  44. 				}
  45. 			for (int x = u[i][j]; x < i; x++)
  46. 				if (dp[i][j] <= dp[x][j - 1] + 1)
  47. 				{
  48. 					if (dp[i][j] < dp[x][j - 1] + 1)
  49. 					{	
  50. 						dp[i][j] = dp[x][j - 1] + 1;
  51. 						kol[i][j] = 0;
  52. 					}
  53. 					kol[i][j] += kol[x][j - 1];
  54. 					if (kol[i][j] >= MOD) kol[i][j] -= MOD;
  55. 				}
  56. 			if (l[i][j] < j && u[i][j] < i && dp[i][j] == dp[i - 1][j - 1] + 1)
  57. 			{
  58. 				kol[i][j] -= kol[i - 1][j - 1];
  59. 				if (kol[i][j] < 0) kol[i][j] += MOD;
  60. 			}
  61. 		}   
  62. 	int mx = 0;
  63. 	int ans = 0;
  64. 	for (int i = 0; i < n; i++)
  65. 		for (int j = 0; j < m; j++)
  66.  			mx = max(mx, dp[i][j]);
  67. 	for (int i = 0; i < n; i++)
  68. 		for (int j = 0; j < m; j++)
  69. 			if (mx == dp[i][j])   
  70. 			{
  71. 				ans += kol[i][j];
  72. 				if (ans >= MOD) ans -= MOD;
  73. 			}
  74. 	cout << mx << " " << ans << "\n";								
  75. }
  76.  
  77. int main()
  78. {
  79. 	ios::sync_with_stdio(0);
  80. 	int T;
  81. 	cin >> T;
  82. 	for (int z = 0; z < T; z++)
  83. 		solve();
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
3
3 4 2
1 1 2 2
2 2 3 4
3 3 2
1 1 3 3
1 1 3 3
6 6 2
1 1 4 3
3 2 5 5
stdout
copy 
3 2
3 1
5 1
https://ideone.com/laqEDk
language:
C++14 (gcc 8.3)
created:
5 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!