Submission #464686

#	Time	Username	Problem	Language	Result	Execution time	Memory
464686		aihay	Strah (COCI18_strah)	C++14	22 / 110	3 ms	588 KiB

strah

#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[2010][2010],arr[100010];
string s[2010];

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[st.top()]=j-1;
                    st.pop();
                }
                st.pp(j);
            }
            while(st.size()){
                arr[st.top()]=m-1;
                st.pop();
            }
            for(int j=0;j<m;j++){
                int x=j,y=arr[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 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11