Submission #41505

#TimeUsernameProblemLanguageResultExecution timeMemory
41505festJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
917 ms7784 KiB
// fest #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define y1 dasdasfasfas #define x1 wqdadfasfasfas #define All(c) c.begin(), c.end() #define SZ(A) (int((A).size())) #define umap unordered_map #define FILENAME "" #define __ fflush(stdout) typedef long long ll; typedef long double ld; using namespace std; void FREOPEN() { #ifdef COMP freopen(".in", "r", stdin); freopen("1.out", "w", stdout); #else freopen(FILENAME".in", "r", stdin); freopen(FILENAME".out", "w", stdout); #endif } inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; } const int N = 200500, inf = 1e9 * 2, MOD = (int)1e9 + 7; char CH[N]; const ll INF = 1e18; const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1}; const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1}; int dp[N]; vector<int> have[N]; int main() { int n, m; scanf("%d %d", &n, &m); int start = 0, finish = 0; for (int i = 0; i < m; i++) { int b, p; scanf("%d %d", &b, &p); have[b].pb(p); if (i == 0) start = b; if (i == 1) finish = b; } for (int i = 0; i < n; i++) dp[i] = inf; dp[start] = 0; set<pair<int, int> > s; s.insert({0, start}); while (!s.empty()) { int v = s.begin() -> S; s.erase(s.begin()); for (auto p : have[v]) { for (int mul = 1; v + mul * p < n; mul++) { int u = v + mul * p; if (dp[u] > dp[v] + mul) { s.erase({dp[u], u}); dp[u] = dp[v] + mul; s.insert({dp[u], u}); } } for (int mul = 1; v - mul * p >= 0; mul++) { int u = v - mul * p; if (dp[u] > dp[v] + mul) { s.erase({dp[u], u}); dp[u] = dp[v] + mul; s.insert({dp[u], u}); } } } } if (dp[finish] == inf) dp[finish] = -1; cout << dp[finish]; return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'void FREOPEN()':
skyscraper.cpp:25:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".in", "r", stdin);
                                     ^
skyscraper.cpp:26:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".out", "w", stdout);
                                       ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:48: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:52:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &b, &p);
                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...