oj.uz

Submission #426253

# Submission time Handle Problem Language Result Execution time Memory
426253 2021-06-13T15:51:43 Z Amylopectin Journey (NOI18_journey) C++14
100 / 100
 368 ms 47792 KB 
#include <iostream>
#include <stdio.h>
using namespace std;
const long long mxn = 1e4 + 10,mxm = 410,mxi = 5e8 + 1;
struct pat
{
    long long to,tim;
};
struct pat pa[mxn][mxm] = {};
long long dp[mxm][mxn] = {};
int main()
{
    long long i,j,n,m,h,f,t,cti,k,o,fn;
    scanf("%lld %lld %lld",&n,&m,&h);
    for(i=0; i<n-1; i++)
    {
        for(j=0; j<h; j++)
        {
            scanf("%lld %lld",&t,&cti);
            pa[i][j] = {t,cti};
        }
    }
    dp[0][0] = 1;
    for(i=0; i<m; i++)
    {
        for(j=0; j<n-1; j++)
        {
            if(i > 0)
                dp[i][j] += dp[i-1][j];
            if(dp[i][j] > mxi)
            {
                dp[i][j] = mxi;
            }
            for(k=0; k<h; k++)
            {
                fn = pa[j][k].to;
                cti = pa[j][k].tim;
                if(i + cti < m && fn > j)
                {
                    dp[i+cti][fn] += dp[i][j];
                    if(dp[i+cti][fn] > mxi)
                    {
                        dp[i+cti][fn] = mxi;
                    }
                }
            }
        }
//        if(i > 0)
//        {
//            dp[i][n-1] += dp[i-1][n-1];
//        }
        printf("%lld\n",dp[i][n-1]);
    }
    return 0;
}

Compilation message

journey.cpp: In function 'int main()':
journey.cpp:13:25: warning: unused variable 'f' [-Wunused-variable]
   13 |     long long i,j,n,m,h,f,t,cti,k,o,fn;
      |                         ^
journey.cpp:13:35: warning: unused variable 'o' [-Wunused-variable]
   13 |     long long i,j,n,m,h,f,t,cti,k,o,fn;
      |                                   ^
journey.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%lld %lld %lld",&n,&m,&h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
journey.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |             scanf("%lld %lld",&t,&cti);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 158 ms 47792 KB Output is correct
8 Correct 368 ms 35404 KB Output is correct
9 Correct 57 ms 8008 KB Output is correct
10 Correct 193 ms 9368 KB Output is correct