結果
問題 | No.1515 Making Many Multiples |
ユーザー |
![]() |
提出日時 | 2023-04-28 14:32:14 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 1,326 bytes |
コンパイル時間 | 3,105 ms |
コンパイル使用メモリ | 250,344 KB |
実行使用メモリ | 19,200 KB |
最終ジャッジ日時 | 2024-11-17 14:50:21 |
合計ジャッジ時間 | 4,820 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; #define chmax(a,b) a = max(a,b) pair<int,int> calc(int a,int b){ return make_pair(min(a,b),max(a,b)); } int main(){ int n,k,x,y; cin>>n>>k>>x>>y; vector<int> a(n); for(int i = 0;i<n;i++) cin>>a[i]; vector<int> b(n+2); x %= k; y %= k; b[0] = x % k; b[1] = y % k; for(int i = 0;i<n;i++) b[i+2] = a[i] % k; int ans = 0; vector<vector<int>> tmp(n+2,vector<int>(k+1,-1e9)); tmp[0][y] = 0; tmp[1][x] = 0; vector<int> cnt(n+2,0); for(int i = 0;i<n;i++){ int now = b[i+2]; for(int j = 0;j<i+2;j++){ int nxt = b[j]; int need = 2 * k - nxt - now; need %= k; if(tmp[j][need]>=0){ int can = max(tmp[j][need]+1,cnt[j]); chmax(tmp[i+2][nxt],can); chmax(cnt[i+2],can); chmax(cnt[j],can); chmax(tmp[j][need],tmp[j][need]+1); chmax(tmp[j][now],can); ans = max(ans,can); }else{ int can = cnt[j]; chmax(tmp[i+2][nxt],can); chmax(cnt[i+2],can); chmax(tmp[j][now],can); ans = max(ans,can); } } } cout<<ans<<endl; }