Submission #1209317

#TimeUsernameProblemLanguageResultExecution timeMemory
1209317SpyrosAlivNafta (COI15_nafta)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define int long long vector<pair<int, int>> delta = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; const int MN = 2005; int grid[MN][MN], c[MN][MN], dp[MN][MN], n, m, lb, rb, s; bool vis[MN][MN]; vector<tuple<int, int, int>> ranges; bool inside(int i, int j) { return i >= 1 && i <= n && j >= 1 && j <= m; } void flood(int i, int j) { s += grid[i][j]; vis[i][j] = true; lb = min(lb, j); rb = max(rb, j); for (auto [pi, pj]: delta) { int ni = i + pi; int nj = j + pj; if (inside(ni, nj) && grid[ni][nj] != -1 && !vis[ni][nj]) { flood(ni, nj); } } } void dnc(int l, int r, int optl, int optr, int k) { if (l > r) return; int mid = (l + r) / 2; int best = -1, opt = -1; for (int i = optl; i <= min(optr, mid); i++) { int ans = c[i][mid]; if (i > 1) ans += dp[i-1][k-1]; if (ans > best) { best = ans; opt = i; } } dp[mid][k] = best; dnc(l, mid - 1, optl, opt, k); dnc(mid+1, r, opt, optr, k); } void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { char c; cin >> c; if (c == '.') { grid[i][j] = -1; } else grid[i][j] = (c - '0'); } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (vis[i][j] || grid[i][j] == -1) continue; s = 0; lb = m; rb = 0; flood(i, j); ranges.push_back({lb, rb, s}); } } swap(n, m); for (auto [l, r, s]: ranges) { for (int i = 1; i <= n; i++) { if (i > l || r < i) break; c[i][l] += s; c[i][r+1] -= s; } } for (int i = 1; i <= n; i++) { for (int j = i+1; j <= n; j++) { c[i][j] += c[i][j-1]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i][1] = max(dp[i][1], c[1][j]); } } for (int k = 2; k <= n; k++) { dnc(1, n, 1, n, k); } for (int i = 1; i <= n; i++) { cout << dp[n][i] << "\n"; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; while (t--) solve(); return 0; }

Compilation message (stderr)

nafta.cpp: In function 'void solve()':
nafta.cpp:64:13: error: reference to 'ranges' is ambiguous
   64 |             ranges.push_back({lb, rb, s});
      |             ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from nafta.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
nafta.cpp:9:30: note:                 'std::vector<std::tuple<long long int, long long int, long long int> > ranges'
    9 | vector<tuple<int, int, int>> ranges;
      |                              ^~~~~~
nafta.cpp:68:26: error: reference to 'ranges' is ambiguous
   68 |     for (auto [l, r, s]: ranges) {
      |                          ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from nafta.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
nafta.cpp:9:30: note:                 'std::vector<std::tuple<long long int, long long int, long long int> > ranges'
    9 | vector<tuple<int, int, int>> ranges;
      |                              ^~~~~~