結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2022-11-07 14:22:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 974 bytes |
コンパイル時間 | 1,788 ms |
コンパイル使用メモリ | 170,656 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 22:22:11 |
合計ジャッジ時間 | 2,516 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int N=50+10,C=300+10,M=1500+10; inline void cmin(int &x,int y) { if (x>y) x=y; } struct L { int s,t,c,m; bool operator < (const L& a) const { return t<a.t; } } l[M]; int n,v,k,s[M],t[M],c[M],m[M],dp[N][C],ans=0x3f3f3f3f; int main() { scanf("%d%d%d",&n,&v,&k); // for (int i=1;i<=k;++i) // scanf("%d%d%d%d",&l[i].s,&l[i].t,&l[i].c,&l[i].m); for (int i=1;i<=k;++i) scanf("%d",&l[i].s); for (int i=1;i<=k;++i) scanf("%d",&l[i].t); for (int i=1;i<=k;++i) scanf("%d",&l[i].c); for (int i=1;i<=k;++i) scanf("%d",&l[i].m); sort(l+1,l+k+1); memset(dp,0x3f,sizeof(dp)); memset(dp[1],0,sizeof(dp[1])); for (int i=1,x=1;i<=n;++i) { while (x<=k&&l[x].t==i) { for (int j=l[x].c;j<=v;++j) cmin(dp[i][j],dp[l[x].s][j-l[x].c]+l[x].m); ++x; } for (int j=1;j<=v;++j) cmin(dp[i][j],dp[i][j-1]); } for (int i=1;i<=v;++i) cmin(ans,dp[n][i]); if (ans==0x3f3f3f3f) ans=-1; printf("%d\n",ans); return 0; }