제출 #868598

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

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10;
int n,m,av;
set<int>fst[maxn];
vector<int>st[maxn];
int s=0,te=0;

void upd(int ind,int p){
	st[ind].push_back(p);
	if(fst[ind].count(p)!=0){
		return ;
	}
	fst[ind].insert(p);
	for(int i=ind-p;i>=0;i-=p){
		te++;
		fst[i].insert(p);
	}
	for(int i=ind+p;i<n;i+=p){
		te++;
		fst[i].insert(p);
	}
}

int solve(){
	vector<pair<int,pair<int,int>>>di;
	for(auto x:st[av]){
		di.push_back(make_pair(0,make_pair(av,x)));
	}
	for(int i=0;i<(int)di.size();i++){
		auto x=di[i];
		if(x.second.first<0||x.second.first>=n){
			continue;
		}
		if(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(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		upd(u,v);
		if(i==1){
			s=u;
		}
		if(i==0){
			av=u;
		}
	}
	if(te>30000000){
		assert(0);
	}
	cout<<solve()<<"\n";
}

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