oj.uz

Submission #775370

# Submission time Handle Problem Language Result Execution time Memory
775370 2023-07-06T10:26:55 Z vjudge1 T-Covering (eJOI19_covering) C++17
30 / 100
 56 ms 19408 KB 
#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl "\n"
#define ll long long
#define pb push_back
#define N 2000000
int k,n,m;
ll int off[N],alan[N];
int arr[N][2];
ll int hmm(int yer){
	if(yer>=k)return 0;
	ll int cev=-1000000000000;
	int a=arr[yer][0],b=arr[yer][1];
	b++;
	int konum=(a*m)+b;
	if(konum+m<=n*m&&konum-m>0&&alan[konum+m]==0&&alan[konum-m]==0){
		if((konum-1)%m&&konum>1&&alan[konum-1]==0){
			alan[konum+m]=alan[konum-m]=alan[konum-1]=1;
			cev=max(cev,off[konum+m]+off[konum-m]+off[konum-1]+off[konum]+hmm(yer+1));
			alan[konum+m]=alan[konum-m]=alan[konum-1]=0;
			//cout<<yer<<" a "<<cev<<" "<<konum<<endl;		
		}
		if(konum%m&&alan[konum+1]==0){
			alan[konum+m]=alan[konum-m]=alan[konum+1]=1;
			cev=max(cev,off[konum+m]+off[konum-m]+off[konum+1]+off[konum]+hmm(yer+1));
			alan[konum+m]=alan[konum-m]=alan[konum+1]=0;
			//cout<<yer<<" b "<<cev<<" "<<konum<<endl;
		}
	}
	if((konum-1)%m&&konum>1&&konum%m&&alan[konum-1]==0&&alan[konum+1]==0){
		if(konum+m<=n*m&&alan[konum+m]==0){
			alan[konum+m]=alan[konum+1]=alan[konum-1]=1;
			cev=max(cev,off[konum+m]+off[konum+1]+off[konum-1]+off[konum]+hmm(yer+1));
			alan[konum+m]=alan[konum+1]=alan[konum-1]=0;

			//cout<<yer<<" c "<<cev<<" "<<konum<<endl;
		}
		if(konum-m>0&&alan[konum-m]==0){
			alan[konum-m]=alan[konum+1]=alan[konum-1]=1;
			cev=max(cev,off[konum-m]+off[konum+1]+off[konum-1]+off[konum]+hmm(yer+1));
			alan[konum-m]=alan[konum+1]=alan[konum-1]=0;

			//cout<<yer<<" d "<<cev<<" "<<konum<<endl;
		}
	}
	//cout<<yer<<"_"<<cev<<" "<<konum<<endl;
	return cev;
}
map<pair<int,int>,int> mp;
int main(){
	lalala;
	cin>>n>>m;
	int mat[n][m];
	int yap[n][m];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>mat[i][j];
			off[i*m+j+1]=mat[i][j];
			yap[i][j]=0;
		}
	}

	cin>>k;
	ll int cev=0;
	int yes=1;
	for(int i=0;i<k;i++){
		cin>>arr[i][0]>>arr[i][1];
		alan[arr[i][0]*m+arr[i][1]+1]=1;
		if(mp[{arr[i][0],arr[i][1]}]){
			yes=0;
		}
		mp[{arr[i][0],arr[i][1]}]=1;
	}

	if(yes==0){
		cout<<"No"<<endl;
		return 0;
	}
	if(k<=10){
		cev=hmm(0);
		if(cev>-1)cout<<cev<<endl;
		else cout<<"No"<<endl;
		return 0;
	}
	for(int i=0;i<k&&yes;i++){
		int a=arr[i][0], b=arr[i][1];
		int kac=0,toplam=0;
		cev+=mat[a][b];
		if(mp[{a+1,b}]){
			kac++;
			if(a+2>=n||a-1<0||b+1>=m||b-1<0){yes=0;break;}
			toplam=(mat[a-1][b]+mat[a+2][b]+mat[a][b-1]+mat[a][b+1]+mat[a+1][b-1]+mat[a+1][b+1]);
			yap[a+1][b]=1;		}
		if(mp[{a-1,b}]){
			kac++;
			if(a+1>=n||a-2<0||b+1>=m||b-1<0){yes=0;break;}
			toplam=(mat[a+1][b]+mat[a-2][b]+mat[a][b-1]+mat[a][b+1]+mat[a-1][b-1]+mat[a-1][b+1]);
			yap[a-1][b]=1;
		}
		if(mp[{a,b+1}]){
			kac++;
			if(a+1>=n||a-1<0||b+2>=m||b-1<0){yes=0;break;}
			toplam=(mat[a+1][b]+mat[a-1][b]+mat[a][b-1]+mat[a][b+2]+mat[a-1][b+1]+mat[a+1][b+1]);
			yap[a][b+1]=1;
		}
		if(mp[{a,b-1}]){
			kac++;
			if(a+1>=n||a-1<0||b+1>=m||b-2<0){yes=0;break;}
			toplam=(mat[a+1][b]+mat[a-1][b]+mat[a][b+1]+mat[a][b-2]+mat[a-1][b-1]+mat[a+1][b-1]);
			yap[a][b-1]=1;
		}
		if(kac){
			if(kac>1){yes=0;break;}
			//cout<<toplam<<endl;
			if(yap[a][b]==0)cev+=toplam;
			continue;
		}
		int aaa=0;
		if(a+1<n&&a-1>-1){
			if(b+1<m)aaa=max(aaa,mat[a+1][b]+mat[a-1][b]+mat[a][b+1]);
			if(b-1>-1)aaa=max(aaa,mat[a+1][b]+mat[a-1][b]+mat[a][b-1]);
		}
		if(b+1<m&&b-1>-1){
			if(a+1<n)aaa=max(aaa,mat[a+1][b]+mat[a][b-1]+mat[a][b+1]);
			if(a-1>-1)aaa=max(aaa,mat[a][b+1]+mat[a-1][b]+mat[a][b-1]);
		}
		//cout<<a<<" "<<b<<aaa<<endl;
		if(yap[a][b]==0)cev+=aaa;
		yap[a][b]=1;
		if(aaa==0){yes=0;break;}
	}
	if(yes)cout<<cev<<endl;
	else cout<<"No"<<endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 468 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 6 ms 2164 KB Output is correct
4 Correct 17 ms 6484 KB Output is correct
5 Correct 56 ms 19408 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 532 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 6 ms 2184 KB Output is correct
4 Correct 16 ms 6484 KB Output is correct
5 Correct 54 ms 19348 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 468 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 6 ms 2164 KB Output is correct
4 Correct 17 ms 6484 KB Output is correct
5 Correct 56 ms 19408 KB Output is correct
6 Correct 8 ms 532 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 6 ms 2184 KB Output is correct
9 Correct 16 ms 6484 KB Output is correct
10 Correct 54 ms 19348 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Incorrect 2 ms 908 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 468 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 6 ms 2164 KB Output is correct
4 Correct 17 ms 6484 KB Output is correct
5 Correct 56 ms 19408 KB Output is correct
6 Correct 8 ms 532 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 6 ms 2184 KB Output is correct
9 Correct 16 ms 6484 KB Output is correct
10 Correct 54 ms 19348 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Incorrect 2 ms 908 KB Output isn't correct
13 Halted 0 ms 0 KB -