Submission #1109279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109279		ALTAKEXE	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1053 ms	2384 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define inf INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) (x.begin(), x.end())
const int MOD = 1e9 + 7;
const int mx = 3e4 + 5;
using namespace std;
int d[mx], b[mx], p[mx];
bool vis[mx];
vector<int> v[mx];
int main()
{
  int n, m, q = 0;
  cin >> n >> m;
  FOR(i, 0, mx)
  d[i] = inf;
  FOR(i, 0, m)
  {
    cin >> b[i] >> p[i];
    v[b[i]].push_back(p[i]);
  }
  int idx = b[0];
  d[idx] = 0;
  while (!vis[b[1]] && idx != -1)
  {
    vis[idx] = 1;
    for (auto it : v[idx])
    {
      for (int j = 1; idx + j * it < n; j++)
        d[idx + j * it] = min(d[idx + j * it], d[idx] + j);
      for (int j = 1; idx - j * it >= 0; j++)
        d[idx - j * it] = min(d[idx - j * it], d[idx] + j);
    }
    idx = -1;
    FOR(i, 0, n)
    {
      if (vis[i])
        continue;
      if (d[i] == inf)
        continue;
      if (idx == -1 || d[idx] > d[i])
        idx = i;
    }
  }
  if (d[b[1]] == inf)
    d[b[1]] = -1;
  cout << d[b[1]] << endl;
  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:17:13: warning: unused variable 'q' [-Wunused-variable]
   17 |   int n, m, q = 0;
      |             ^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43