22072023-01-02 23:33:20kohumarkJegesmedve (50)cpp11Futási hiba 19/50379ms4440 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;
	int tlen=(n-2)*(m-2)*4+(n+m-4)*6+4*2;
	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 temp=0; int halak=0; int sol=0; int rt = 0;
	//int rh = 0;
	//vector<int> halszam;
	int halszam = 0;
	while(true){
		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++;
		}
		if(ntemp==1000000001) break;
		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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base19/50
1Elfogadva0/03ms1872 KiB
2Elfogadva0/013ms2196 KiB
3Elfogadva3/314ms2704 KiB
4Elfogadva3/329ms3128 KiB
5Futási hiba0/33ms3216 KiB
6Futási hiba0/44ms3452 KiB
7Elfogadva3/32ms2976 KiB
8Elfogadva3/33ms3108 KiB
9Elfogadva3/33ms3316 KiB
10Elfogadva4/43ms3464 KiB
11Időlimit túllépés0/4379ms2976 KiB
12Időlimit túllépés0/4356ms3084 KiB
13Időlimit túllépés0/4370ms3072 KiB
14Futási hiba0/44ms4440 KiB
15Futási hiba0/44ms4428 KiB
16Futási hiba0/44ms4432 KiB