結果
問題 | No.484 収穫 |
ユーザー | maroon_kuri |
提出日時 | 2017-03-12 11:37:14 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 41 ms / 3,000 ms |
コード長 | 2,010 bytes |
コンパイル時間 | 1,340 ms |
コンパイル使用メモリ | 163,212 KB |
実行使用メモリ | 66,692 KB |
最終ジャッジ日時 | 2024-10-13 13:15:27 |
合計ジャッジ時間 | 2,565 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 1 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,820 KB |
testcase_08 | AC | 2 ms
6,820 KB |
testcase_09 | AC | 4 ms
9,752 KB |
testcase_10 | AC | 3 ms
9,640 KB |
testcase_11 | AC | 3 ms
9,764 KB |
testcase_12 | AC | 38 ms
66,464 KB |
testcase_13 | AC | 38 ms
66,344 KB |
testcase_14 | AC | 39 ms
66,496 KB |
testcase_15 | AC | 38 ms
66,692 KB |
testcase_16 | AC | 41 ms
66,560 KB |
testcase_17 | AC | 39 ms
66,560 KB |
testcase_18 | AC | 40 ms
66,560 KB |
testcase_19 | AC | 39 ms
66,560 KB |
testcase_20 | AC | 40 ms
66,688 KB |
testcase_21 | AC | 40 ms
66,560 KB |
testcase_22 | AC | 40 ms
66,560 KB |
testcase_23 | AC | 39 ms
66,624 KB |
コンパイルメッセージ
main.cpp: In function ‘ll read()’: main.cpp:38:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 38 | scanf("%lld",&i); | ~~~~~^~~~~~~~~~~ main.cpp: In function ‘std::string readString()’: main.cpp:60:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 60 | scanf("%s",buf); | ~~~~~^~~~~~~~~~ main.cpp: In function ‘char* readCharArray()’: main.cpp:68:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 68 | scanf("%s",ret); | ~~~~~^~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; #define int ll #define FOR(i,a,b) for(int i=int(a);i<int(b);i++) #define REP(i,b) FOR(i,0,b) #define MP make_pair #define PB push_back #define ALL(x) x.begin(),x.end() #define REACH cerr<<"reached line "<<__LINE__<<endl #define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl using pi=pair<int,int>; using vi=vector<int>; using ld=long double; template<class T,class U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os<<"("<<p.first<<","<<p.second<<")"; return os; } template<class T> ostream& operator <<(ostream& os,const vector<T>& v){ os<<"["; REP(i,(int)v.size()){ if(i)os<<","; os<<v[i]; } os<<"]"; return os; } int read(){ int i; scanf("%lld",&i); return i; } void printSpace(){ printf(" "); } void printEoln(){ printf("\n"); } void print(int x,int suc=1){ printf("%lld",x); if(suc==1) printEoln(); if(suc==2) printSpace(); } string readString(){ static char buf[3341919]; scanf("%s",buf); return string(buf); } char* readCharArray(){ static char buf[3341919]; static int bufUsed=0; char* ret=buf+bufUsed; scanf("%s",ret); bufUsed+=strlen(ret)+1; return ret; } template<class T,class U> void chmax(T& a,U b){ if(a<b) a=b; } template<class T,class U> void chmin(T& a,U b){ if(a>b) a=b; } template<class T> T Sq(const T& t){ return t*t; } const int inf=LLONG_MAX/3; const int Nmax=2017; int dp[Nmax][Nmax][2]; signed main(){ int n=read(); vi a; REP(i,n)a.PB(read()); REP(i,n)REP(j,n)dp[i][j][0]=dp[i][j][1]=inf; dp[0][n-1][0]=max(a[0]+n-1,a[n-1]); dp[0][n-1][1]=max(a[0],a[n-1]+n-1); for(int d=n-1;d>=1;d--) REP(l,n-d){ int r=l+d; chmin(dp[l+1][r][0],max(a[l+1]+(r-(l+1)),dp[l][r][0])); chmin(dp[l+1][r][1],max(a[l+1],dp[l][r][0]+(r-(l+1)))); chmin(dp[l][r-1][1],max(a[r-1]+((r-1)-l),dp[l][r][1])); chmin(dp[l][r-1][0],max(a[r-1],dp[l][r][1]+((r-1)-l))); } int ans=inf; REP(i,n) chmin(ans,min(dp[i][i][0],dp[i][i][1])); cout<<ans<<endl; }