Submission #1222041

#TimeUsernameProblemLanguageResultExecution timeMemory
1222041395333emNafta (COI15_nafta)C++20
34 / 100
1097 ms46684 KiB
#include <bits/stdc++.h> #define int long long #define emb emplace_back #define pii pair <int, int> using namespace std; const int mod = 1e9 + 7; const int inf = 1e18; const int N = 2e3 + 5; int n, m, dp[N][N], cal[N][N]; // dp[i][j] = max number of oil after picking i columns including column j char a[N][N]; bool visited[N][N]; map <int, vector <pii>> mp; struct fenwick { int fw[N]; void update(int idx, int val){ if (idx >= N) return; fw[idx] += val; update(idx + (idx & -idx), val); } int query(int idx){ if (idx <= 0) return 0; return fw[idx] + query(idx - (idx & -idx)); } } f; void bfs(int r, int c){ queue <pii> q; q.emplace(r, c); int sum = 0; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; visited[r][c] = true; int mn = inf, mx = 0; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); sum += a[x][y] - '0'; mn = min(mn, y); mx = max(mx, y); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 1 || nx > n || ny < 1 || ny > m || a[nx][ny] == '.' || visited[nx][ny]) continue; visited[nx][ny] = true; q.emplace(nx, ny); } } mp[mx].emb(mn, sum); // cout << mn << " -> " << mx << ": " << sum << "\n"; } signed main(){ cin.tie(NULL)->sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i][j] == '.' || visited[i][j]) continue; bfs(i, j); } } for (int r = m; r >= 1; r--) { for (auto [l, sum] : mp[r]) f.update(l, sum); for (int l = r; l >= 1; l--) cal[l][r] = f.query(l); } // cout << "----------------------------\n"; // for (int i = 1; i <= m; i++) { // for (int j = i + 1; j <= m; j++) { // cout << i << " -> " << j << ": " << cal[i][j] << "\n"; // } // } for (int i = 1; i <= m; i++) dp[1][i] = cal[i][i]; for (int k = 2; k <= m; k++) { for (int i = 1; i <= m; i++) { for (int j = 1; j < i; j++) { dp[k][i] = max(dp[k][i], dp[k - 1][j] + cal[i][i] - cal[j][i]); } // cout << dp[k][i] << "\n"; } } for (int i = 1; i <= m; i++) cout << *max_element(dp[i] + 1, dp[i] + 1 + m) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...