Submission #81862

#	Time	Username	Problem	Language	Result	Execution time	Memory
81862		Shtef	Strah (COCI18_strah)	C++14	110 / 110	135 ms	47740 KiB

strah

#include <iostream>
#include <stack>
 
using namespace std;
 
typedef long long ll;
 
int n, m, b[2005][2005], h;
ll val[2005][2005], sol;
 
void initvals(){
    for(ll i = 1 ; i <= m ; ++i){
        val[1][i] = (i * (i + 1) * (i + 2)) / 6LL;
        //cout << val[1][i] << ' ';
    }
    //cout << endl;
    for(ll i = 2 ; i <= n ; ++i){
        for(ll j = 1 ; j <= m ; ++j){
            val[i][j] = val[1][j] * ((i * (i + 1)) / 2LL);
            //cout << val[i][j] << ' ';
        }
        //cout << endl;
    }
}
 
void histval(int a[]){
    stack <int> s;
    int t;
    int i = 0;
    while(i < m){
        if(s.empty() || a[s.top()] <= a[i]){
            s.push(i++);
        }
        else{
            //cout << i << " : " << h << endl;
            t = a[s.top()];
            s.pop();
            if(!s.empty()){
                if(t == a[s.top()])
                    continue;
                /*
                if(!(br[h + 1][i - 1] - br[h + 1][s.top()]))
                    continue;
                if(!t || !(i - s.top() - 1))
                    continue;
                */
                //cout << t << ' ' << i << ' ' << h << ' ' << s.top() << "tu1" << endl;
                sol += val[t][i - s.top() - 1];
                sol -= val[max(a[i], a[s.top()])][i - s.top() - 1];
            }
            else{
                /*
                if(!br[h + 1][i - 1])
                    continue;
                if(!t || !i)
                    continue;
                */
                //cout << t << ' ' << i << ' ' << h << "tu2" << endl;
                sol += val[t][i];
                sol -= val[max(a[i], 0)][i];
            }
        }
    }
    while(!s.empty()){
        t = a[s.top()];
        s.pop();
        if(!s.empty()){
            if(t == a[s.top()])
                continue;
            /*
            if(!(br[h + 1][i - 1] - br[h + 1][s.top()]))
                continue;
            if(!t || !(i - s.top() - 1))
                continue;
            */
            //cout << t << ' ' << i << ' ' << h << ' ' << s.top() << "tu3" << endl;
            sol += val[t][i - s.top() - 1];
            sol -= val[max(a[s.top()], 0)][i - s.top() - 1];
        }
        else{
            /*
            if(!br[h + 1][i - 1])
                continue;
            if(!t || !i)
                continue;
            */
            //cout << t << ' ' << i << ' ' << h << "tu4" << endl;
            sol += val[t][i];
        }
    }
}
 
void getval(){
    histval(b[0]);
    //cout << sol << endl;
    for(int i = 1 ; i < n ; ++i){
        h = i;
        for(int j = 0 ; j < m ; ++j){
            if(b[i][j]){
                b[i][j] += b[i - 1][j];
            }
            //cout << b[i][j] << ' ';
        }
        //cout << endl << endl;
        histval(b[i]);
        //cout << sol << endl;
    }
}
 
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
initvals();
for(int i = 0 ; i < n ; ++i){
    string s;
    cin >> s;
    for(int j = 0 ; j < m ; ++j){
        b[i][j] = (s[j] == '.');
    }
}
getval();
cout << sol << 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