제출 #809199

#제출 시각아이디문제언어결과실행 시간메모리
809199Username4132Rectangles (IOI19_rect)C++14
27 / 100
570 ms1048576 KiB
#include "rect.h" #include<iostream> #include<vector> #include<bitset> using namespace std; using ll = long long; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define forsn(i, s, n) for(int i=s; i<(int)n; ++i) #define dforn(i, n) for(int i=n-1; i>=0; --i) #define dforsn(i, s, n) for(int i=n-1; i>=s; --i) #define PB push_back const int MAXN = 710; bitset<MAXN> mask[MAXN][MAXN]; // column, start row bitset<MAXN> one("1"), full; int n, m, arr[MAXN][MAXN], brr[MAXN][MAXN]; int far[MAXN][MAXN][MAXN]; // row, l, r void calc1(){ dforn(row, n){ forsn(i, 1, m-1){ int mx = -1; forsn(j, i, m-1){ mx = max(mx, arr[row][j]); if(mx<arr[row][i-1] && mx<arr[row][j+1]){ far[row][i][j]=far[row+1][i][j]; } else far[row][i][j]=row; } } } } void calc2(){ forn(col, m){ forsn(i, 1, n-1){ int mx = -1; forsn(j, i, n-1){ mx = max(mx, brr[col][j]); if(mx<brr[col][i-1] && mx<brr[col][j+1]){ mask[i][col]|=(one<<j); } } } } } long long count_rectangles(std::vector<std::vector<int> > a) { n=(int)a.size(), m=(int)a.front().size(); forn(i, 800) full|=(one<<i); forn(i, n) forn(j, m) brr[j][i]=arr[i][j]=a[i][j]; forn(i, m) forn(j, m) far[n][i][j]=n; calc1(); calc2(); ll ans=0; forsn(row, 1, n-1){ forsn(i, 1, m-1){ bitset<MAXN> bt=full; forsn(j, i, m-1){ bt&=mask[row][j]; ans+=(bt&(~(full<<far[row][i][j]))).count(); } } } return ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...