oj.uz

Submission #43573

# Submission time Handle Problem Language Result Execution time Memory
43573 2018-03-17T23:17:07 Z RezwanArefin01 Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 13 ms 16480 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, b[maxn], p[maxn], dp[2010][2010], vis[2010][2010];
vector<ii> adj[maxn]; 

int f(int u, int len) {
	if(u == 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);
	cout << f(0, p[0]) << endl;

}

Compilation message

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:36: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 16248 KB Output is correct
2 Incorrect 1 ms 16248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16420 KB Output is correct
2 Incorrect 1 ms 16420 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 16480 KB Output is correct
2 Incorrect 2 ms 16480 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 16480 KB Output is correct
2 Incorrect 1 ms 16480 KB Output isn't correct
3 Halted 0 ms 0 KB -