Submission #147290

#	Time	Username	Problem	Language	Result	Execution time	Memory
147290		xDWaffle	Journey (NOI18_journey)	C++11	100 / 100	209 ms	10620 KiB

journey

#include <bits/stdc++.h>
#define ff(j, a, b) for(long long j=a;j<b;j++)
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<ll> vll;

ll n, m, h;
vpll* planes;
vll* dp;
ll MAX=500000001;

int main()
{
    cin >> n >> m >> h;

    planes = new vpll[n];
    dp = new vll[n];

    ff(j, 0, m)
    {
        dp[0].pb(0);
    }
    ff(j, 1, n)
    {
        dp[j]=dp[0];
    }
    ff(j, 0, n-1)
    {
        ff(k, 0, h)
        {
            ll dest, wait;
            cin >> dest >> wait;
            if(dest<=j)
            {
                continue;
            }
            planes[j].pb( pll(dest, wait) );
        }
    }

    dp[0][0]=1;
    ff(j, 0, n-1)
    {
        ff(k, 1, m)
        {
            dp[j][k] += dp[j][k-1];
            dp[j][k] = min(dp[j][k], MAX);
        }
        ff(p, 0, planes[j].size())
        {
            ll dest=planes[j][p].first, wait=planes[j][p].second;
            ff(t, 0, m-wait)
            {
                dp[dest][wait+t] += dp[j][t];
                dp[dest][wait+t] = min(MAX, dp[dest][wait+t]);
            }
        }
    }


    ff(j, 0, m)
    {
        cout << dp[n-1][j] << endl;
    }

    return 0;
}

Compilation message (stderr)

journey.cpp: In function 'int main()':
journey.cpp:2:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define ff(j, a, b) for(long long j=a;j<b;j++)
journey.cpp:54:12:
         ff(p, 0, planes[j].size())
            ~~~~~~~~~~~~~~~~~~~~~~       
journey.cpp:54:9: note: in expansion of macro 'ff'
         ff(p, 0, planes[j].size())
         ^~

• Subtask 1: 20 / 20
• Subtask 2: 23 / 23
• Subtask 3: 26 / 26
• Subtask 4: 31 / 31