oj.uz

Submission #640446

# Submission time Handle Problem Language Result Execution time Memory
640446 2022-09-14T16:36:19 Z itnes Nafta (COI15_nafta) C++14
100 / 100
 505 ms 70016 KB 
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
const ll INFLL=1e18+7;
const int INF=1e9+7;
#define pb push_back
const int MAXN=2e3+7,nTree=(1<<11);
int arr[MAXN][MAXN];
struct seg_tree{
	int T[nTree<<1];
	seg_tree(){
		for(int i=0;i<(nTree<<1);++i) T[i]=0;
	}
	void update(int l,int r,int val){
		if(l>r) return;
		l+=nTree; r+=nTree;
		T[l]+=val;
		if(l<r) T[r]+=val;
		while(l<r-1){
			if(l%2==0) T[l+1]+=val;
			if(r%2==1) T[r-1]+=val;
			l>>=1; r>>=1;
		}
	}
	int query(int pos){
		pos+=nTree;
		int res=0;
		while(pos>0){
			res+=T[pos];
			pos>>=1;
		}
		return res;
	}
};
seg_tree t[MAXN];
bool visited[MAXN][MAXN];
int cost[MAXN][MAXN];
int dp[MAXN],dp_curr[MAXN];
void dp_opt(int l,int r,int optl,int optr){
	if(l>r) return;
	int mid=(l+r)>>1;
	int best=-1,pos=0;
	for(int i=optl;i<=min(mid,optr);++i){
		if(best<(i?dp_curr[i-1]:0)+cost[i][mid]){
			best=(i?dp_curr[i-1]:0)+cost[i][mid];
			pos=i;
		}
	}
	dp[mid]=best;
	dp_opt(l,mid-1,optl,pos);
	dp_opt(mid+1,r,pos,optr);
}
int main()
{
	ios_base::sync_with_stdio(0);
	int r,s; cin>>r>>s;
	for(int i=1;i<=r;++i){
		for(int j=1;j<=s;++j){
			char c; cin>>c;
			if(c=='.') arr[i][j]=-1;
			else arr[i][j]=c-'0';
		}
	}
	vector<pii> shifts={{-1,0},{1,0},{0,-1},{0,1}};
	for(int i=1;i<=r;++i){
		for(int j=1;j<=s;++j){
			if(!visited[i][j]&&arr[i][j]!=-1){
				visited[i][j]=1;
				int L=j,R=j;
				queue<pii> Q;
				Q.push({i,j});
				int total=arr[i][j];
				while(!Q.empty()){
					pii vert=Q.front(); Q.pop();
					for(pii p:shifts){
						int new_x=vert.first+p.first,new_y=vert.second+p.second;
						if(new_x<1||new_x>r||new_y<1||new_y>s||arr[new_x][new_y]==-1||visited[new_x][new_y]) continue;
						total+=arr[new_x][new_y];
						L=min(L,new_y); R=max(R,new_y);
						visited[new_x][new_y]=1;
						Q.push({new_x,new_y});
					}
				}
				for(int k=L;k<=R;++k) t[k].update(1,L,total);
			}
		}
	}
	for(int i=1;i<=s;++i){
		for(int j=i;j<=s;++j){
			cost[i][j]=t[j].query(i);
		}
	}
	for(int i=1;i<=s;++i){
		dp_opt(0,s,0,s);
		int ans=0;
		for(int j=1;j<=s;++j) ans=max(ans,dp[j]);
		for(int j=1;j<=s;++j) dp_curr[j]=dp[j];
		cout<<ans<<"\n";
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32980 KB Output is correct
2 Correct 13 ms 32980 KB Output is correct
3 Correct 13 ms 33024 KB Output is correct
4 Correct 15 ms 33028 KB Output is correct
5 Correct 15 ms 32968 KB Output is correct
6 Correct 13 ms 32980 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32980 KB Output is correct
2 Correct 13 ms 32980 KB Output is correct
3 Correct 13 ms 33024 KB Output is correct
4 Correct 15 ms 33028 KB Output is correct
5 Correct 15 ms 32968 KB Output is correct
6 Correct 13 ms 32980 KB Output is correct
7 Correct 20 ms 36044 KB Output is correct
8 Correct 21 ms 36052 KB Output is correct
9 Correct 20 ms 36064 KB Output is correct
10 Correct 19 ms 36052 KB Output is correct
11 Correct 18 ms 36116 KB Output is correct
12 Correct 19 ms 36112 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32980 KB Output is correct
2 Correct 13 ms 32980 KB Output is correct
3 Correct 13 ms 33024 KB Output is correct
4 Correct 15 ms 33028 KB Output is correct
5 Correct 15 ms 32968 KB Output is correct
6 Correct 13 ms 32980 KB Output is correct
7 Correct 20 ms 36044 KB Output is correct
8 Correct 21 ms 36052 KB Output is correct
9 Correct 20 ms 36064 KB Output is correct
10 Correct 19 ms 36052 KB Output is correct
11 Correct 18 ms 36116 KB Output is correct
12 Correct 19 ms 36112 KB Output is correct
13 Correct 463 ms 70016 KB Output is correct
14 Correct 480 ms 69932 KB Output is correct
15 Correct 441 ms 69976 KB Output is correct
16 Correct 463 ms 69964 KB Output is correct
17 Correct 505 ms 69900 KB Output is correct
18 Correct 490 ms 70004 KB Output is correct