Submission #950301

#	Time	Username	Problem	Language	Result	Execution time	Memory
950301		hqminhuwu	Nafta (COI15_nafta)	C++14	100 / 100	389 ms	137964 KiB

nafta

#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 * r)
		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){
      |  ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66