Submission #1264310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264310		_rain_	Nafta (COI15_nafta)	C++20	100 / 100	295 ms	98056 KiB

nafta

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask , x) (((mask)>>(x))&(1))
#define sz(x) (int)(x).size()

template<class T1 , class T2>
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>	
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}
	
const int N = (int) 2e3;
const int dx[] = {0 , 0 , 1 , -1};
const int dy[] = {1 , -1 , 0 , 0};
	int a[N + 2][N + 2];
	int numrow , numcol;
	
	LL cost[N + 2][N + 2] = {};
	bool vis[N + 2][N + 2] = {};
	int mx[N + 2] = {};
	LL sum = 0;
	
	void bfs(int u , int v , int root){
		queue<pair<int,int>>q;
		q.push({u , v});
		vis[u][v] = true;
		while (q.size()){
			int u = q.front().first;
			int v = q.front().second;
			sum += a[u][v];
			q.pop();
			maximize(mx[root] , v);
			for(int i = 0; i < 4; ++i){
				int nxt_u = u + dx[i];
				int nxt_v = v + dy[i];
				if (nxt_u > 0 && nxt_u <= numrow && nxt_v > 0 && nxt_v <= numcol && vis[nxt_u][nxt_v]==false){
					vis[nxt_u][nxt_v] = true;
					q.push({nxt_u , nxt_v});
				}
			}
		}
		return;
	}

	LL dp[N + 2][N + 2] = {};
	LL w[N + 2][N + 2] = {};
	
	int opt[N + 2][N + 2] = {};
	
	void solve(int layer , int l , int r , int best_l , int best_r){
		if (l > r) return;
		int mid = (l + r) / 2;
	
		dp[mid][layer] = -1;
		opt[mid][layer] = -1;
		
		for(int i = max(mid  , best_l); i <= best_r; ++i){
			if (maximize(dp[mid][layer] , dp[i][layer - 1] + w[mid][i])){
				opt[mid][layer] = i;
			}
		}
		
		assert(opt[mid][layer] != -1);
		solve(layer , l , mid - 1 , best_l , opt[mid][layer]);
		solve(layer , mid + 1 , r , opt[mid][layer] , best_r);
		return;
	}
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> numrow >> numcol;
		for(int i = 1; i <= numrow; ++i){
			string s; cin >> s;
			s = '#' + s;
			for(int j = 1; j <= numcol; ++j) {
				if (s[j] >= '0' && s[j] <= '9') a[i][j] = s[j] - '0'; 
				else {
					a[i][j] = 0;
					vis[i][j] = true;
				}
			}
		}
		
		for(int j = 1; j <= numcol; ++j){
			for(int i = 1; i <= numrow; ++i){
				if (vis[i][j] == 0){
					mx[j] = 0;
					sum = 0;
					bfs(i , j , j);
					for(int t = j; t <= mx[j]; ++t) cost[j][t] += sum;
				}
			}
		}
		
		for(int i = numcol; i >= 0; --i){
			for(int j = i + 1; j <= numcol; ++j) w[i][j] = w[i + 1][j] + cost[i + 1][j];
		}

		for(int i = 1; i <= numcol; ++i){
			solve(i ,  0 , numcol , 0 , numcol);
		}
	
		for(int i = 1; i <= numcol; ++i){
			LL ans = 0;
			for(int j = 0; j <= numcol; ++j) {
				maximize(ans , dp[j][i]);
			}
			cout << ans << '\n';
		}
	return 0;
}

Compilation message (stderr)

nafta.cpp: In function 'int main()':
nafta.cpp:90:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:91:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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