Submission #475660

#	Time	Username	Problem	Language	Result	Execution time	Memory
475660		cpp219	Strah (COCI18_strah)	C++14	110 / 110	132 ms	4204 KiB

strah

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
typedef pair<ld,ll> LD;
const ll N = 2e3 + 9;
const ll mod = 1e9 + 7;
const ll base = 31;

ll n,m,ans,h[N],lf[N],rg[N];
string s;

ll cal(ll x){
    return x * (x + 1)/2;
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>m;
    for (ll i = 1;i <= n;i++){
        cin>>s; s = " " + s; vector<ll> st;
        for (ll j = 1;j <= m;j++){
            if (s[j] == '.') h[j]++;
            else h[j] = 0;
        }
        for (ll j = 1;j <= m;j++){
            while(!st.empty() && h[st.back()] >= h[j]) st.pop_back();
            if (!st.empty()) lf[j] = st.back();
            else lf[j] = 0; st.push_back(j);
        }
        st.clear();
        for (ll j = m;j > 0;j--){
            while(!st.empty() && h[st.back()] > h[j]) st.pop_back();
            if (!st.empty()) rg[j] = st.back();
            else rg[j] = m + 1; st.push_back(j);
        }
        for (ll j = 1;j <= m;j++){
            ll r = rg[j] - j,l = j - lf[j];
            ll tmp = r * cal(l) + l * cal(r) - l*r;
            ans += tmp * cal(h[j]);
            //cout<<lf[j]<<" "<<rg[j]<<"\n";
        }
    }
    cout<<ans;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message (stderr)

strah.cpp: In function 'int main()':
strah.cpp:38:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   38 |             else lf[j] = 0; st.push_back(j);
      |             ^~~~
strah.cpp:38:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   38 |             else lf[j] = 0; st.push_back(j);
      |                             ^~
strah.cpp:44:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   44 |             else rg[j] = m + 1; st.push_back(j);
      |             ^~~~
strah.cpp:44:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   44 |             else rg[j] = m + 1; st.push_back(j);
      |                                 ^~
strah.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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