oj.uz

Submission #432008

# Submission time Handle Problem Language Result Execution time Memory
432008 2021-06-17T19:02:10 Z Malheiros Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 59552 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define ld long double
#define ll long long
#define FF first.first
#define FS first.second
#define SF second.first
#define SS second.second
#define PB push_back
#define MP make_pair
#define all(cont) cont.begin(),cont.end()
#define rall(cont) cont.rbegin(), cont.rend()
#define FOR(i, j) for(int i=0;i<j;i++)
#define RFOR(i, j) for (int i=j;i>=0;i--)
#define GO cin.tie(NULL);
#define FAST ios_base::sync_with_stdio(false);
typedef pair<int,int> pii;
 
 
// Your function
//DEBBUGGING STUFF, JUST USE deb(a,b,c) and it will print the variables;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cout << vars << " = ";
    string delim = "";
    (..., (cout << delim << values, delim = ", "));
    cout<<endl;
}
 
 const int maxn=2010;
 int v[maxn][maxn];
 int dp[maxn][maxn];
 int c[maxn];
 int n,m;
 int ccome[maxn];
 int custo[maxn][maxn];
 vector<pair<pii,int>> comecam[maxn];
 vector<pair<pii,int>> terminam[maxn];

 bool valid(int a,int b){
	 if (a<0 || a>=n || b<0 || b>=m || v[a][b]==-1)return false;
	 return true;
 }

 pair<pii,int> bfs(int a,int b){
	 int menor=b;
	 int maior=b;
	 queue<pii> q;
	 int tot=0;
	 q.push({a,b});
	 tot+=v[a][b];
	 v[a][b]=-1;
	while(!q.empty()){
		auto o=q.front();
		q.pop();
		auto i=o.first;
		auto j=o.second;
		if (valid(i+1,j)){
			tot+=v[i+1][j];
			v[i+1][j]=-1;
			q.push({i+1,j});
		}
		if(valid(i-1,j)){
			tot+=v[i-1][j];
			v[i-1][j]=-1;
			q.push({i-1,j});
		}
		if(valid(i,j-1)) {
			tot+=v[i][j-1];
			v[i][j-1]=-1;
			menor=min(menor,j-1);
			q.push({i,j-1});
		}
		if(valid(i,j+1)){
			tot+=v[i][j+1];
			maior=max(maior,j+1);
			v[i][j+1]=-1;
			q.push({i,j+1});
		}
	}
	return MP(MP(menor,maior),tot);
 }

void solve(int i,int l,int r,int searchL,int searchR){
	if(l>r)return;
	int mid=(l+r)/2;
	int validR=min(searchR,mid);
	pii melhor=MP(c[mid],-1);
	for (int j=searchL;j<=validR;j++){
		melhor=max(melhor,MP(dp[i-1][j]+custo[j][mid],j));
	}
	dp[i][mid]=melhor.first;	
	if(melhor.second==-1)return;
	solve(i,l,mid-1,searchL,melhor.second);
	solve(i,mid+1,r,melhor.second,searchR);
}
 
int main(){
	GO FAST
	cin>>n>>m;
	FOR(i,n){
		FOR(j,m){
			char c;cin>>c;
			if (c=='.'){
				v[i][j]=-1;
			}
			else v[i][j]=c-'0';
		}
	}
	vector<pair<pii,int>> ranges;
	FOR(i,n){
		FOR(j,m){
			if(v[i][j]!=-1){
				ranges.PB(bfs(i,j));
			}
		}
	}
	for(auto k:ranges){
		comecam[k.FF].PB(k);
		ccome[k.FF]+=k.second;
	}
	for(auto k:ranges){
		terminam[k.FS].PB(k);
	}
	for(auto k:comecam[0]){
		c[0]+=k.second;
	}
	for (int i=1;i<m;i++){
		c[i]=c[i-1];
		for (auto k:comecam[i])c[i]+=k.second;
		for(auto k:terminam[i-1])c[i]-=k.second;
	}
	for(int j=0;j<m;j++){
		//C[i][j]=C[i][j-1]+comecamaqui[j];
		//custo de ter uma coisa em j menos as coisas que estao em i e j
		custo[0][j]=c[j];
		for(auto k:comecam[0]){
			if (k.FS>=j)custo[0][j]-=k.second;
		}
		for(int i=1;i<j;i++){
			custo[i][j]=custo[i-1][j];
			for(auto k:comecam[i]){
				if(k.FS>=j)custo[i][j]-=k.second;
			}
		}

	}
/*	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			cout<<custo[i][j]<<" ";
		}
		cout<<endl;
	}*/
	int melhor=0;
	for(int i=0;i<m;i++){
		dp[1][i]=c[i];
		melhor=max(melhor,c[i]);
	}
	cout<<melhor<<endl;
	
	for(int i=2;i<=m;i++){
		solve(i,0,m-1,0,m-1);
		int tot=0;
		for(int j=0;j<m;j++){
		tot=max(tot,dp[i][j]);
		}
		cout<<tot<<endl;
	}
	
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 2 ms 1048 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 2 ms 1048 KB Output is correct
7 Correct 14 ms 5624 KB Output is correct
8 Correct 11 ms 5196 KB Output is correct
9 Correct 11 ms 4940 KB Output is correct
10 Correct 13 ms 5252 KB Output is correct
11 Correct 9 ms 5068 KB Output is correct
12 Correct 8 ms 5032 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 2 ms 1048 KB Output is correct
7 Correct 14 ms 5624 KB Output is correct
8 Correct 11 ms 5196 KB Output is correct
9 Correct 11 ms 4940 KB Output is correct
10 Correct 13 ms 5252 KB Output is correct
11 Correct 9 ms 5068 KB Output is correct
12 Correct 8 ms 5032 KB Output is correct
13 Execution timed out 1084 ms 59552 KB Time limit exceeded
14 Halted 0 ms 0 KB -