oj.uz

Submission #586420

# Submission time Handle Problem Language Result Execution time Memory
586420 2022-06-30T08:38:23 Z krit3379 Journey (NOI18_journey) C++17
100 / 100
 146 ms 6456 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 10005

int dp[405][N];
vector<pair<int,int>> g[N];

int main(){
    int n,m,h,i,j,a,w;
    scanf("%d %d %d",&n,&m,&h);
    for(i=0;i<n-1;i++){
        for(j=0;j<h;j++){
            scanf("%d %d",&a,&w);
            if(a<=i)continue;
            g[i].push_back({a,w});
        }
    }
    dp[0][0]=1;
    for(j=0;j<m;j++){
        for(i=0;i<n-1;i++){
            dp[j+1][i]=min(dp[j+1][i]+dp[j][i],500000001);
            for(auto [x,w]:g[i])if(j+w<m)dp[j+w][x]=min(dp[j+w][x]+dp[j][i],500000001);
        }
    }
    for(i=0;i<m;i++)printf("%d ",dp[i][n-1]);
    return 0;
}

Compilation message

journey.cpp: In function 'int main()':
journey.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d %d %d",&n,&m,&h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
journey.cpp:15:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |             scanf("%d %d",&a,&w);
      |             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 61 ms 3852 KB Output is correct
8 Correct 93 ms 6456 KB Output is correct
9 Correct 27 ms 3528 KB Output is correct
10 Correct 146 ms 4728 KB Output is correct