제출 #1276474

#제출 시각아이디문제언어결과실행 시간메모리
1276474Ivo_12Sandcastle 2 (JOI22_ho_t5)C++20
100 / 100
431 ms15800 KiB
#include <bits/stdc++.h> #define mp make_pair #define F first #define S second #define pb push_back #define pii pair < int, int > #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) typedef long long ll; using namespace std; const ll inf = (ll) 1e11; const vector < ll > nul; int h, w; vector < vector < ll > > mat; vector < vector < ll > > prefsum[16];// 1 = x + 1, 2 = y + 1, 4 = x - 1, 8 = y - 1 pii dir[4] = {mp(0, 1), mp(1, 0), mp(0, -1), mp(-1, 0)}; int l2[16] = {0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3}; unordered_map < ll, ll > rep; bool inbounds( int y, int x ) {return (y >= 0 && y < h && x >= 0 && x < w);} void flipmat( void ) { vector < vector < ll > > newmat; for(int i = 0; i < w; i++) { newmat.pb(nul); for(int j = 0; j < h; j++) { newmat[i].pb(mat[j][i]); } } mat = newmat; swap(h, w); return; } ll rec( int k, int y1, int x1, int y2, int x2 ) { return prefsum[k][y1][x1] - prefsum[k][y2][x1] - prefsum[k][y1][x2] + prefsum[k][y2][x2]; } void task( void ) { cin >> h >> w; for(int i = 0; i < h; i++) { mat.pb(nul); for(int j = 0; j < w; j++) { mat[i].pb(0); cin >> mat[i][j]; } } if(h > w) flipmat(); int curbit; int prevval; //mark sus for(int i = 0; i < 16; i++) { prefsum[i].pb(nul); for(int j = 0; j < w + 1; j++) prefsum[i][0].pb(0); curbit = l2[i & -i]; for(int j = 1; j < h + 1; j++) { prefsum[i].pb(nul); prefsum[i][j].pb(0); for(int z = 1; z < w + 1; z++) { prefsum[i][j].pb(mat[j - 1][z - 1]); } } if(i != 0) { prevval = i - (i&-i); for(int j = 1; j < h + 1; j++) { for(int z = 1; z < w + 1; z++) { prefsum[i][j][z] = prefsum[prevval][j][z]; if(inbounds(j + dir[curbit].F - 1, z + dir[curbit].S - 1) && mat[j + dir[curbit].F - 1][z + dir[curbit].S - 1] < mat[j - 1][z - 1]) prefsum[i][j][z] = min(prefsum[prevval][j][z], mat[j - 1][z - 1] - mat[j + dir[curbit].F - 1][z + dir[curbit].S - 1]); } } } } //mark the biggest bool biggest; for(int i = 0; i < 16; i++) { for(int j = 0; j < h; j++) { for(int z = 0; z < w; z++) { biggest = 1; for(int k = 0; k < 4; k++) { if(inbounds(j + dir[k].F, z + dir[k].S) && ((1<<k) & i) && mat[j + dir[k].F][z + dir[k].S] > mat[j][z]) biggest = 0; } if(biggest) prefsum[i][j + 1][z + 1] += inf - mat[j][z]; } } } //make sums for(int i = 0; i < 16; i++) { for(int j = 1; j < h + 1; j++) { for(int z = 1; z < w + 1; z++) { prefsum[i][j][z] += prefsum[i][j - 1][z] + prefsum[i][j][z - 1] - prefsum[i][j - 1][z - 1]; } } } ll cur = 0; ll sol = 0; for(int i = 0; i < h; i++) { for(int j = i; j < h; j++) { cur = 0; rep.clear(); for(int z = 0; z < w; z++) { if(j - i > 0) { if(rec(2, i, z, i + 1, z + 1) + rec(8, j, z, j + 1, z + 1) + rec(10, i + 1, z, j, z + 1) == inf) sol++; sol += rep[inf - rec(6, i, z, i + 1, z + 1) - rec(12, j, z, j + 1, z + 1) - rec(14, i + 1, z, j, z + 1) - cur]; cur += rec(7, i, z, i + 1, z + 1) + rec(13, j, z, j + 1, z + 1) + rec(15, i + 1, z, j, z + 1); rep[rec(3, i, z, i + 1, z + 1) + rec(9, j, z, j + 1, z + 1) + rec(11, i + 1, z, j, z + 1) - cur]++; } else { sol++; sol += rep[inf - rec(4, i, z, i + 1, z + 1) - cur]; cur += rec(5, i, z, i + 1, z + 1); rep[rec(1, i, z, i + 1, z + 1) - cur]++; } } } } cout << sol << "\n"; return; } int main( void ) { FIO; task(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...