oj.uz

Submission #337127

# Submission time Handle Problem Language Result Execution time Memory
337127 2020-12-18T14:38:24 Z BeanZ Strah (COCI18_strah) C++14
110 / 110
 230 ms 8248 KB 
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 2e3 + 5;
long long mod = 1e9 + 7;
const int lim = 2e5;
const int lg = 18;
const int base = 311;
const long double eps = 1e-6;
char a[N][N];
ll cnt[N], l[N], r[N];
ll sum(ll u){
    return u * (u + 1) / 2;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n, m;
    cin >> n >> m;
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
            if (a[i][j] == '.') cnt[j]++;
            else cnt[j] = 0;
        }
        vector<ll> st;
        for (int j = 1; j <= m; j++){
            while (st.size()){
                if (cnt[st.back()] >= cnt[j]) st.pop_back();
                else break;
            }
            if (st.size()) l[j] = st.back() + 1;
            else l[j] = 1;
            st.push_back(j);
        }
        st.clear();
        for (int j = m; j >= 1; j--){
            while (st.size()){
                if (cnt[st.back()] > cnt[j]) st.pop_back();
                else break;
            }
            if (st.size()) r[j] = st.back() - 1;
            else r[j] = m;
            st.push_back(j);
        }
        for (int j = 1; j <= m; j++){
            ll lf = j - l[j] + 1;
            ll rt = r[j] - j + 1;
            ll tot = lf * sum(rt) + rt * sum(lf) - lf * rt;
            ans = ans + tot * sum(cnt[j]);
        }
    }
    cout << ans;
}
/*
3 3
...
...
...
Ans:

Out:
*/

Compilation message

strah.cpp: In function 'int main()':
strah.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   21 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
strah.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   22 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1004 KB Output is correct
2 Correct 6 ms 1004 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Correct 7 ms 980 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3052 KB Output is correct
2 Correct 131 ms 5740 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 5356 KB Output is correct
2 Correct 197 ms 7788 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3564 KB Output is correct
2 Correct 157 ms 6112 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4192 KB Output is correct
2 Correct 146 ms 6984 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 8248 KB Output is correct
2 Correct 230 ms 4332 KB Output is correct