oj.uz

Submission #81539

# Submission time Handle Problem Language Result Execution time Memory
81539 2018-10-25T08:58:07 Z win11905 Strah (COCI18_strah) C++11
110 / 110
 199 ms 20660 KB 
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define pii pair<long, long>
#define x first
#define y second

const int N = 1<<11;

long ans;
int n, m;
char inp[N][N];
int pref[N][N];

long c2(long v) {
    return (v * (v+1)) / 2;
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%s", inp[i]+1);
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) {
        if(inp[i][j] == '.') pref[j][i] = pref[j-1][i] + 1;
    }
    for(int i = 1 ; i <= m; ++i) {
        stack<pii> S;
        long sum = 0;
        for(int j = 1; j <= n; ++j) {
            int cnt = 1;
            while(!S.empty() && S.top().x >= pref[i][j]) sum -= c2(S.top().x) * S.top().y, cnt += S.top().y, S.pop();
            sum += c2(pref[i][j]) * cnt;
            if(pref[i][j]) S.emplace(pref[i][j], cnt);
            ans += sum * (j+1);
        }
        sum = 0, S = stack<pii>();
        for(int j = n; j > 0; --j) {
            int cnt = 1;
            while(!S.empty() && S.top().x >= pref[i][j]) sum -= c2(S.top().x) * S.top().y, cnt += S.top().y, S.pop();
            sum += c2(pref[i][j]) * cnt;
            if(pref[i][j]) S.emplace(pref[i][j], cnt);
            ans -= sum * j;
        }
    }
    printf("%lld\n", ans);
}

Compilation message

strah.cpp: In function 'int main()':
strah.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
strah.cpp:22:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%s", inp[i]+1);
                                 ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3484 KB Output is correct
2 Correct 8 ms 3532 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 12268 KB Output is correct
2 Correct 128 ms 16292 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 18156 KB Output is correct
2 Correct 187 ms 19644 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 19644 KB Output is correct
2 Correct 132 ms 19644 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19644 KB Output is correct
2 Correct 158 ms 19644 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 20588 KB Output is correct
2 Correct 199 ms 20660 KB Output is correct