Submission #257890

#TimeUsernameProblemLanguageResultExecution timeMemory
257890leductoanBob (COCI14_bob)C++14
120 / 120
153 ms25868 KiB
#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);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...