oj.uz

Submission #464679

# Submission time Handle Problem Language Result Execution time Memory
464679 2021-08-13T16:37:57 Z aihay Strah (COCI18_strah) C++14
22 / 110
 41 ms 1040 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef int in;
#define int long long
#define f first
#define s second
#define pb push_back
#define pp push
#define double long double
#define ceil(x,y) (x/y)+(x%y!=0)*((double)(1.0*x/y)<0?0:1)
#define floor(x,y) (x/y)+(x%y!=0)*((double)(1.0a*x/y)<0?-1:0)
const int MAX=1e7;
const int MOD=1e9+7;
const int MAAX=1e18;

int n,m,csum[10010][10010],arr[10010][10010];
string s[10010];

in main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc=1;
    //cin>>tc;
    while(tc--){
        cin>>n>>m;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>s[i][j];
                if(s[i][j]=='.')
                    csum[i][j]=csum[max(0ll,i-1)][j]+1;
            }
        }
        int ans=0;
        for(int i=0;i<n;i++){
            stack<int> st;
            for(int j=0;j<m;j++){
                while(st.size()&&csum[i][j]<csum[i][st.top()]){
                    arr[i][st.top()]=j-1;
                    st.pop();
                }
                st.pp(j);
            }
            while(st.size()){
                arr[i][st.top()]=m-1;
                st.pop();
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int x=j,y=arr[i][j];
                while(x&&csum[i][x-1]>csum[i][j]){
                    x--;
                }
                ans+=((y-j+1)*(y-j+2)/2*(j-x+1)+(j-x+1)*(j-x)/2*(y-j+1))*((csum[i][j]*(csum[i][j]+1))/2);
            }
        }
        cout<<ans<<endl;
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 716 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 1040 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -