#include "dzialka.h" #include "message.h" #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int MAXN = 2001; int n, m; int non, myid; vector <vector <int> > t; void pre(); inline int get_sum(int x, int y, int a, int b); inline bool is_ok(int x, int y, int a, int b); int main() { non = NumberOfNodes(); myid = MyNodeId(); pre(); int chunk_size = n / non + 1; int my_start = chunk_size * myid, next_start = chunk_size * (myid + 1); int upper_limit = min(next_start, n); long long my_result = 0LL; for(int i = my_start; i < upper_limit; ++i) { for(int j = 0; j < m; ++j) { int l_limiter = m; for(int k = i; k < n; ++k) { for(int l = j; l < m and l < l_limiter; ++l) { if(is_ok(i + 1, j + 1, k + 1, l + 1)) { my_result += 1LL; } else { l_limiter = l; } } } } } if(myid == 0) { long long result = my_result; for(int i = 1; i < non; ++i) { Receive(i); result += GetLL(i); } printf("%lld\n", result); } else { PutLL(0, my_result); Send(0); } return 0; } void pre() { n = GetFieldHeight(); m = GetFieldWidth(); t.resize(n + 1); for(int i = 0; i <= n; ++i) { t[i].resize(m + 1); t[i][0] = 0; } for(int j = 0; j <= m; ++j) { t[0][j] = 0; } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { int add = IsUsableCell(i, j); t[i + 1][j + 1] = t[i][j + 1] + t[i + 1][j] - t[i][j] + add; } } } inline int get_sum(int x, int y, int a, int b) { return t[a][b] - t[x - 1][b] - t[a][y - 1] + t[x - 1][y - 1]; } inline bool is_ok(int x, int y, int a, int b) { return get_sum(x, y, a, b) == (a - x + 1) * (b - y + 1); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | #include "dzialka.h" #include "message.h" #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int MAXN = 2001; int n, m; int non, myid; vector <vector <int> > t; void pre(); inline int get_sum(int x, int y, int a, int b); inline bool is_ok(int x, int y, int a, int b); int main() { non = NumberOfNodes(); myid = MyNodeId(); pre(); int chunk_size = n / non + 1; int my_start = chunk_size * myid, next_start = chunk_size * (myid + 1); int upper_limit = min(next_start, n); long long my_result = 0LL; for(int i = my_start; i < upper_limit; ++i) { for(int j = 0; j < m; ++j) { int l_limiter = m; for(int k = i; k < n; ++k) { for(int l = j; l < m and l < l_limiter; ++l) { if(is_ok(i + 1, j + 1, k + 1, l + 1)) { my_result += 1LL; } else { l_limiter = l; } } } } } if(myid == 0) { long long result = my_result; for(int i = 1; i < non; ++i) { Receive(i); result += GetLL(i); } printf("%lld\n", result); } else { PutLL(0, my_result); Send(0); } return 0; } void pre() { n = GetFieldHeight(); m = GetFieldWidth(); t.resize(n + 1); for(int i = 0; i <= n; ++i) { t[i].resize(m + 1); t[i][0] = 0; } for(int j = 0; j <= m; ++j) { t[0][j] = 0; } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { int add = IsUsableCell(i, j); t[i + 1][j + 1] = t[i][j + 1] + t[i + 1][j] - t[i][j] + add; } } } inline int get_sum(int x, int y, int a, int b) { return t[a][b] - t[x - 1][b] - t[a][y - 1] + t[x - 1][y - 1]; } inline bool is_ok(int x, int y, int a, int b) { return get_sum(x, y, a, b) == (a - x + 1) * (b - y + 1); } |