Submission #960545

#TimeUsernameProblemLanguageResultExecution timeMemory
960545NiosakaruNafta (COI15_nafta)C++17
34 / 100
1029 ms138748 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i,l,r) for (int i = l ; i <= r ; i ++) #define N 2020 const int mod = 1e9 + 7 , base = 311; int n , m , s , r , w[N][N] , e[N][N] , a[N][N] , vs[N][N] , rs[N] , dp[N][N] , dx[] = {0,0,-1,1} , dy[] = {1,-1,0,0}; int bfs(int u,int v){ r = max(r,v); vs[u][v] = 1; int sum = a[u][v]; rep(i,0,3){ int x = u + dx[i] , y = v + dy[i]; if (1 > x || 1 > y || n < x || m < y || vs[x][y] || a[x][y] == -1) continue; sum += bfs(x,y); } return sum; } signed main(){ cin.tie(NULL)->sync_with_stdio(NULL); cin >> n >> m; memset(a , -1 , sizeof a); rep(i,1,n) rep(j,1,m) { char c; cin >> c; if (c == '.') continue; a[i][j] = c - '0'; } rep(j,1,m) rep(i,1,n) { if (vs[i][j] || a[i][j] == -1) continue; r = j , s = bfs(i,j); w[j][r] += s; } for (int i = m ; i ; i --){ s = 0; for (int j = m ; j >= i ; j --){ s += w[i][j]; e[i][j] = e[i + 1][j] + s; } } rep(k,1,m){ rep(i,1,m) rep(j,0,i-1){ dp[i][k] = max(dp[i][k] , dp[j][k - 1] + e[j + 1][i]); rs[k] = max(rs[k] , dp[i][k]); } } rep(i,1,m) cout << rs[i] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...