//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int MAX_N = 100002;
const int MAX_M = 52;
struct event {
int a, b, row;
event() {}
event(int a, int b, int row):
a(a), b(b), row(row) {}
bool operator<(const event& T) {
return row>T.row;
}
};
struct dsu {
int cnt_0, cnt_1;
vector<int> lab;
vector<bool> left_side;
void clear(int _n) {
cnt_0 = cnt_1 = 0;
lab.clear();
left_side.clear();
lab.resize(_n+1);
left_side.resize(_n+1);
}
int findset(int u) {
return lab[u]<=0 ? u : lab[u] = findset(lab[u]);
}
void uni(int s, int t) {
s = findset(s);
t = findset(t);
if (s==t)
return;
if (lab[s]>lab[t])
swap(s, t);
if (lab[s]==lab[t])
--lab[s];
lab[t] = s;
if (left_side[t] && left_side[s])
--cnt_1;
else
--cnt_0;
}
};
int n, m, f[2][MAX_M][MAX_M];
char a[MAX_M][MAX_N];
dsu D;
vector<event> E;
void enter() {
scanf("%d%d\n", &m, &n);
for (int i=1; i<=m; ++i) {
for (int j=1; j<=n; ++j) {
a[j][i] = getchar();
}
getchar();
}
swap(m, n);
}
void solve() {
int64_t res = 0;
int p = 0;
for (int c=1; c<=n; ++c) {
p ^= 1;
for (int i=1; i<=m; ++i) {
if (a[i][c]=='1')
f[p][i][i] = c;
else
f[p][i][i] = 0;
}
for (int i=m; i>=1; --i) {
for (int j=i+1; j<=m; ++j) {
if (i!=j && a[i][c]!='0' && a[j][c]!='0')
f[p][j][i] = f[p][i][j] = max(max(f[p][i+1][j], f[p][i][j-1]), f[p^1][i][j]);
else
f[p][i][j] = f[p][j][i] = 0;
}
}
D.clear(m);
for (int i=1; i<=m; ++i) {
if (a[i][c]=='1')
++D.cnt_0;
if (c<n && a[i][c]=='1' && a[i][c+1]=='1') {
--D.cnt_0;
++D.cnt_1;
D.left_side[i] = true;
}
}
E.clear();
for (int i=1; i<=m; ++i) {
for (int j=i+1; j<=m; ++j) {
if (i!=j && f[p][i][j]>0 && f[p][i][j]<c) {
E.push_back(event(i, j, f[p][i][j]));
}
if (i!=j && f[p][i][j]==c)
D.uni(i, j);
}
}
sort(E.begin(), E.end());
int _prev = c;
for (int i=0; i<E.size(); ++i) {
res += 1LL * D.cnt_0 * (n - c + 1) * (_prev - E[i].row);
res += 1LL * D.cnt_1 * (_prev - E[i].row);
int j = i - 1;
while (j+1<E.size() && E[j+1].row == E[i].row) {
++j;
D.uni(E[j].a, E[j].b);
}
_prev = E[i].row;
i = j;
}
res += 1LL * D.cnt_0 * (n - c + 1) * _prev;
res += 1LL * D.cnt_1 *_prev;
}
cout << res;
}
int main() {
//#define OFFLINE_JUDGE doraemon
#ifdef OFFLINE_JUDGE
freopen(FILE_NAME".inp", "r", stdin);
//freopen(FILE_NAME".out", "w", stdout);
#endif
enter();
solve();
}
Compilation message
raspad.cpp: In function 'void solve()':
raspad.cpp:118:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<E.size(); ++i) {
~^~~~~~~~~
raspad.cpp:122:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j+1<E.size() && E[j+1].row == E[i].row) {
~~~^~~~~~~~~
raspad.cpp: In function 'void enter()':
raspad.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d\n", &m, &n);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
744 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
744 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
87 ms |
1236 KB |
Output is correct |
| 2 |
Incorrect |
166 ms |
1900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
744 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
