Submission #167666

#	Time	Username	Problem	Language	Result	Execution time	Memory
167666		rzbt	Strah (COCI18_strah)	C++14	110 / 110	189 ms	129960 KiB

strah

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 2005
typedef long long ll;


using namespace std;

ll n,m;
ll iznad[MAXN][MAXN],mat[MAXN][MAXN],res[MAXN][MAXN],zbirvis[MAXN][MAXN];
char ss[MAXN];
stack<pair<ll,ll> > s;
ll sol;
int main()
{
    scanf("%lld %lld", &n, &m);
    for(ll i=1;i<=n;i++){
        scanf("%s",ss);
        for(ll j=1;j<=m;j++)mat[i][j]=(ss[j-1]=='#'?0:1);
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            iznad[i][j]=mat[i][j]*(iznad[i-1][j]+1);
            //printf("lol");
        }
    }
    for(ll i=1;i<=n;i++){
        while(!s.empty()){s.pop();}
        s.push(mp(-1,0));
        ll tz=1;
        for(ll j=1;j<=m;j++){
            ll kolko=1;
            while(!s.empty() && s.top().first>=iznad[i][j]){

                kolko+=s.top().second;
                tz-=s.top().first*s.top().second;
                s.pop();
            }
            ll prosli=j-kolko;
            res[i][j]=(kolko*(kolko+1)*iznad[i][j]*(iznad[i][j]+1))/4 + zbirvis[i][prosli]*kolko+res[i][prosli];
            zbirvis[i][j]=zbirvis[i][prosli]+kolko*iznad[i][j]*(iznad[i][j]+1)/2;
            s.push(mp(iznad[i][j],kolko));
            sol+=res[i][j];

        }
    }

    printf("%lld",sol);

    return 0;
}

Compilation message (stderr)

strah.cpp: In function 'int main()':
strah.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
strah.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",ss);
         ~~~~~^~~~~~~~~

• 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