제출 #870058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
870058		amirhoseinfar1385	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	5 ms	4124 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const short maxn=30000+10;
short n,m,av,akh[maxn];
set<short>fst[maxn];
vector<short>st[maxn];
short s=0;
 
void upd(short ind,short p){
	st[ind].push_back(p);
	if(fst[ind].count(p)!=0){
		return ;
	}
	fst[ind].insert(p);
	for(short i=ind-p;i>=0;i-=p){
		fst[i].insert(p);
	}
	for(short i=ind+p;i<n;i+=p){
		fst[i].insert(p);
	}
}
 
short solve(){
	vector<pair<short,pair<short,short>>>di;
	for(auto x:st[av]){
		di.push_back(make_pair(0,make_pair(av,x)));
	}
	for(short i=0;i<(short)di.size();i++){
		pair<short,pair<short,short>> x=di[i];
		if(x.second.first<0||x.second.first>=n){
			continue;
		}
		if((short)fst[x.second.first].size()==0||fst[x.second.first].count(x.second.second)==0){
			continue;
		}
		if(x.second.first==s){
			return x.first;
		}
		di.push_back(make_pair(x.first+1,make_pair(x.second.first-x.second.second,x.second.second)));
		di.push_back(make_pair(x.first+1,make_pair(x.second.first+x.second.second,x.second.second)));
		fst[x.second.first].erase(x.second.second);
		for(auto y:st[x.second.first]){
			di.push_back(make_pair(x.first+1,make_pair(x.second.first-y,y)));
			di.push_back(make_pair(x.first+1,make_pair(x.second.first+y,y)));
			fst[x.second.first].erase(y);
		}
		st[x.second.first].clear();
	}
	return -1;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(short i=0;i<m;i++){
		short u,v;
		cin>>u>>v;
		upd(u,v);
		if(i==1){
			s=u;
		}
		if(i==0){
			av=u;
		}
//		if(te>1000000){
//			assert(0);
//		}
	}
//	if(te>1000000){
//		assert(0);
//	}
	cout<<solve()<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43