oj.uz

Submission #95563

# Submission time Handle Problem Language Result Execution time Memory
95563 2019-02-02T05:29:48 Z oolimry Journey (NOI18_journey) C++14
100 / 100
 253 ms 40008 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long l;
typedef pair<l, l> ii;

///stores edges where it comes from, not goes to
vector<ii> adj[10005];
l e;
l memo[10005][405];
///isWaiting 0 - false, 1- true
l dp(l city, l nights){

    if(nights < 0){
        return 0;
    }
    if(city == 0 && nights == 0){
        return 1;
    }

    if(memo[city][nights] != -1){
        return memo[city][nights];
    }

    l ways = 0;


    for(l i = 0;i < adj[city].size();i++){
        l neigh = adj[city][i].first;
        l time = adj[city][i].second;

        if(neigh < city){
            ways += dp(neigh, nights - time);
        }

        if(ways > 500000001){
            return 500000001;
        }

    }
    if(city != e){
        ways += dp(city, nights - 1);
    }
    //printf("%d %d %d\n",city,nights,ways);
    if(ways > 500000001){
        return 500000001;
    }
    memo[city][nights] = ways;
    return ways;
}

int main()
{
    //freopen("i.txt","r",stdin);
    l n, m, h;
    scanf("%lld %lld %lld",&n,&m,&h);
    e = n - 1;
    for(int i = 0;i < n - 1;i++){
        for(int j = 0;j < h;j++){
            l a, b;
            scanf("%lld %lld", &a, &b);
            adj[a].push_back(ii(i,b));
        }
    }

    memo[0][0] = 1;
    for(int i = 0;i < 10003;i++){
        for(int j = 0 ;j < 403;j++){
            memo[i][j] = -1;
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < adj[i].size();j++){
            //printf("%lld %lld | ",adj[i][j].first,adj[i][j].second);
        }
        //printf("\n");
    }

    for(int i = 0;i < m;i++){
        printf("%lld ",dp(n-1, i));
        //printf("\n\n\n");
    }


    return 0;
}

Compilation message

journey.cpp: In function 'l dp(l, l)':
journey.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(l i = 0;i < adj[city].size();i++){
                 ~~^~~~~~~~~~~~~~~~~~
journey.cpp: In function 'int main()':
journey.cpp:73:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < adj[i].size();j++){
                       ~~^~~~~~~~~~~~~~~
journey.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld",&n,&m,&h);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
journey.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld %lld", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 32248 KB Output is correct
2 Correct 30 ms 32248 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 32248 KB Output is correct
2 Correct 27 ms 32248 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 32248 KB Output is correct
2 Correct 30 ms 32248 KB Output is correct
3 Correct 28 ms 32248 KB Output is correct
4 Correct 27 ms 32248 KB Output is correct
5 Correct 27 ms 32376 KB Output is correct
6 Correct 27 ms 32400 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 32248 KB Output is correct
2 Correct 30 ms 32248 KB Output is correct
3 Correct 28 ms 32248 KB Output is correct
4 Correct 27 ms 32248 KB Output is correct
5 Correct 27 ms 32376 KB Output is correct
6 Correct 27 ms 32400 KB Output is correct
7 Correct 144 ms 40008 KB Output is correct
8 Correct 253 ms 37028 KB Output is correct
9 Correct 51 ms 32912 KB Output is correct
10 Correct 69 ms 35192 KB Output is correct