Submission #151866

#	Time	Username	Problem	Language	Result	Execution time	Memory
151866		Ruxandra985	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	818 ms	3948 KiB

skyscraper

/// cine ia tle ? eu iau tle
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define DIMN 30010

using namespace std;
priority_queue <pair <int,int> > h;
int f[DIMN],dp[DIMN];
pair <int,int> v[DIMN];
vector <int> poz[DIMN];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n,m,i,curr,add,jump,p,idx;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&v[i].first,&v[i].second);
        v[i].first++;
        poz[v[i].first].push_back(i);
    }
    for (i=1;i<=n;i++)
        dp[i] = 2000000000;
    h.push(make_pair(0,v[1].first));
    dp[v[1].first] = 0;
    while (!h.empty()){
        curr = h.top().second;
        h.pop();
        while (f[curr] && !h.empty()){
            curr = h.top().second;
            h.pop();
        }
        if (h.empty() && f[curr])
            break;
        f[curr] = 1;
        /// cost = dp[curr]
        for (i=0;i<poz[curr].size();i++){
            idx = poz[curr][i];
            add = v[idx].second;
            p = curr + add;
            jump = 1;
            while (p<=n){
                if (dp[p] > dp[curr] + jump){
                    dp[p] = dp[curr] + jump;
                    h.push(make_pair(-dp[p] , p));
                }
                p+=add;
                jump++;
            }
            p = curr - add;
            jump = 1;
            while (p>0){
                if (dp[p] > dp[curr] + jump){
                    dp[p] = dp[curr] + jump;
                    h.push(make_pair(-dp[p] , p));
                }
                p-=add;
                jump++;
            }
        }
    }
    if (dp[v[2].first] == 2000000000)
        dp[v[2].first] = -1;
    fprintf (fout,"%d",dp[v[2].first]);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<poz[curr].size();i++){
                  ~^~~~~~~~~~~~~~~~~
skyscraper.cpp:18:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
skyscraper.cpp:20:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&v[i].first,&v[i].second);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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