Submission #43574

#	Time	Username	Problem	Language	Result	Execution time	Memory
43574		RezwanArefin01	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	13 ms	16516 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int maxn = 2010;
vector<int> jump[maxn];
int n, m, b[maxn], p[maxn], dp[2010][2010], vis[2010][2010];
vector<ii> adj[maxn]; 

int f(int u, int len) {
	if(u == b[1]) return 0;
	if(vis[u][len] == 1) return 1e9;

	int &ret = dp[u][len]; 
	if(vis[u][len] == 2) return ret; 

	vis[u][len] = 1;
	ret = 1e9;
	if(u + len < n) ret = 1 + f(u + len, len);
	if(u - len >= 0) ret = min(ret, 1 + f(u - len, len));

	for(ii v : adj[u]) ret = min(ret, 1 + f(v.first, v.second)); 

	vis[u][len] = 2; 
	return ret ;
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	scanf("%d %d", &n, &m);
	if(n == 1) { puts("-1"); return 0; }

	for(int i = 0; i < m; i++) {
		scanf("%d %d", &b[i], &p[i]); 
		jump[b[i]].push_back(p[i]); 
	}	
	for(int i = 0; i < n; i++) {
		sort(jump[i].begin(), jump[i].end()); 
		jump[i].erase(unique(jump[i].begin(), jump[i].end()), jump[i].end()); 

		for(int p : jump[i]) {
			if(i + p < n) adj[i].emplace_back(i + p, p);
			if(i - p >= 0) adj[i].emplace_back(i - p, p);  

		} 
	}

	memset(dp, -1, sizeof dp);
	int ret = f(b[0], p[0]); 
	if(ret >= 1e8) cout << "-1" << endl;
	else cout << ret << endl;

}

Compilation message (stderr)

skyscraper.cpp: In function 'int main(int, const char**)':
skyscraper.cpp:33:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
skyscraper.cpp:37:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &b[i], &p[i]); 
                               ^

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