| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 15562 |
2015-07-12T21:21:47 Z |
Fakeable |
빨간 직사각형 (kriii3_QQ) |
C++ |
|
252 ms |
1764 KB |
#include<iostream>
#include<stack>
#include<memory.h>
#include<stdlib.h>
#define pi pair<int,int>
#define mp make_pair
using namespace std;
const int max_n = 3030;
int n,m,h[max_n],l[max_n],r[max_n],lbnd[max_n];
long long ans;
char a[max_n];
inline long long comb(int x) {
return 1LL * x*(x+1)/2;
}
int main() {
ios_base::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<n;i++) {
cin>>a;
for(int j=0;j<m;j++) {
if(a[j]=='R') h[j]++;
else h[j] = 0;
}
stack<pi> s;
s.push(mp(-1,-1));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(lbnd,0,sizeof(lbnd));
for(int j=0;j<m;j++) {
while(1) {
pi T = s.top();
if(T.second > h[j]) {
s.pop();
r[T.first] = j;
lbnd[T.first] = max(lbnd[T.first], h[j]);
}
else break;
}
if(s.top().second == h[j]) {
pi T= s.top();
l[j] = l[T.first];
lbnd[j] = lbnd[T.first];
s.pop();
}
else {
l[j] = s.top().first;
lbnd[j] = (s.top().second == -1) ? 0 : s.top().second;
}
s.push(mp(j,h[j]));
}
while(!s.empty()) {
int now = s.top().first;
r[now] = m;
s.pop();
}
for(int j=0;j<m;j++) {
if(r[j]) {
ans += comb(r[j]-l[j]-1) * (h[j]-lbnd[j]);
}
}
}
cout<<ans<<endl;
return 0;
}
/*
1
3+1=4
6+4=10
10+10=20
15+20=35
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 22 |
Correct |
4 ms |
1764 KB |
Output is correct |
| 23 |
Correct |
6 ms |
1764 KB |
Output is correct |
| 24 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 25 |
Correct |
0 ms |
1764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1764 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 6 |
Correct |
14 ms |
1764 KB |
Output is correct |
| 7 |
Correct |
13 ms |
1764 KB |
Output is correct |
| 8 |
Correct |
11 ms |
1764 KB |
Output is correct |
| 9 |
Correct |
19 ms |
1764 KB |
Output is correct |
| 10 |
Correct |
16 ms |
1764 KB |
Output is correct |
| 11 |
Correct |
9 ms |
1764 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1764 KB |
Output is correct |
| 13 |
Correct |
19 ms |
1764 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 22 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 23 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 24 |
Correct |
13 ms |
1764 KB |
Output is correct |
| 25 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 26 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 27 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 28 |
Correct |
8 ms |
1764 KB |
Output is correct |
| 29 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 30 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 31 |
Correct |
87 ms |
1764 KB |
Output is correct |
| 32 |
Correct |
0 ms |
1764 KB |
Output is correct |
| 33 |
Correct |
92 ms |
1764 KB |
Output is correct |
| 34 |
Correct |
105 ms |
1764 KB |
Output is correct |
| 35 |
Correct |
147 ms |
1764 KB |
Output is correct |
| 36 |
Correct |
155 ms |
1764 KB |
Output is correct |
| 37 |
Correct |
197 ms |
1764 KB |
Output is correct |
| 38 |
Correct |
219 ms |
1764 KB |
Output is correct |
| 39 |
Correct |
252 ms |
1764 KB |
Output is correct |
| 40 |
Correct |
139 ms |
1764 KB |
Output is correct |
