Submission #146546

#	Time	Username	Problem	Language	Result	Execution time	Memory
146546		arnold518	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	466 ms	48468 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const ll INF = 1e14;

int N, M, B[MAXN+10], P[MAXN+10];
ll dist[MAXN+10], adj[MAXN+10][MAXN+10];

struct Queue
{
    int u; ll w;
    bool operator < (const Queue &p) const { return w>p.w; }
};

int main()
{
    int i, j;

    scanf("%d%d", &N, &M);
    for(i=1; i<=M; i++) scanf("%d%d", &B[i], &P[i]), B[i]++;

    for(i=1; i<=N; i++) for(j=1; j<=N; j++) adj[i][j]=INF;
    for(i=1; i<=M; i++)
    {
        for(j=1; B[i]+j*P[i]<=N; j++) adj[B[i]][B[i]+j*P[i]]=min(adj[B[i]][B[i]+j*P[i]], (ll)j);
        for(j=1; B[i]-j*P[i]>=1; j++) adj[B[i]][B[i]-j*P[i]]=min(adj[B[i]][B[i]-j*P[i]], (ll)j);
    }

    for(i=1; i<=N; i++) dist[i]=INF;

    priority_queue<Queue> PQ;
    PQ.push({B[1], 0});

    while(!PQ.empty())
    {
        Queue now=PQ.top(); PQ.pop();
        if(dist[now.u]<=now.w) continue;
        dist[now.u]=now.w;
        for(i=1; i<=N; i++) if(adj[now.u][i]!=INF && dist[i]>now.w+adj[now.u][i]) PQ.push({i, now.w+adj[now.u][i]});
    }
    if(dist[B[2]]==INF) dist[B[2]]=-1;
    printf("%lld", dist[B[2]]);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:25:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=M; i++) scanf("%d%d", &B[i], &P[i]), B[i]++;
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

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