結果
問題 | No.209 Longest Mountain Subsequence |
ユーザー |
|
提出日時 | 2020-02-09 00:43:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 770 bytes |
コンパイル時間 | 2,108 ms |
コンパイル使用メモリ | 194,120 KB |
最終ジャッジ日時 | 2025-01-08 23:15:52 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’: main.cpp:10:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 10 | int n,a[100]; scanf("%d",&n); | ~~~~~^~~~~~~~~ main.cpp:11:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 11 | rep(i,n) scanf("%d",&a[i]); | ~~~~~^~~~~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:40:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 40 | int q; scanf("%d",&q); rep(_,q) solve(); | ~~~~~^~~~~~~~~
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(n);i++)using namespace std;const int INF=1<<29;void solve(){int n,a[100]; scanf("%d",&n);rep(i,n) scanf("%d",&a[i]);int dp[2][100][100];rep(t,2){rep(i,n) rep(j,n) dp[t][i][j]=-INF;rep(i,n) dp[t][i][i]=1;for(int i=1;i<n;i++) rep(j,i) if(a[j]<a[i]) dp[t][j][i]=2;for(int i=2;i<n;i++){rep(j,i) if(a[j]<a[i]) rep(k,j) if(a[k]<a[j] && a[j]-a[k]<a[i]-a[j]) {dp[t][j][i]=max(dp[t][j][i],dp[t][k][j]+1);}}reverse(a,a+n);}int ans=0;rep(i,n){int tmp0=0,tmp1=0;rep(j,n){tmp0=max(tmp0,dp[0][j][i]);tmp1=max(tmp1,dp[1][j][n-i-1]);}ans=max(ans,tmp0+tmp1-1);}printf("%d\n",ans);}int main(){int q; scanf("%d",&q); rep(_,q) solve();return 0;}