結果

問題 No.484 収穫
ユーザー legendcn
提出日時 2025-01-28 23:59:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,532 ms / 3,000 ms
コード長 1,400 bytes
コンパイル時間 1,628 ms
コンパイル使用メモリ 160,492 KB
実行使用メモリ 74,496 KB
最終ジャッジ日時 2025-01-28 23:59:46
合計ジャッジ時間 20,156 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:40:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |         scanf ("%lld", &n);
      |         ~~~~~~^~~~~~~~~~~~
main.cpp:42:46: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   42 |         for (int i = 1; i <= n; i ++ ) scanf ("%lld", &a[i]), mx = max (mx, a[i]);
      |                                        ~~~~~~^~~~~~~~~~~~~~~

ソースコード

diff # 

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 2005;

int n;
int a[N];
int f[N][N][2];
bool vis[N][N][2];
int dfs (int l, int r, int x, int mid)
{
	if (vis[l][r][x]) return f[l][r][x];
	vis[l][r][x] = 1;
	if (l == r) return f[l][r][x] = mid; 
	if (!x)
	{
	    int t = dfs (l + 1, r, 0, mid);
	    if (a[l] < t) f[l][r][x] = max (f[l][r][x], t - 1);
	    t = dfs (l, r - 1, 1, mid);
	    if (a[r] < t) f[l][r][x] = max (f[l][r][x], t - (r - l + 1));
	}
	else
	{
		int t = dfs (l + 1, r, 0, mid);
	    if (a[l] < t) f[l][r][x] = max (f[l][r][x], t - (r - l + 1));
	    t = dfs (l, r - 1, 1, mid);
	    if (a[r] < t) f[l][r][x] = max (f[l][r][x], t - 1);
	}
	return f[l][r][x];
}
signed main ()
{
//	freopen ("apple.in", "r", stdin);
//	freopen ("apple.out", "w", stdout);
	scanf ("%lld", &n);	
	int mx = 0;
	for (int i = 1; i <= n; i ++ ) scanf ("%lld", &a[i]), mx = max (mx, a[i]);
	int l = mx, r = 2e9, ans = 0;
	while (l <= r)
	{
		int mid = l + r >> 1;
		for (int i = 1; i <= n; i ++ )
		{
			for (int j = 1; j <= n; j ++ )
			{
				for (int k = 0; k <= 1; k ++ )
					f[i][j][k] = -1e18, vis[i][j][k] = 0;
			}
		}
		if (dfs (1, n, 0, mid) >= 0 || dfs (1, n, 1, mid) >= 0) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	printf ("%lld\n", ans);
	return 0;
}
0