oj.uz

답안 #80164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
80164 2018-10-19T10:25:35 Z FutymyClone Bob (COCI14_bob) C++14
120 / 120
 174 ms 64388 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n, m, a[N][N], h[N][N];
long long ans = 0;

int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
    for (int i = 1; i <= m; i++) h[1][i] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == a[i - 1][j]) h[i][j] = h[i - 1][j] + 1;
            else h[i][j] = 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        vector <pair <int, int> > vec; vec.push_back({0, 0});
        int pos = 0;
        for (int j = 1; j <= m; j++) {
            if (j - 1 && a[i][j] != a[i][j - 1]) {
                pos++;
                while (!vec.empty() && vec.back().first >= 0) vec.pop_back();
                vec.push_back({0, pos});
                long long res = 0;

                for (int k = 1; k < vec.size(); k++) res += 1LL * (vec[k].first - vec[k - 1].first) * (pos - vec[k - 1].second);
            }

            pos++;
            while (!vec.empty() && vec.back().first >= h[i][j]) vec.pop_back();
            vec.push_back({h[i][j], pos});
            long long res = 0;

            for (int k = 1; k < vec.size(); k++) res += 1LL * (vec[k].first - vec[k - 1].first) * (pos - vec[k - 1].second);
            ans += res;
        }
    }

    printf("%lld", ans);
    return 0;
}

Compilation message

bob.cpp: In function 'int main()':
bob.cpp:31:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int k = 1; k < vec.size(); k++) res += 1LL * (vec[k].first - vec[k - 1].first) * (pos - vec[k - 1].second);
                                 ~~^~~~~~~~~~~~
bob.cpp:39:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = 1; k < vec.size(); k++) res += 1LL * (vec[k].first - vec[k - 1].first) * (pos - vec[k - 1].second);
                             ~~^~~~~~~~~~~~
bob.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
bob.cpp:12:68: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
                                                               ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 888 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1028 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 5268 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 6576 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 7908 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 9120 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 19616 KB Output is correct
2 Correct 119 ms 21656 KB Output is correct
3 Correct 113 ms 23520 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 33284 KB Output is correct
2 Correct 115 ms 35332 KB Output is correct
3 Correct 112 ms 37228 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 46924 KB Output is correct
2 Correct 121 ms 48968 KB Output is correct
3 Correct 118 ms 50804 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 60540 KB Output is correct
2 Correct 113 ms 62492 KB Output is correct
3 Correct 111 ms 64388 KB Output is correct