Submission #250680

#	Time	Username	Problem	Language	Result	Execution time	Memory
250680		kingfran1907	Bob (COCI14_bob)	C++14	120 / 120	179 ms	10232 KiB

bob

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

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 / 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