Submission #847583

#	Time	Username	Problem	Language	Result	Execution time	Memory
847583		Qiroz167	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	45 ms	18132 KiB

skyscraper

#include <bits/stdc++.h>
#define quan160607 "BoundSeq"
#define fi first
#define se second
#define pii pair<int, int>
#define piii pair<int, pii>
#define pb push_back
using namespace std;
typedef long long ll;
const ll oo = 1e18;
const int inf = 2e9;
const int nmax = 2000 + 5;
void start()
{
//    freopen(quan160607".inp","r",stdin);
//    freopen(quan160607".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m;
int b[nmax], a[nmax], p[nmax], dp[nmax][nmax];
vector<int> v[nmax];
priority_queue<piii, vector<piii>, greater<piii>> q;
bool ck[nmax];
bool minimize(int &a, int b)
{
    if(a > b)
    {
        a = b;
        return true;
    } else return false;
}

void dij()
{
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
            dp[i][j] = inf;
    }
//    cout << "kaka\n";
    for(auto x : v[b[0]])
    {
        dp[b[0]][p[x]] = 0;
        q.push({dp[b[0]][p[x]], {b[0], x}});
    }
//    cout << b[0] << "\n";
    while(!q.empty())
    {
        piii temp = q.top();
        q.pop();
        int u = temp.se.fi, pk = p[temp.se.se];
//        cout << u << " " << pk << "\n";
        if(temp.fi != dp[u][pk])
            continue;
//        cout << "kaka\n";
        for(auto x : v[u])
        {
//            cout << p[x] << "\n";
            if(p[x] > n) continue;
            for(int i = u + p[x]; i < n; i += p[x]) {
//                cout << i << " ";
                if(minimize(dp[i][p[x]], dp[u][pk] + (i - u) / p[x]))
                    q.push({dp[i][p[x]], {i, x}});
            }
            for(int i = u - p[x]; i >= 0; i -= p[x]) {
                if(minimize(dp[i][p[x]], dp[u][pk] + (u - i) / p[x]))
                    q.push({dp[i][p[x]], {i, x}});
            }
        }
    }
}
int main()
{
    start();
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        cin >> b[i] >> p[i];
        v[b[i]].push_back(i);
    }
    dij();
    int ans = inf;
    for(int j = 0; j <= n; j++)
        ans = min(ans, dp[b[1]][j]);
    cout << (ans == inf ? -1 : ans);
}

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