oj.uz

답안 #257890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257890 2020-08-05T02:21:13 Z leductoan Bob (COCI14_bob) C++14
120 / 120
 153 ms 25868 KB 
#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

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.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 22776 KB Output is correct
2 Correct 39 ms 18040 KB Output is correct
3 Correct 39 ms 18044 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 25868 KB Output is correct
2 Correct 46 ms 18040 KB Output is correct
3 Correct 37 ms 17964 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 25688 KB Output is correct
2 Correct 45 ms 18040 KB Output is correct
3 Correct 37 ms 18040 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 25848 KB Output is correct
2 Correct 50 ms 17984 KB Output is correct
3 Correct 37 ms 18040 KB Output is correct