Submission #464691

#	Time	Username	Problem	Language	Result	Execution time	Memory
464691		aihay	Strah (COCI18_strah)	C++14	110 / 110	136 ms	8516 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],arr[2010],x,y;
long long ans;
string s[2010];
stack<int> st;

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++){
            cin>>s[i];
            for(int j=0;j<m;j++){
                if(s[i][j]=='.')
                    csum[j]=csum[j]+1;
                else
                    csum[j]=0;
            }
            for(int j=0;j<m;j++){
                while(st.size()&&csum[j]<csum[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++){
                x=j,y=arr[j];
                while(x&&csum[x-1]>csum[j]){
                    x--;
                }
                ans+=((y-j+1ll)*(y-j+2ll)/2ll*(j-x+1ll)+(j-x+1ll)*(j-x)/2ll*(y-j+1ll))*((csum[j]*(csum[j]+1ll))/2ll);
            }
        }
        cout<<ans<<endl;
    }
}

Compilation message (stderr)

strah.cpp:18:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int MAAX=1e18;
      |                ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11