結果
問題 | No.818 Dinner time |
ユーザー |
![]() |
提出日時 | 2019-04-20 01:40:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 60 ms / 2,000 ms |
コード長 | 893 bytes |
コンパイル時間 | 1,662 ms |
コンパイル使用メモリ | 166,608 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-11-29 23:32:50 |
合計ジャッジ時間 | 3,337 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0;i<((int)(n));i++) #define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++) #define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--) #define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--) typedef long long ll; /* dp(i,j) = i番目をj個使う 実はjは0 or 1 or Mに限られる */ ll n,m,a[100010],b[100010],dp[100010][3]; void init(){ cin>>n>>m; reg(i,1,n)cin>>a[i]>>b[i]; } int main(void){ init(); //最初だけは必ず1回以上取らなければいけない。 dp[1][0]=-1e18;//不可能 dp[1][1]=b[1]; dp[1][2]=max({a[1]*m,a[1]*(m-1)+b[1],b[1]}); reg(i,2,n){ dp[i][0]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]}); dp[i][1]=max(dp[i-1][1],dp[i-1][2])+max(a[i],b[i]); dp[i][2]=dp[i-1][2]+max({a[i]*m,a[i]*(m-1)+b[i],b[i]}); } cout<<max({dp[n][0],dp[n][1],dp[n][2]})<<endl; return 0; }