Submission #113136

#	Time	Username	Problem	Language	Result	Execution time	Memory
113136		_demon_	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	101 ms	128532 KiB

skyscraper

 #include <bits/stdc++.h>
    using namespace std;
    long long n,m;
    long long a[2009];
    long long p[2009];
    long long done[2009][2009][4];
    long long dp[2009][2009][4];
    vector<long long>v[10009];
    long long inf=1000000000000009ll;
    long long bt(long long id,long long dog,int t){
            //cout<<id<<" "<<dog<<" "<<t<<endl;
            if(id<0 || id>=n)return inf;
            if(done[id][dog][t]==1)return inf;
            done[id][dog][t]=1;
            if(id==a[1])return 0;
            long long &ret=dp[id][dog][t];
            if(ret!=-1)return ret;
            if(t==0) ret=min(bt(id,dog,1),bt(id,dog,2));
            if(t==2) ret=bt(id-p[dog],dog,2)+1;
            if(t==1) ret=bt(id+p[dog],dog,1)+1;
            for(int i=0;i<v[id].size();i++){
                    long long D=v[id][i];
                    ret=min(ret,bt(id,D,0));
            }
            return ret;
    }
    int main(){
            memset(dp,-1,sizeof(dp));
            cin>>n>>m;
            for(int i=0;i<m;i++){
                    cin>>a[i]>>p[i];
                    v[a[i]].push_back(i);
            }
            long long x=bt(a[0],0,0);
            if(x!=inf) cout<<x<<endl;
            else cout<<-1<<endl;
    }

Compilation message (stderr)

skyscraper.cpp: In function 'long long int bt(long long int, long long int, int)':
skyscraper.cpp:21:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<v[id].size();i++){
                         ~^~~~~~~~~~~~~

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