oj.uz

Submission #167666

# Submission time Handle Problem Language Result Execution time Memory
167666 2019-12-09T10:51:43 Z rzbt Strah (COCI18_strah) C++14
110 / 110
 189 ms 129960 KB 
#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

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.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 47448 KB Output is correct
2 Correct 133 ms 97756 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 86136 KB Output is correct
2 Correct 180 ms 125560 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 55400 KB Output is correct
2 Correct 149 ms 103936 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 38136 KB Output is correct
2 Correct 165 ms 121224 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 129876 KB Output is correct
2 Correct 189 ms 129960 KB Output is correct