oj.uz

Submission #119291

# Submission time Handle Problem Language Result Execution time Memory
119291 2019-06-21T00:10:19 Z OptxPrime Strah (COCI18_strah) C++11
110 / 110
 481 ms 35832 KB 
#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.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2816 KB Output is correct
2 Correct 11 ms 2944 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2944 KB Output is correct
2 Correct 11 ms 2944 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 13676 KB Output is correct
2 Correct 230 ms 27140 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 23908 KB Output is correct
2 Correct 350 ms 34652 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 15608 KB Output is correct
2 Correct 252 ms 28804 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13304 KB Output is correct
2 Correct 248 ms 33736 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 35732 KB Output is correct
2 Correct 340 ms 35832 KB Output is correct