結果
問題 | No.818 Dinner time |
ユーザー |
![]() |
提出日時 | 2019-04-19 23:23:24 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 1,292 bytes |
コンパイル時間 | 1,325 ms |
コンパイル使用メモリ | 159,184 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2024-11-29 23:31:45 |
合計ジャッジ時間 | 3,335 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll n,m;cin>>n>>m; ll a[n+1],b[n+1];for(ll i=1;i<=n;i++)cin>>a[i]>>b[i]; a[0]=0;b[0]=0; ll dp[n+1][2]; for(ll i=0;i<n+1;i++){ dp[i][0]=-1000000000000000000; dp[i][1]=-1000000000000000000; } dp[0][0]=0;dp[0][1]=0; ll ans; if(a[1]<0&&b[1]<0){ ans=max(b[1],a[1]*m); dp[1][0]=max(b[1],a[1]*m); dp[1][1]=b[1]; } else{ if(b[1]>=0){ ans=max(a[1],b[1])+max(a[1]*(m-1),(ll)0); dp[1][0]=max(a[1]*(m-1),(ll)0)+max(a[1],b[1]); dp[1][1]=b[1]; } else{ ans=a[1]*m; dp[1][0]=a[1]*m; dp[1][1]=b[1]; } } for(ll i=2;i<=n;i++){ if(a[i]<0&&b[i]<0){ dp[i][1]=max(dp[i][1],max(dp[i-1][0],dp[i-1][1])+max(a[i],b[i])); dp[i][0]=max(dp[i][0],dp[i-1][0]+max(b[i],a[i]*m)); } else{ dp[i][1]=max(dp[i][1],max(dp[i-1][0],dp[i-1][1])+max(a[i],b[i])); if(b[i]>=0){ dp[i][0]=max(dp[i][0],dp[i-1][0]+max(a[i],b[i])+max(a[i]*(m-1),(ll)0)); } else{ dp[i][0]=max(dp[i][0],dp[i-1][0]+a[i]*m); } } ans=max(ans,max(dp[i][0],dp[i][1])); } cout<<ans<<endl; }