oj.uz

Submission #15560

# Submission time Handle Problem Language Result Execution time Memory
15560 2015-07-12T19:24:16 Z Fakeable 빨간 직사각형 (kriii3_QQ) C++
0 / 20
 0 ms 6692 KB 
#include<iostream>
#include<algorithm>
#include<memory.h>
#include<stack>
#include<utility>
using namespace std;
const int max_n = 1010;
int n,m,h[max_n][max_n];
long long ans;
char a[max_n][max_n];
int main() {
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) if(a[0][i]=='R') h[0][i] = 1;
    for(int i=1;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(a[i][j] == 'R') h[i][j] = h[i-1][j]+1;
        }
    }
    for(int i=0;i<n;i++) {
        stack<pair<int,int> > s;
        s.push(make_pair(-1,-1));
        for(int j=0;j<m;j++) {
            pair<int,int> now = make_pair(j,h[i][j]);
            while(1) {
                pair<int,int> T = s.top();
                if(T.second >= now.second) s.pop();
                else break;
            }
            int width = j-s.top().first;
            ans += 1LL * width * now.second;
            s.push(now);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6692 KB Output is correct
2 Incorrect 0 ms 6692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -