oj.uz

Submission #679723

# Submission time Handle Problem Language Result Execution time Memory
679723 2023-01-09T02:44:36 Z vjudge1 Bob (COCI14_bob) C++14
120 / 120
 115 ms 13948 KB 
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int m, n;
ll res = 0;

void solve()
{
    cin >> n >> m;
    int a[n + 1][m + 1], h[m + 1]{}, l[m + 1]{};
    ll dp[m + 1]{};
    memset(a, 0, sizeof a);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            h[j]++;
            if(a[i][j] != a[i - 1][j]) h[j] = 1;
        }
        stack<int> s;
        for(int j = 1; j <= m; j++)
        {
            while(s.size() && a[i][j] == a[i][s.top()] && h[j] <= h[s.top()]) s.pop();
            if(s.empty()) l[j] = 0;
            else l[j] = s.top();
            s.push(j);
        }
        for(int j = 1; j <= m; j++)
        {
            dp[j] = 1LL * (j - l[j]) * h[j];
            if(a[i][j] == a[i][l[j]]) dp[j] += dp[l[j]];
            res += dp[j];
        }
    }
    cout << res;   
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 10892 KB Output is correct
2 Correct 54 ms 6140 KB Output is correct
3 Correct 56 ms 6192 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 13948 KB Output is correct
2 Correct 56 ms 6144 KB Output is correct
3 Correct 56 ms 6136 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 13712 KB Output is correct
2 Correct 52 ms 6148 KB Output is correct
3 Correct 51 ms 6092 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 13836 KB Output is correct
2 Correct 55 ms 6152 KB Output is correct
3 Correct 52 ms 6132 KB Output is correct