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;
  9. vector<pair<int, int> > to[N][N];
  10.  
  11. inline void solve()
  12. {
  13. 	cin >> n >> m >> q;
  14. 	for (int i = 0; i < n; i++)
  15. 		for (int j = 0; j < m; j++)
  16. 			to[i][j].clear();
  17. 	for (int i = 0; i < q; i++)
  18. 	{
  19. 		int x1, y1, x2, y2;
  20. 		cin >> x1 >> y1 >> x2 >> y2;
  21. 		x1--, x2--, y1--, y2--;
  22. 		for (int xa1 = x1; xa1 <= x2; xa1++)
  23. 			for (int ya1 = y1; ya1 <= y2; ya1++)
  24. 				for (int xa2 = xa1 + 1; xa2 <= x2; xa2++)
  25. 					for (int ya2 = ya1 + 1; ya2 <= y2; ya2++)
  26. 						to[xa1][ya1].push_back(make_pair(xa2, ya2));		
  27. 	}
  28. 	for (int i = 0; i < n; i++)
  29. 		for (int j = 0; j < m; j++)
  30. 		{	
  31. 			sort(to[i][j].begin(), to[i][j].end());
  32. 			to[i][j].resize(unique(to[i][j].begin(), to[i][j].end()) - to[i][j].begin());	
  33. 		}	
  34. 	for (int i = 0; i < n; i++)
  35. 		for (int j = 0; j < m; j++)
  36. 		{
  37. 			dp[i][j] = 1;
  38. 			kol[i][j] = 1;
  39. 		}
  40. 	for (int s = 0; s <= (n + m - 2); s++)
  41. 		for (int i = 0; i < min(s + 1, n); i++)
  42. 		{
  43. 			int j = (s - i);
  44. 			if (j < 0 || j >= m) continue;
  45. 			for (pair<int, int> t : to[i][j])
  46. 			{
  47. 				if (dp[t.first][t.second] > dp[i][j] + 1) continue;
  48. 				if (dp[t.first][t.second] < dp[i][j] + 1) 
  49. 				{
  50. 					dp[t.first][t.second] = dp[i][j] + 1;
  51. 					kol[t.first][t.second] = 0;
  52. 				}
  53. 				kol[t.first][t.second] += kol[i][j];
  54. 				if (kol[t.first][t.second] >= MOD) kol[t.first][t.second] -= MOD;
  55. 			}
  56. 		}
  57. 	int mx = 0;
  58. 	int ans = 0;
  59. 	for (int i = 0; i < n; i++)
  60. 		for (int j = 0; j < m; j++)
  61.  			mx = max(mx, dp[i][j]);
  62. 	for (int i = 0; i < n; i++)
  63. 		for (int j = 0; j < m; j++)
  64. 			if (mx == dp[i][j])   
  65. 			{
  66. 				ans += kol[i][j];
  67. 				if (ans >= MOD) ans -= MOD;
  68. 			}
  69. 	cout << mx << " " << ans << "\n";						
  70. }
  71.  
  72. int main()
  73. {
  74. 	ios::sync_with_stdio(0);
  75. 	int T;
  76. 	cin >> T;
  77. 	for (int z = 0; z < T; z++)
  78. 		solve();
  79. 	return 0;
  80. }
Success #stdin #stdout 0.05s 97760KB
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/FkXsaP
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!