oj.uz

Submission #147289

# Submission time Handle Problem Language Result Execution time Memory
147289 2019-08-28T18:17:17 Z xDWaffle Journey (NOI18_journey) C++11
20 / 100
 2 ms 376 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]);
            }
        }
    }

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

    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 256 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -