oj.uz

Submission #1051394

# Submission time Handle Problem Language Result Execution time Memory
1051394 2024-08-10T05:53:24 Z PieArmy Nafta (COI15_nafta) C++17
100 / 100
 168 ms 47136 KB 
#include<bits/stdc++.h>
typedef long long ll;
#define fr first
#define sc second
#define pb push_back
#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 6492 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 6492 KB Output is correct
7 Correct 5 ms 10012 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 3 ms 9784 KB Output is correct
12 Correct 3 ms 9820 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 6492 KB Output is correct
7 Correct 5 ms 10012 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 3 ms 9784 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 164 ms 47036 KB Output is correct
14 Correct 161 ms 47136 KB Output is correct
15 Correct 168 ms 40272 KB Output is correct
16 Correct 144 ms 46268 KB Output is correct
17 Correct 120 ms 40176 KB Output is correct
18 Correct 120 ms 39956 KB Output is correct