Submission #1308206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308206		athena	Journey (NOI18_journey)	C++20	100 / 100	43 ms	9448 KiB

journey

#include <bits/stdc++.h>
using namespace std;
#define int long long int

int32_t main()
{
   std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 int n,m,h;
 cin>>n>>m>>h;
 vector<vector<pair<int,int>>>adj(n);
 for(int x=0;x<n-1;x++){
 for(int i=0;i<h;i++)
 {
  int j,w;
  cin>>j>>w;
  if(j<=x)continue;
  adj[x].push_back({j,w});//ignore those that fail the condition
 }
}
vector<vector<int>>base(n,vector<int>(m,0));
base[0][0]=1;//to be in the first city spending no nights
vector<int>dep(m);

for(int i=0;i<n-1;i++)
{int x=0;
  for(int t=0;t<m;t++){
  x=min(x+base[i][t],500000001LL);
  dep[t]=x;
}

for(auto [j,k]:adj[i])
{
  if(k>=m)continue;//if min days are way too much
  int maxt=m-k-1;
  for(int t=0;t<=maxt;t++)
  {
    base[j][t+k]=min(base[j][t+k]+dep[t],500000001LL);
  }
}
}

for(int t=0;t<m;t++)
  cout<<min(base[n-1][t],500000001LL)<<" ";
cout<<endl;
  return 0;

}

• Subtask 1: 20 / 20
• Subtask 2: 23 / 23
• Subtask 3: 26 / 26
• Subtask 4: 31 / 31