fork download
copy 
  1. #include <cstdio>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <memory.h>
  6. #include <cmath>
  7. #include <map>
  8. #include <set>
  9. #include <queue>
  10. #include <stack>
  11. #include <ctime>
  12. #include <iostream>
  13. #include <functional>
  14. #include <complex>
  15. #include <stdlib.h>
  16. #include <fstream>
  17. #include <random>
  18. #include <csignal>
  19. #include <chrono> 
  20. #include <bitset>
  21. #include <unordered_set>
  22. #include <unordered_map>
  23.  
  24. using namespace std;
  25.  
  26. typedef long long ll;
  27. typedef pair<int, int> pii;
  28. typedef pair<double, double> pdd;
  29. typedef pair<pii, int> p3i;
  30. typedef vector<int> vi;
  31. typedef vector<pii> vii;
  32. typedef vector<p3i> v3i;
  33. typedef vector<vii> vvii;
  34. typedef vector<p3i> vp3i;
  35. typedef long double ld;
  36. typedef vector<ld> vld;
  37.  
  38. #define pb push_back
  39. #define mp make_pair
  40. #define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
  41. #define REPD(i, n) for (int (i) = (n) - 1; (i) >= 0; (i)--)
  42. #define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
  43. #define FORD(i,a, b) for (int (i) = (a); (i) >= (b); (i)--)
  44. #define sz(v) (int)(v).size()
  45. #define all(v) (v).begin(), (v).end()
  46. #define rv(v) reverse(all(v))
  47. #define CL(v, val) memset((v), (val), sizeof((v)))
  48. #define SORT(a) sort(all(a))
  49. #define un(v) SORT(v), (v).resize(unique(all(v)) - (v).begin())
  50. #define eps 1.0e-9
  51. #define X first
  52. #define Y second
  53. #define bit(n) (1 << (n))
  54. #define bit64(n) (ll(1) << (n))
  55. #define sqr(x) ((x) * (x))
  56. #define sq5(x) ((x) * (x) * (x) * (x) * (x))
  57. #define N 4005
  58.  
  59. int a[N][N];
  60. int sa[N][N];
  61.  
  62. int getSum(int lx, int rx, int ly, int ry) {
  63. 	int res = sa[rx][ry];
  64. 	if (lx) {
  65. 		res -= sa[lx - 1][ry];
  66. 	}
  67. 	if (ly) {
  68. 		res -= sa[rx][ly - 1];
  69. 	}
  70. 	if (lx && ly) {
  71. 		res += sa[lx - 1][ly - 1];
  72. 	}
  73.  
  74. 	return res / 2;
  75. }
  76.  
  77. int dp[N][2];
  78.  
  79. int Solve(int j, int i) {
  80. 	int ans = j ? dp[j - 1][0] : 0;
  81. 	ans += getSum(j, i, j, i);
  82. 	return ans;
  83. }
  84.  
  85. int main(void) {
  86. 	int n, k;
  87. 	scanf("%d%d", &n, &k);
  88. 	REP(i, n) {
  89. 		REP(j, n) {
  90. 			scanf("%d", &a[i][j]);
  91. 			sa[i][j] = a[i][j];
  92. 			if (i) {
  93. 				sa[i][j] += sa[i - 1][j];
  94. 			}
  95. 			if (j) {
  96. 				sa[i][j] += sa[i][j - 1];
  97. 			}
  98. 			if (i && j) {
  99. 				sa[i][j] -= sa[i - 1][j - 1];
  100. 			}
  101. 		}
  102. 	}
  103.  
  104. 	REP(i, n) {
  105. 		dp[i][0] = getSum(0, i, 0, i);
  106. 	}
  107.  
  108. 	REP(j, k - 1) {
  109. 		deque<int>q;
  110. 		q.push_back(0);
  111. 		dp[0][1] = getSum(0, 0, 0, 0);
  112. 		FOR(i, 1, n) {
  113. 			while (sz(q) >= 1) {
  114. 				int a = Solve(q.back(), i);
  115. 				int b = Solve(i, i);
  116. 				if (a <= b) {
  117. 					break;
  118. 				}
  119. 				q.pop_back();
  120. 			}
  121. 			q.push_back(i);
  122. 			while (sz(q) >= 2) {
  123. 				int a = Solve(q[0], i);
  124. 				int b = Solve(q[1], i); 
  125. 				if (a <= b) {
  126. 					break;
  127. 				}
  128. 				q.pop_front();
  129. 			}
  130. 			dp[i][1] = Solve(q[0], i);
  131. 		}
  132. 		REP(i, n) {
  133. 			dp[i][0] = dp[i][1];
  134. 		}
  135. 	}
  136.  
  137. 	printf("%d\n", dp[n - 1][0]);
  138. }
Runtime error #stdin #stdout 1.04s 66068KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qnLAn9
language:
C++14 (gcc 8.3)
created:
3 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!