結果
問題 | No.1536 仕切り直し |
ユーザー |
|
提出日時 | 2021-06-06 19:07:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 1,455 bytes |
コンパイル時間 | 2,331 ms |
コンパイル使用メモリ | 217,976 KB |
最終ジャッジ日時 | 2025-01-22 04:12:23 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 |
ソースコード
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef unsigned long long ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } const int N=2021; ll dp[N][N]; int re[N][N]; bool chmax(ll &x,ll y){ if(x<=y){ x=y; return true; } return false; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,m; cin >> n >> m; vector<ll> a(n); for(int i=0;i<n;i++){ cin >> a[i]; } a.push_back(0); n++; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ dp[i][j]=-1e18; re[i][j]=-1; } } dp[0][0]=0; for(int i=0;i<n;i++){ for(int j=0;j<=m;j++){ if(dp[i][j]==-1e18)continue; if(j+1<=m){ if(chmax(dp[i][j+1],dp[i][j])){ re[i][j+1]=i; } } if(chmax(dp[i+1][j],dp[i][j]+(ll)(j%2==0?1:-1)*a[i])){ re[i+1][j]=re[i][j]; } } } vector<int> v; // for(int i=0;i<=n;i++){ // for(int j=0;j<=m;j++){ // cout << i << "," << j << endl; // cout << dp[i][j] << " " << re[i][j] << endl; // } // } for(int i=m;i>0;i--){ v.push_back(re[n][i]); n=re[n][i]; } for(int i:v){ cout << i << "\n"; } }