# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25380 | 2017-06-21T20:05:28 Z | gabrielsimoes | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 0 ms | 2984 KB |
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; const int MAXN = 3e4; const int INF = 2e9+10; int N, M; vector<int> v[MAXN]; bool ok[MAXN]; int dp[MAXN]; int d[MAXN]; int f(int cur) { if (dp[cur] != -1) return dp[cur]; dp[cur] = INF; for (int dx : v[cur]) { int i = cur - dx; while (i > 0) dp[cur] = min(dp[cur], f(i) + (cur - i)/dx), i = i - dx; i = cur + dx; while (i < N) dp[cur] = min(dp[cur], f(i) + (i - cur)/dx), i = i + dx; } return dp[cur]; } int dijkstra() { for (int i = 0; i < N; i++) d[i] = INF; d[0] = 0; int cur = 0; while (true) { ok[cur] = true; for (int dx : v[cur]) { printf("%d-%d\n",cur,dx); int i = cur - dx; while (i > 0) d[i] = min(d[i], d[cur] + (cur - i)/dx), i -= dx; i = cur + dx; while (i < N) d[i] = min(d[i], d[cur] + (i - cur)/dx), i += dx; } for (int i = 1; i < N; i++) if (cur == -1 || d[i] < d[cur]) if (!ok[cur]) cur = i; if (cur == -1) break; } return d[1]; } int main() { scanf("%d %d", &N, &M); for (int i = 0,a,b; i < M; i++) { scanf("%d %d", &a, &b); v[a].push_back(b); } memset(dp, -1, sizeof(dp)); dp[1] = 0; int ans = f(0); printf("%d\n", ans < INF ? ans : -1); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2984 KB | Output is correct |
2 | Incorrect | 0 ms | 2984 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2984 KB | Output is correct |
2 | Incorrect | 0 ms | 2984 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2984 KB | Output is correct |
2 | Incorrect | 0 ms | 2984 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2984 KB | Output is correct |
2 | Incorrect | 0 ms | 2984 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2984 KB | Output is correct |
2 | Incorrect | 0 ms | 2984 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |