Submission #43572

#	Time	Username	Problem	Language	Result	Execution time	Memory
43572		RezwanArefin01	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	14 ms	16548 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, vis[maxn][maxn], dp[maxn][maxn], b[maxn], p[maxn];
int cnt = 0;
int f(int pos, int len) {
	//if(++cnt > 10) exit(0);
	if(pos == b[1]) return 0;
	if(pos > n || pos < 0) return 1e9;
	if(vis[pos][len] == 1) return 1e9; 
	int &ret = dp[pos][len];
	if(vis[pos][len] == 2) return ret;

	vis[pos][len] = 1;
	
	ret = min(f(pos + len, len), f(pos - len, len)) + 1; 

	for(int p : jump[pos]) {
		ret = min(ret, 1 + f(pos + p, p));
		ret = min(ret, 1 + f(pos - p, p));
	}

	vis[pos][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]); 
	}	
	memset(dp, -1, sizeof dp); 
	printf("%d\n", f(b[0], p[0]));
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main(int, const char**)':
skyscraper.cpp:35: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:38: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