oj.uz

Submission #67064

# Submission time Handle Problem Language Result Execution time Memory
67064 2018-08-13T09:32:30 Z quoriess Maxcomp (info1cup18_maxcomp) C++14
0 / 100
 5 ms 508 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;
vector<vector<int> > matris;
int n,m;
typedef pair<lli,pii> data;
vector<pii> komsu(int a,int b){
	vector<pii> don;
	for (int i = -1; i < 2; i++)
	{
		for (int j = -1; j < 2; j++)
		{
			if(a+i>=0 && a+i< n && b+j<m && b+j>=0 && (i!=0||j!=0) && (i==0 || j==0)){
				don.push_back({a+i,b+j});
			}
		}
	}
	return don;
}
vector<vector<pii> > graf;
vector<vector<int> > adj;
const int MAXN=1e3+5,MAXM=1e3+5;

int piitoint(pii a){
	return a.first*m+a.second;
}
void createDag(){
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			for (auto u:komsu(i,j))
			{
				//cout << u.first <<"-"<<u.second<<"\n";
				if(matris[u.first][u.second]>=matris[i][j]){
					adj[i*m+j].push_back(u.first*m+u.second);
					//cout << "edge: "<<i*m+j<<"->"<<u.first*m+u.second<<"\n";
				}
			}
			
		}
	}
	
}
pii inttopii(int a){
	return pii(a/m,a%m);
}
vector<lli> ans;

void dfs(int node){
	//cout << "node: "<<node<<"\n";
	if(ans[node]!=-1e7)return;
	ans[node]=-1;
	for (auto u:adj[node])
	{
		//cout <<"komsu: "<<u<<"\n";
		dfs(u);
		ans[node]=max(ans[node],ans[u]+matris[u/m][u%m]-matris[node/m][node%m]-1);
	}
	
}
int main(){
	cin>>n>>m;
	adj=vector<vector<int> >(n*m,vector<int>());
	ans=vector<lli>(n*m,-1e7);
	matris=vector<vector<int> >(n,vector<int>(m,0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin>>matris[i][j];
		}
	}
	createDag();
	for (int i = 0; i < n*m; i++)
	{
		if(ans[i]==-1e7)dfs(i);
	}
	lli anss=-1e14+5;
	for (int i = 0; i < n*m; i++)
	{
		anss=max(ans[i],anss);
	}
	cout << anss<<"\n";
	
	
	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Incorrect 3 ms 508 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Incorrect 3 ms 508 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Incorrect 3 ms 508 KB Output isn't correct
5 Halted 0 ms 0 KB -