Submission #14449

#	Time	Username	Problem	Language	Result	Execution time	Memory
14449		dohyun0324	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	57 / 100	1000 ms	3028 KiB

skyscraper

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>v[30010];
int k,top,arr[30010],pos,n,m,d[30010],now,c,ch[30010],mini;
struct data
{
    int x,p;
}a[30010];
int min(int x,int y)
{
    if(x>y) return y;
    return x;
}
int main()
{
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++) ch[i]=1;
    for(i=0;i<m;i++)
    {
        scanf("%d %d",&a[i].x,&a[i].p);
        v[a[i].x].push_back(i);
        ch[a[i].x]=0;
    }
    for(i=0;i<n;i++) d[i]=2147483647;
    d[a[0].x]=0;
    now=a[0].x;
    top=0; k=v[now].size();
    for(i=0;i<k;i++) arr[++top]=a[v[now][i]].p;
    arr[0]=-1;
    while(1)
    {
        ch[now]=1;
        for(i=1;i<=top;i++)
        {
            if(arr[i]==arr[i-1]) continue;
            c=0;
            for(j=now;j<n;j+=arr[i])
            {
                d[j]=min(d[j],d[now]+c);
                c++;
            }
            c=0;
            for(j=now;j>=0;j-=arr[i])
            {
                d[j]=min(d[j],d[now]+c);
                c++;
            }
        }
        mini=2147483647; pos=-1;
        for(i=0;i<n;i++)
        {
            if(mini>d[i] && ch[i]==0) mini=d[i], pos=i;
        }
        if(pos==-1) break;
        top=0; k=v[pos].size();
        for(i=0;i<k;i++) arr[++top]=a[v[pos][i]].p;
        now=pos;
        if(now==a[1].x) break;
    }
    if(d[a[1].x]==2147483647) printf("-1\n");
    else printf("%d\n",d[a[1].x]);
    return 0;
}

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