oj.uz

답안 #250680

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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