Submission #257890

#	Time	Username	Problem	Language	Result	Execution time	Memory
257890		leductoan	Bob (COCI14_bob)	C++14	120 / 120	153 ms	25868 KiB

bob

#include<bits/stdc++.h>

using namespace std;

#define task "bhouse"
#define fi first
#define se second

template <typename T>
inline void read(T& x)
{
   bool Neg = false;
   char c;
   for (c = getchar(); c < '0' | c > '9'; c = getchar())
       if (c == '-') Neg = !Neg;
   x = c - '0';
   for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
       x = x * 10 + c - '0';
   if (Neg) x = -x;
}

template <typename T>
inline void write(T x)
{
   if (x < 0)
   {
       putchar('-'); x = -x;
   }
   T p = 1;
   for (T temp = x / 10; temp > 0; temp /= 10) p *= 10;
   for (; p > 0; x %= p, p /= 10) putchar(x / p + '0');
}

typedef long double ld;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;

const int mxn=1005;
int n,m,a[mxn][mxn],p[mxn][mxn],h[mxn];
ll ans=0,f[mxn][mxn];
void solve()
{
    read(n); read(m);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
//            cin>>a[i][j];
            read(a[i][j]);
            if(a[i][j]!=a[i][j-1]) p[i][j]=j;
            else p[i][j]=p[i][j-1];
        }
    }

    for(int i=1;i<=n;++i)
    {
        deque<int> q;
        for(int j=1;j<=m;++j)
        {
            if(a[i][j]==a[i-1][j]) ++h[j];
            else h[j]=1;
            while(!q.empty()&&a[i][j]!=a[i][q.front()]) q.pop_front();
            while(!q.empty()&&h[q.back()]>=h[j]) q.pop_back();
            int pos=0;
            if(!q.empty()) pos=q.back();
            else pos=p[i][j]-1;
//            if(i==3&&j==3) cout<<h[j]<<' '<<pos<<'\n';
            if(a[i][j]==a[i][pos]) f[i][j]=f[i][pos]+(j-pos)*h[j];
            else f[i][j]=(j-pos)*h[j];
            ans+=f[i][j];
            q.push_back(j);
        }
    }
//    cout<<f[3][3]<<'\n';
    cout<<ans;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    solve();
}

Compilation message (stderr)

bob.cpp: In instantiation of 'void read(T&) [with T = int]':
bob.cpp:44:11:   required from here
bob.cpp:14:26: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
    for (c = getchar(); c < '0' | c > '9'; c = getchar())
                        ~~^~~~~
bob.cpp: In function 'int main()':
bob.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(task".inp","r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bob.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(task".out","w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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