結果

問題 No.209 Longest Mountain Subsequence
コンテスト
ユーザー evima
提出日時 2015-05-15 22:57:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,826 bytes
コンパイル時間 1,256 ms
コンパイル使用メモリ 161,648 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 04:12:53
合計ジャッジ時間 1,738 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Enjoy your stay.

#include <bits/stdc++.h>

#define long long long
#define LOOPVAR_TYPE long

#define all(x) (x).begin(), (x).end()
#define sz(x) ((LOOPVAR_TYPE)(x).size())
#define foreach(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i, n) _rep2(i, 0, n)
#define _rep2(i, a, b) for(LOOPVAR_TYPE i = (LOOPVAR_TYPE)(a); i < (LOOPVAR_TYPE)(b); i++)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)

#define fir first
#define sec second
#define mp make_pair
#define mt make_tuple
#define pb push_back

const double EPS = 1e-9;
const double PI = acos(-1.0);
const long INF = 1070000000LL;
const long MOD = 1000000007LL;

using namespace std;

typedef istringstream iss;
typedef stringstream sst;
typedef pair<LOOPVAR_TYPE, LOOPVAR_TYPE> pi;
typedef vector<LOOPVAR_TYPE> vi;

int n;
int a[111];
int dp1[111][111];
int dp2[111][111];

int f(int cur, int pre){
	int& res = dp1[cur][pre];
	if(res != -1) return res;
	res = 2;
	rep(nx,cur){
		if(a[nx] < a[cur] && a[nx] > a[cur] - (a[pre] - a[cur])){
			res = max(res, 1 + f(nx, cur));
		}
	}
	return res;
}

int g(int cur, int pre){
	int& res = dp2[cur][pre];
	if(res != -1) return res;
	res = 2;
	rep(nx,cur+1,n){
		if(a[nx] < a[cur] && a[nx] > a[cur] - (a[pre] - a[cur])){
			res = max(res, 1 + f(nx, cur));
		}
	}
	return res;
}

int main2(){
	
	cin>>n;
	rep(i,n)cin>>a[i];
	memset(dp1,-1,sizeof(dp1));
	memset(dp2,-1,sizeof(dp2));
	int ans = 1;
	rep(mid,n){
		int L = 1;
		rep(i,mid) if(a[i] < a[mid]){
			L = max(L, f(i, mid));
		}
		int R = 1;
		rep(i,mid+1,n) if(a[i] < a[mid]){
			R = max(R, g(i, mid));
		}
		ans = max(ans, L+R-1);
	}
	cout<<ans<<endl;
	return 0;
}

int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int T;
	cin>>T;
	rep(i,T)main2();
}
0