Submission #80164

#	Time	Username	Problem	Language	Result	Execution time	Memory
80164		FutymyClone	Bob (COCI14_bob)	C++14	120 / 120	174 ms	64388 KiB

bob

#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 (stderr)

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12