제출 #1263494

#제출 시각아이디문제언어결과실행 시간메모리
1263494LIANafta (COI15_nafta)C++17
11 / 100
1099 ms137028 KiB
#include <bits/stdc++.h> #define ll long long const ll inf = 1e19 + 7; using namespace std; ll r, c; vector<vector<pair<ll, vector<bool>>>> dp; vector<string> grid; ll idx = 0, szcnt = 0; vector<ll> sizes; vector<pair<ll, ll>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; vector<vector<bool>> vis; vector<vector<ll>> color; bool lol(ll i, ll j) { return (i >= 1 && j >= 1 && i <= r && j <= c && !vis[i][j] && grid[i][j - 1] != '.'); } void dfs(ll i, ll j) { color[i][j] = idx; vis[i][j] = 1; if (grid[i][j - 1] != '.') szcnt += (grid[i][j - 1] - '0'); for (auto [x, y] : dir) { if (lol(i + x, j + y)) dfs(i + x, j + y); } } void build_dp() { for (ll i = 1; i <= c; ++i) { for (ll j = 1; j <= c; ++j) { for (ll x = 1; x <= i; ++x) { const auto &prev = dp[x][j - 1]; ll val = prev.first; const auto &vec = prev.second; ll add = 0; vector<bool> visit = vec; for (ll row = 1; row <= r; ++row) { if (grid[row][i - 1] == '.') continue; ll comp = color[row][i]; if (!visit[comp] && grid[row][i - 1] != '.') { visit[comp] = 1; add += sizes[comp]; } } if (val + add > dp[i][j].first) dp[i][j] = {val + add, std::move(visit)}; } } } } int main() { cin >> r >> c; grid.resize(r + 1); vis.resize(r + 1, vector<bool>(c + 1)); color.resize(r + 1, vector<ll>(c + 1)); sizes.resize(r * c + 2); for (ll i = 1; i <= r; ++i) { cin >> grid[i]; } for (ll i = 1; i <= r; ++i) { for (ll j = 1; j <= c; ++j) { if (!vis[i][j] && grid[i][j - 1] != '.') { dfs(i, j); sizes[idx] = szcnt; szcnt = 0; idx++; } } } dp.assign(c + 1, vector<pair<ll, vector<bool>>>(c + 1, {0, vector<bool>(idx + 1)})); build_dp(); vector<ll> ans(c + 1); for (ll j = 1, pref = 0; j <= c; ++j) { ll best = 0; for (ll i = 1; i <= c; ++i) best = max(best, dp[i][j].first); pref = max(pref, best); cout << pref << "\n"; } }

컴파일 시 표준 에러 (stderr) 메시지

nafta.cpp:3:21: warning: overflow in conversion from 'double' to 'long long int' changes value from '1.0e+19' to '9223372036854775807' [-Woverflow]
    3 | const ll inf = 1e19 + 7;
      |                ~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...