Submission #639575

#	Time	Username	Problem	Language	Result	Execution time	Memory
639575		CaoHuuKhuongDuy	Bob (COCI14_bob)	C++14	120 / 120	136 ms	25844 KiB

bob

#include <bits/stdc++.h>
using namespace std;
#define int long long 
typedef pair <int,int> ii;
const int N = 1e3 + 9;
const int oo = 1e10;
int n,m,a[N][N],high[N][N],l[N],r[N],res = 0;
void solve(int a[],int h[],bool kt)
{
    stack <int> s;
    h[0] = -oo;
    s.push(0);
    for (int i = 1;i <= m;i++)
      {
        while (h[i] < h[s.top()] && a[i] == a[s.top()]) s.pop();
        l[i] = s.top() + 1;
        s.push(i);
      }
    while (s.size()) s.pop();
    s.push(m + 1);
    h[m + 1] = -oo;
    for (int i = m;i >= 1;i--)
      {
        while (h[i] <= h[s.top()] && a[i] == a[s.top()]) s.pop();
        r[i] = s.top() - 1;
        s.push(i);
      }
    for (int i = 1;i <= m;i++)
      res += (i - l[i] + 1) * (r[i] - i + 1) * h[i] ;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.inp","r",stdin);
    // freopen("check1.out","w",stdout);
    cin>>n>>m;
    for (int i = 1;i <= n;i++)
      for (int j = 1;j <= m;j++)
        cin>>a[i][j];
    for (int i = 1;i <= n;i++)
      for (int j = 1;j <= m;j++)
        if (a[i][j] != a[i-1][j]) high[i][j] = 1;
        else high[i][j] = high[i-1][j] + 1;
    for (int i = 1;i <= n;i++)
      solve(a[i],high[i],(i == 2));
    cout<<res;
    return 0;
}

• 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