Submission #316340

#TimeUsernameProblemLanguageResultExecution timeMemory
316340FlashGamezzzBob (COCI14_bob)C++17
120 / 120
224 ms18680 KiB
#include <iostream> #include <cstdlib> #include <cstdio> #include <fstream> #include <algorithm> #include <string> #include <map> #include <vector> #include <utility> using namespace std; int n, m, grid[1001][1001] = {}, nl[1001][1001] = {}, nu[1001][1001] = {}, dp[1001][1001] = {}; map<int, int> mps[1001]; int main() { ios_base::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ cin >> grid[i][j]; nl[i][j] = 1; nu[i][j] = 1; if (grid[i][j] == grid[i][j-1]){ nl[i][j] += nl[i][j-1]; } if (grid[i][j] == grid[i-1][j]){ nu[i][j] += nu[i-1][j]; } } } for (int r = 1; r <= n; r++){ dp[r][1] = nu[r][1]; mps[r][dp[r][1]] = 1; } for (int c = 2; c <= m; c++){ for (int r = 1; r <= n; r++){ if (grid[r][c] != grid[r][c-1]){ mps[r].clear(); } dp[r][c] = nu[r][c] * nl[r][c]; if (mps[r].size() > 0){ map<int, int>::iterator lb = mps[r].lower_bound(nu[r][c]); if (lb != mps[r].begin()){ lb--; dp[r][c] -= nl[r][lb->second] * nu[r][c]; dp[r][c] += dp[r][lb->second]; } } mps[r][nu[r][c]] = c; mps[r].erase(mps[r].upper_bound(nu[r][c]), mps[r].end()); } } long ans = 0; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ ans += dp[i][j]; } } cout << ans; }
#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...