22102023-01-02 23:51:45kohumarkJegesmedve (50)cpp17Runtime error 19/50400ms4672 KiB
#include <iostream>
#include <set>
//#include <vector>
#define speed ios::sync_with_stdio(false);cin.tie(NULL)
#define mp make_pair
using namespace std;

int tomb[10000][4];
int adat[100][100][2];

int main(){
	int n, m, x, y;
	speed;
	cin >> n >> m;
	for(int k=0; k<2; k++){
		for(int i=0; i<n; i++) for(int j=0; j<m; j++){
			cin >> adat[i][j][k];
			if(adat[i][j][0]==-1){x=i; y=j;}
		}
	}
	int v=0;
	for(int i=0; i<n; i++) for(int j=0; j<m; j++){
		if(i>0){tomb[v][0]=i; tomb[v][1]=j; tomb[v][2]=i-1; tomb[v][3]=j; v++;}
		if(i<n-1){tomb[v][0]=i; tomb[v][1]=j; tomb[v][2]=i+1; tomb[v][3]=j; v++;}
		if(j>0){tomb[v][0]=i; tomb[v][1]=j; tomb[v][2]=i; tomb[v][3]=j-1; v++;}
		if(j<m-1){tomb[v][0]=i; tomb[v][1]=j; tomb[v][2]=i; tomb[v][3]=j+1; v++;}
	}
	int tlen=v;
	int temp=0; long long int halak=0; int sol=0; int rt = 0;
	//int rh = 0;
	//vector<int> halszam;
	long long int halszam = 0; bool done=false;
	while(!done){
		set<pair<int,int>> places;
		set<pair<int,int>> last;
		places.insert(mp(x,y));
		v=0; int sx = x; int sy = y;
		while(!places.empty()){
			auto it=places.begin();
			sx=(*it).first; sy=(*it).second;
			v=0;
			for(int i=0; i<tlen; i++){
				if(tomb[i][0]==sx&&tomb[i][1]==sy){
					if(adat[tomb[i][2]][tomb[i][3]][0]>=temp&&!last.count(mp(tomb[i][2],tomb[i][3]))){places.insert(mp(tomb[i][2],tomb[i][3])); v++;}
				}
				if(v==4){v=0; break;}
			}
			last.insert(*it); places.erase(it);
		}
		halak=0; int ntemp=1000000001;
		for(auto it=last.begin(); it!=last.end(); it++){
			pair<int,int> pos = *it;
			if(adat[pos.first][pos.second][0]>temp) ntemp=min(ntemp,adat[pos.first][pos.second][0]);
			halak+=adat[pos.first][pos.second][1];
		}
		places.clear(); last.clear();
		if(temp==0){
			halszam = halak-1;
			if(halszam>0) sol++;
		}
		for(int i=0; i<temp-rt; i++){
			if(halak<halszam) halszam=halak-1;
			else halszam=halszam-1;
			if(halszam>0) sol++;
			else done = true;
		}
		rt = temp;
		//rh = halak;
		temp = ntemp;
	}
	//halszam.push_back(adat[x][y][1]);
	//for(int i=0; i<(int)halszam.size(); i++){
		//cout << halszam[i] << endl;
		//halszam[i]--;
		//if(halszam[i]<=0||i==(int)halszam.size()-1){sol=i;break;}
		//int j=i+1;
		//while(halszam[j-1]<halszam[j]&&j<(int)halszam.size()){halszam[j]--; j++;}
	//}
	//cout << sol+1;
	cout << sol+1;
}
SubtaskSumTestVerdictTimeMemory
base19/50
1Accepted0/03ms1836 KiB
2Accepted0/013ms2188 KiB
3Accepted3/314ms2704 KiB
4Accepted3/329ms3040 KiB
5Runtime error0/33ms3124 KiB
6Runtime error0/44ms3428 KiB
7Accepted3/32ms2908 KiB
8Accepted3/33ms3048 KiB
9Accepted3/33ms3044 KiB
10Accepted4/43ms3172 KiB
11Time limit exceeded0/4400ms3000 KiB
12Time limit exceeded0/4368ms2936 KiB
13Time limit exceeded0/4372ms3092 KiB
14Runtime error0/44ms4204 KiB
15Runtime error0/44ms4480 KiB
16Runtime error0/44ms4672 KiB