oj.uz

Submission #1051032

# Submission time Handle Problem Language Result Execution time Memory
1051032 2024-08-09T18:34:58 Z PieArmy Nafta (COI15_nafta) C++17
100 / 100
 183 ms 85936 KB 
#include<bits/stdc++.h>
typedef long long ll;
#define fr first
#define sc second
#define pb push_back
#define int ll
#define endl '\n'
using namespace std;
struct Fen{
	int n;
	vector<int>tree;
	Fen(int N){
		n=N;
		tree.resize(n+1,0);
	}
	void update(int tar,int x){
		while(tar<=n){
			tree[tar]+=x;
			tar+=(tar&-tar);
		}
	}
	int query(int tar){
		int res=0;
		while(tar){
			res+=tree[tar];
			tar-=(tar&-tar);
		}
		return res;
	}
};

int n,m,k;
char grid[2002][2002];
int w[2002][2002];
vector<pair<pair<int,int>,int>>ara;
int dp[2002][2002];

void f(int left,int right,int l,int r,int t){
	if(left>right)return;
	int mid=((left+right+1)>>1);
	pair<int,int>res={-1,-1};
	for(int i=l;i<=min(mid,r);i++){
		int cos=dp[t-1][i]+w[i][mid];
		res=max(res,{cos,i});
	}
	dp[t][mid]=res.fr;
	f(left,mid-1,l,res.sc,t);
	f(mid+1,right,res.sc,r,t);
}

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);

	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>grid[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(grid[i][j]=='.')continue;
			int l=m+1,r=0,sum=0;
			queue<pair<int,int>>q;q.push({i,j});
			sum=grid[i][j]-'0';
			grid[i][j]='.';
			while(q.size()){
				pair<int,int>pos=q.front();
				q.pop();
				l=min(l,pos.sc);
				r=max(r,pos.sc);
				if(pos.fr!=1&&grid[pos.fr-1][pos.sc]!='.'){
					sum+=grid[pos.fr-1][pos.sc]-'0';
					grid[pos.fr-1][pos.sc]='.';
					q.push({pos.fr-1,pos.sc});
				}
				if(pos.sc!=1&&grid[pos.fr][pos.sc-1]!='.'){
					sum+=grid[pos.fr][pos.sc-1]-'0';
					grid[pos.fr][pos.sc-1]='.';
					q.push({pos.fr,pos.sc-1});
				}
				if(pos.fr!=n&&grid[pos.fr+1][pos.sc]!='.'){
					sum+=grid[pos.fr+1][pos.sc]-'0';
					grid[pos.fr+1][pos.sc]='.';
					q.push({pos.fr+1,pos.sc});
				}
				if(pos.sc!=m&&grid[pos.fr][pos.sc+1]!='.'){
					sum+=grid[pos.fr][pos.sc+1]-'0';
					grid[pos.fr][pos.sc+1]='.';
					q.push({pos.fr,pos.sc+1});
				}
			}
			ara.pb({{l,r},sum});
		}
	}
	k=ara.size();
	Fen fen(m);
	{
		vector<pair<int,int>>up[m+1];
		for(pair<pair<int,int>,int>p:ara){
			up[p.fr.fr].pb({p.fr.sc,p.sc});
		}
		for(int i=1;i<=m;i++){
			for(pair<int,int>x:up[i]){
				fen.update(x.fr,x.sc);
			}
			up[i].clear();
			int fir=fen.query(m);
			int toplam=fir-fen.query(i-1);
			for(int j=1;j<=m+1;j++){
				w[i][j]+=toplam;
			}
			for(int j=i+1;j<=m;j++){
				w[j][i]-=fir-fen.query(j-1);
			}
		}
		for(pair<pair<int,int>,int>p:ara){
			up[p.fr.sc].pb({p.fr.fr,p.sc});
		}
		fen.tree.resize(0);fen.tree.resize(m+1,0);
		for(int i=m;i>=1;i--){
			for(pair<int,int>x:up[i]){
				fen.update(x.fr,x.sc);
			}
			up[i].clear();
			for(int j=i;j>=1;j--){
				w[j][i]-=fen.query(j);
			}
		}
	}
	for(int i=1;i<=m+1;i++){
		for(int j=1;j<i;j++){
			dp[1][i]=max(dp[1][i],w[j][i]);
		}
	}
	cout<<dp[1][m+1]<<endl;
	for(int i=2;i<=m;i++){
		f(1,m+1,1,m+1,i);
		cout<<dp[i][m+1]<<endl;
	}

	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6744 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6744 KB Output is correct
7 Correct 5 ms 12636 KB Output is correct
8 Correct 5 ms 12320 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 5 ms 12320 KB Output is correct
11 Correct 4 ms 12124 KB Output is correct
12 Correct 4 ms 12040 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6744 KB Output is correct
7 Correct 5 ms 12636 KB Output is correct
8 Correct 5 ms 12320 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 5 ms 12320 KB Output is correct
11 Correct 4 ms 12124 KB Output is correct
12 Correct 4 ms 12040 KB Output is correct
13 Correct 183 ms 84472 KB Output is correct
14 Correct 174 ms 85936 KB Output is correct
15 Correct 160 ms 72400 KB Output is correct
16 Correct 158 ms 84260 KB Output is correct
17 Correct 131 ms 72020 KB Output is correct
18 Correct 131 ms 71620 KB Output is correct