#include <iostream> #include <queue> #include <algorithm> #include "message.h" #include "dzialka.h" using namespace std; /* bool isUsableCell(int h, int w) { int res; cin >> res; return res; } */ struct candid { int startCol; int height; }; unsigned long long result = 0; queue<candid> candids; /* 5 5 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 */ int main() { ios_base::sync_with_stdio(0); if (MyNodeId() == 0) { int h, w; h = GetFieldHeight(); w = GetFieldWidth(); int upCount[20000][20000]; // -1: not usable int isUsable; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { isUsable = IsUsableCell(i, j); if (!isUsable) upCount[i][j] = -1; else if (i != 0 && upCount[i - 1][j] != -1) upCount[i][j] = upCount[i - 1][j] + 1; else upCount[i][j] = 0; if (isUsable) result += upCount[i][j] + 1; } } for (int i = 0; i < h; i++) { int prevHeight = 0; for (int j = 0; j < w; j++) { candid a; a.height = a.startCol = -1; candids.push(a); int maxLengthHigher = 0; bool wasEqual = false; while (true) { candid curr = candids.front(); candids.pop(); if (curr.height == -1 && curr.startCol == -1) break; if (curr.height > upCount[i][j] + 1) maxLengthHigher = max(maxLengthHigher, j - curr.startCol); else { candids.push(curr); if (curr.height == upCount[i][j] + 1) wasEqual = true; result += curr.height * (j - curr.startCol); //cout << "h: " << i << " w: " << j << " start: " << curr.startCol << " haj: " << curr.height << " result: " << result << "\n"; } } if (prevHeight < upCount[i][j] + 1 || !wasEqual) { candid extend; extend.height = upCount[i][j] + 1; extend.startCol = j - maxLengthHigher; candids.push(extend); if (maxLengthHigher > 0) result += extend.height * (j - extend.startCol); } prevHeight = upCount[i][j] + 1; } queue<candid> empty; candids = empty; } cout << result << "\n"; } }
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 90 91 92 93 94 95 96 97 98 99 100 101 | #include <iostream> #include <queue> #include <algorithm> #include "message.h" #include "dzialka.h" using namespace std; /* bool isUsableCell(int h, int w) { int res; cin >> res; return res; } */ struct candid { int startCol; int height; }; unsigned long long result = 0; queue<candid> candids; /* 5 5 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 */ int main() { ios_base::sync_with_stdio(0); if (MyNodeId() == 0) { int h, w; h = GetFieldHeight(); w = GetFieldWidth(); int upCount[20000][20000]; // -1: not usable int isUsable; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { isUsable = IsUsableCell(i, j); if (!isUsable) upCount[i][j] = -1; else if (i != 0 && upCount[i - 1][j] != -1) upCount[i][j] = upCount[i - 1][j] + 1; else upCount[i][j] = 0; if (isUsable) result += upCount[i][j] + 1; } } for (int i = 0; i < h; i++) { int prevHeight = 0; for (int j = 0; j < w; j++) { candid a; a.height = a.startCol = -1; candids.push(a); int maxLengthHigher = 0; bool wasEqual = false; while (true) { candid curr = candids.front(); candids.pop(); if (curr.height == -1 && curr.startCol == -1) break; if (curr.height > upCount[i][j] + 1) maxLengthHigher = max(maxLengthHigher, j - curr.startCol); else { candids.push(curr); if (curr.height == upCount[i][j] + 1) wasEqual = true; result += curr.height * (j - curr.startCol); //cout << "h: " << i << " w: " << j << " start: " << curr.startCol << " haj: " << curr.height << " result: " << result << "\n"; } } if (prevHeight < upCount[i][j] + 1 || !wasEqual) { candid extend; extend.height = upCount[i][j] + 1; extend.startCol = j - maxLengthHigher; candids.push(extend); if (maxLengthHigher > 0) result += extend.height * (j - extend.startCol); } prevHeight = upCount[i][j] + 1; } queue<candid> empty; candids = empty; } cout << result << "\n"; } } |