oj.uz

Submission #950301

# Submission time Handle Problem Language Result Execution time Memory
950301 2024-03-20T07:51:16 Z hqminhuwu Nafta (COI15_nafta) C++14
100 / 100
 389 ms 137964 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21340 KB Output is correct
2 Correct 4 ms 21340 KB Output is correct
3 Correct 3 ms 21292 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 21260 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21340 KB Output is correct
2 Correct 4 ms 21340 KB Output is correct
3 Correct 3 ms 21292 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 21260 KB Output is correct
7 Correct 7 ms 23644 KB Output is correct
8 Correct 8 ms 23644 KB Output is correct
9 Correct 11 ms 25176 KB Output is correct
10 Correct 6 ms 22876 KB Output is correct
11 Correct 7 ms 22876 KB Output is correct
12 Correct 6 ms 23024 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21340 KB Output is correct
2 Correct 4 ms 21340 KB Output is correct
3 Correct 3 ms 21292 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 21260 KB Output is correct
7 Correct 7 ms 23644 KB Output is correct
8 Correct 8 ms 23644 KB Output is correct
9 Correct 11 ms 25176 KB Output is correct
10 Correct 6 ms 22876 KB Output is correct
11 Correct 7 ms 22876 KB Output is correct
12 Correct 6 ms 23024 KB Output is correct
13 Correct 335 ms 78164 KB Output is correct
14 Correct 347 ms 74792 KB Output is correct
15 Correct 389 ms 137964 KB Output is correct
16 Correct 284 ms 70884 KB Output is correct
17 Correct 293 ms 69916 KB Output is correct
18 Correct 285 ms 70108 KB Output is correct