22082023-01-02 23:35:42kohumarkJegesmedve (50)cpp11Futási hiba 19/50400ms4444 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;
	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.push_back(halak);
		for(int i=0; i<temp-rt; i++) halszam.push_back(halak);
		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++){
		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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base19/50
1Elfogadva0/03ms1840 KiB
2Elfogadva0/072ms2476 KiB
3Elfogadva3/314ms2704 KiB
4Elfogadva3/329ms3132 KiB
5Futási hiba0/33ms3216 KiB
6Futási hiba0/44ms3184 KiB
7Elfogadva3/319ms4008 KiB
8Elfogadva3/323ms4192 KiB
9Elfogadva3/325ms4392 KiB
10Elfogadva4/413ms4444 KiB
11Időlimit túllépés0/4400ms2960 KiB
12Időlimit túllépés0/4368ms3108 KiB
13Időlimit túllépés0/4377ms3112 KiB
14Futási hiba0/44ms4140 KiB
15Futási hiba0/44ms4428 KiB
16Futási hiba0/44ms4360 KiB