Submission #119291

#	Time	Username	Problem	Language	Result	Execution time	Memory
119291		OptxPrime	Strah (COCI18_strah)	C++11	110 / 110	481 ms	35832 KiB

strah

#include <iostream>
#include <cmath>
#include <algorithm>
#include <utility>
#include<stack>

using namespace std;

#define pb push_back
#define mp make_pair

int h[2010],levo[2010],desno[2010];
char a[2010][2010];
long long dp[2010][2010];

int main()
{
   int n,m;
   long long res=0;
   cin>>n>>m;
   for(int i=0;i<m;i++) h[i]=n;
   for( long long i=1;i<=n;i++ ) dp[i][1]=i*(i+1)/2;

   for( long long i=1;i<=n;i++ ){
    for( long long j=2;j<=m;j++ ) dp[i][j] = dp[i][j-1] + (long long)(( i*(i+1)*j*(j+1) )/4);
   }

   stack<int> s;
   for(int i=0;i<n;i++ ){
    for( int j=0;j<m;j++ )cin>>a[i][j];
   }

   for( int i=0;i<n;i++ ){
    for( int j=0;j<m;j++ ){
    //    cin>>a[i][j];
        if( a[i][j] == '#' ){
            h[j]=n-i-1;
            s.push(j);
            continue;
        }
        if( s.empty() ){
            levo[j]=-1;
            s.push(j);
            continue;
        }
        int curr=s.top();
       // cout << " skaka " <<endl;
        while( h[curr] > h[j] ){
            s.pop();
            if( s.empty() ) break;
            else curr=s.top();
        }
      //  cout<< " ee  " <<endl;
        if( s.empty() ) levo[j]=-1;
       else levo[j] = curr;
        s.push(j);
    }
        while( !s.empty() ) s.pop();
        for( int j=m-1;j>=0;j-- ){
                if( a[i][j] =='#' ){
                   // h[j]=n-i-1;
                    s.push(j);
                    continue;
                }
            if( s.empty() ) {
                    desno[j] = m;
                    s.push(j);
                    continue;
            }
            int curr=s.top();
            while( h[curr] >= h[j] ){
                s.pop();
                if( s.empty() ) break;
                else curr=s.top();
            }
            if( s.empty() ) desno[j] = m;
            else desno[j] = curr;
            s.push(j);
        }
       /* for( int j=0;j<m;j++ ){
            cout << i << " " << j << " " << levo[j] << " " << desno[j] << " hehe " <<endl;
        }*/

        while( !s.empty() ) s.pop();
        for( int j=0;j<m;j++ ){
                if( a[i][j] == '#' ) continue;
       //         cout << i << " " << j << " " <<" " << h[j] << " "<<h[j]-( n-i-1 ) << " dosta " <<endl;
        long long vis =(long long)( h[j]-( n-i-1 ) );
        long long velka= (long long)(desno[j]-levo[j]-1);
        long long mala1=(long long)(desno[j]-j-1);
        long long mala2=(long long)(j-levo[j]-1);
       // cout << i << " " << j << " " << " " << vis << " " << velka << " " << mala1 << " " << mala2 << " " << dp[vis][velka] << " rahib " <<endl;
        res+=dp[vis][velka];
        res-=dp[vis][mala1];
        res-=dp[vis][mala2];
        //    cout << dp[1][2] << " bratee " <<endl;
        }


   }
        cout<<res<<endl;

    return 0;
}

• 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