Submission #250680

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
250680	2020-07-18T17:09:29 Z	kingfran1907	Bob (COCI14_bob)	C++14	120 / 120	179 ms	10232 KB

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1010;

int n, m;
int niz[maxn][maxn];
int pref[maxn][maxn];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &niz[i][j]);

    long long sol = 0;
    for (int i = 0; i < n; i++) {
        vector<int> his;
        for (int j = 0; j < m; j++) {
            if (i == 0) pref[i][j] = 1;
            else pref[i][j] = (niz[i - 1][j] == niz[i][j] ? pref[i - 1][j] + 1 : 1);
            his.push_back(pref[i][j]);
        }

        stack< pair<int, pair<int, long long> > > s;
        //printf("histogram: "); for (int i = 0; i < m; i++) printf("%d ", his[i]); printf("\n");

        for (int j = 0; j < m; j++) {
            if (j > 0 && niz[i][j] != niz[i][j - 1]) {while (!s.empty()) s.pop();}

            int cnt = 1;
            while (!s.empty() && his[s.top().first] >= his[j]) {
                cnt += s.top().second.first;
                s.pop();
            }
            //printf("debug: %d %d\n", his[j], cnt);

            long long tren = (long long)cnt * his[j];
            if (!s.empty()) tren += s.top().second.second;
            sol += tren;
            s.push(make_pair(j, make_pair(cnt, tren)));
        }
    }
    printf("%lld", sol);
    return 0;
}

Compilation message

bob.cpp: In function 'int main()':
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:14:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &niz[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	4216 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	4216 KB	Output is correct

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	155 ms	8248 KB	Output is correct
2	Correct	110 ms	10232 KB	Output is correct
3	Correct	114 ms	10232 KB	Output is correct

Subtask #8
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	8204 KB	Output is correct
2	Correct	115 ms	10232 KB	Output is correct
3	Correct	118 ms	10232 KB	Output is correct

Subtask #9
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	167 ms	8312 KB	Output is correct
2	Correct	108 ms	10232 KB	Output is correct
3	Correct	111 ms	10232 KB	Output is correct

Subtask #10
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	170 ms	8184 KB	Output is correct
2	Correct	111 ms	10232 KB	Output is correct
3	Correct	110 ms	10104 KB	Output is correct