oj.uz

Submission #147290

# Submission time Handle Problem Language Result Execution time Memory
147290 2019-08-28T18:24:11 Z xDWaffle Journey (NOI18_journey) C++11
100 / 100
 209 ms 10620 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 348 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 380 KB Output is correct
6 Correct 4 ms 504 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 380 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 209 ms 7428 KB Output is correct
8 Correct 147 ms 10620 KB Output is correct
9 Correct 27 ms 3320 KB Output is correct
10 Correct 111 ms 5112 KB Output is correct