Submission #80164

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
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

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	888 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1028 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	5268 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	6576 KB	Output is correct

Subtask #5
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	7908 KB	Output is correct

Subtask #6
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	9120 KB	Output is correct

Subtask #7
12.0 / 12.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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