oj.uz

Submission #43572

# Submission time Handle Problem Language Result Execution time Memory
43572 2018-03-17T22:57:35 Z RezwanArefin01 Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 14 ms 16548 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16120 KB Output is correct
2 Incorrect 1 ms 16120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16336 KB Output is correct
2 Incorrect 1 ms 16336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16412 KB Output is correct
2 Incorrect 1 ms 16412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16504 KB Output is correct
2 Incorrect 1 ms 16504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16548 KB Output is correct
2 Incorrect 1 ms 16548 KB Output isn't correct
3 Halted 0 ms 0 KB -