Submission #950289

#TimeUsernameProblemLanguageResultExecution timeMemory
950289hqminhuwuNafta (COI15_nafta)C++14
0 / 100
4 ms21336 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll,ll> pll; typedef pair <int,int> pii; typedef pair <int,pii> piii; #define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a) #define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);) #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a) #define st first #define nd second #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define mask(i) (1LL << (i)) #define bit(x, i) (((x) >> (i)) & 1) #define bp __builtin_popcountll #define file "test" const int N = 2e3 + 5; const ll oo = 1e9; const ll mod = 1e9 + 7; const int d[5] = {0, 1, 0, -1, 0}; const int M = 4e6 + 4; int r, c, cnt, vis[N][N], sum[M], fl[M], fr[M], dc[N], col[N], f[M], cost[N][N], ic[N]; int dp[N][N], now; string a[N]; bool maxi (int &x, int y){ if (y > x) return x = y, 1; return 0; } bool ok (int i, int j){ return i > 0 && j > 0 && i <= r && j <= c && a[i][j] != '.'; } void dfs (int i, int j){ vis[i][j] = cnt; fr[cnt] = max (fr[cnt], j); fl[cnt] = min (fl[cnt], j); sum[cnt] += a[i][j] - '0'; forf (k, 0, 5){ int ni = i + d[k], nj = j + d[k + 1]; if (ok(ni, nj) && !vis[ni][nj]) dfs(ni, nj); } } void calc (int l, int r, int opl, int opr){ if (l > r) return; // if (now == 2){ // cout << l << " " << r << " " << opl << " " << opr << "\n"; // } int mid = (l + r) >> 1; int op = -1; forr (i, opl, min(mid, opr)){ if (maxi(dp[mid][now], dp[i - 1][now - 1] + cost[i][mid])) op = i; } //cout << dp[mid][now] << " " << op << '\n'; calc(l, mid - 1, opl, op); calc (mid + 1, r, op, opr); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef hqm freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); #endif cin >> r >> c; forr (i, 1, r){ cin >> a[i]; a[i] = '.' + a[i]; } forr (i, 1, c) fl[i] = c + 1; memset (dp, -63, sizeof dp); forr (i, 0, c) dp[i][0] = 0, dp[0][i] = 0; forr (i, 1, r) forr (j, 1, c) if (!vis[i][j] && a[i][j] != '.'){ ++cnt; dfs(i, j); // dc[fl[cnt]] += sum[cnt]; // ic[fr[cnt]] += sum[cnt]; // cout << sum[cnt] << " " << fl[cnt] << " " << fr[cnt] << "\n"; } forr (j, 1, c){ col[j] = 0; forr (i, 1, r) f[vis[i][j]] = 1; forr (i, 1, r){ ic[fl[vis[i][j]]] += sum[vis[i][j]] * f[vis[i][j]]; f[vis[i][j]] = 0; } ford (i, j, 1) cost[i][j] = cost[i + 1][j] + ic[i], ic[i] = 0; // forr (i, 1, j) // cout << cost[i][j] << " "; // cout << "\n"; } forr (i, 1, c) dp[i][1] = cost[1][i]; forr (t, 2, c) forr (i, 1, c){ forr (j, 1, i) dp[i][t] = max (dp[i][t], dp[j - 1][t - 1] + cost[j][i]); } // forr (i, 2, c){ // now = i; // calc(1, c, 1, c); // } forr (i, 1, c){ int ans = 0; forr (j, 1, c) maxi(ans, dp[j][i]); cout << ans << "\n"; } return 0; } /* */

Compilation message (stderr)

nafta.cpp: In function 'void dfs(int, int)':
nafta.cpp:49:38: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
   49 |   int ni = i + d[k], nj = j + d[k + 1];
      |                               ~~~~~~~^
nafta.cpp:11:46: note: within this loop
   11 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
      |                                              ^
nafta.cpp:48:2: note: in expansion of macro 'forf'
   48 |  forf (k, 0, 5){
      |  ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...