Submission #349936

#TimeUsernameProblemLanguageResultExecution timeMemory
349936knightron0Bob (COCI14_bob)C++14
0 / 120
169 ms50228 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define fr first #define sc second #define clr(a) memset(a, 0, sizeof(a)) #define sz(x) x.size() #define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl; #define REP(i, n) for (int i = 0; i < n; i++) #define FOR(i, x, y) for (int i = x; i < y; i++) #define DEC(i, x, y) for (int i = x; i >= y; i--) #define all(v) v.begin(), v.end() #define min3(a, b, c) min(a, min(b, c)) #define max3(a, b, c) max(a, max(b, c)) #define alla(a, n) a, a + n #define gcd(a, b) __gcd(a, b) #define lcm(a, b) (a * b)/gcd(a, b) #define int long long int #define ull unsigned long long #define printarray(arr, n) for(int i= 0;i<n;i++) cout<<arr[i]<<' '; cout<<endl; #define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl; #define initdp(a) memset(a, -1, sizeof(a)); #define endl '\n' #define float long double using namespace std; const int MOD = 1e9 + 7; const int INF = 2e15; const int MAXN = 1e5 + 5; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin>>n>>m; int a[n][m]; for(int i= 0;i<n;i++){ for(int j= 0;j<m;j++){ cin>>a[i][j]; } } int prefh[n][m], prefv[n][m]; clr(prefh); for(int i= 0;i<n;i++){ for(int j= 0;j<m;j++){ if(j==0) { prefh[i][j]= 1; continue; } if(a[i][j] == a[i][j-1]){ prefh[i][j] = prefh[i][j-1]+1; } else { prefh[i][j] = 1; } } } for(int j= 0;j<m;j++){ for(int i= 0;i<n;i++){ if(i==0) { prefv[i][j]= 1; continue; } if(a[i][j] == a[i-1][j]){ prefv[i][j] = prefv[i-1][j]+1; } else { prefv[i][j] = 1; } } } int dp1[n][m]; bool flag[n][m]; clr(flag); // dp1[i][j] = max width ending at (i, j) int dp2[n][m]; // dp2[i][j] = max height ending at (i, j) for(int i= 0;i<n;i++){ for(int j= 0;j<m;j++){ if(i == 0 && j == 0){ dp1[i][j] = 1; dp2[i][j] = 1; continue; } if(i == 0){ dp1[i][j] = prefh[i][j]; } else { if(a[i-1][j-1] == a[i][j]){ dp1[i][j] = min(dp1[i-1][j-1]+1, prefh[i][j]); } else { dp1[i][j] = prefh[i][j]; flag[i][j]= true; } } if(j == 0){ dp2[i][j] = prefv[i][j]; } else { if(a[i-1][j-1] == a[i][j]){ dp2[i][j] = min(dp2[i-1][j-1]+1, prefv[i][j]); } else { dp2[i][j] = prefv[i][j]; flag[i][j]= true; } } } } int ans = 0; for(int i= 0;i<n;i++){ for(int j= 0;j<m;j++){ if(flag[i][j]){ ans += dp1[i][j] + dp2[i][j]-1; } else { ans += dp1[i][j] * dp2[i][j]; } } } cout<<ans<<endl; return 0; }
#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...