Submission #682783

#TimeUsernameProblemLanguageResultExecution timeMemory
682783Paul_Liao_1457Collecting Stamps 3 (JOI20_ho_t3)C++17
15 / 100
60 ms63612 KiB
//記得跳題 #include<iostream> #include<array> #include<vector> #include<string> #include<algorithm> #include<set> #include<queue> #include<stack> #include<math.h> #include<map> #include<unordered_map> #include<cstring> #include<iomanip> #include<bitset> #include<tuple> #define ll long long #define LL __int128_t #define DB double #define FOR(i,a,b) for(int i=a;i<b;i++) #define REP(i,a,b) for(int i=a;i>=b;i--) #define pb push_back #define mp make_pair #define INF (ll)(2e9) #define MOD (ll)(1e9+7) #define F first #define S second #define endl "\n" #define AC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; template<class T> using PQ=priority_queue<T,vector<T>,less<T> >; void file(){ freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin); freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout); } /*int s[200005],seg[800005]; void build(int id,int l,int r){ if(l==r){ seg[id]=s[l]; return; } int mid=(l+r)>>1; build(id*2,l,mid); build(id*2+1,mid+1,r); seg[id]=max(seg[id*2],seg[id*2+1]); } int ask(int id,int l,int r,int L,int R){ if(l>R||r<L) return 0; if(L<=l&&r<=R) return seg[id]; int mid=(l+r)>>1; return max(ask(id*2,l,mid,L,R),ask(id*2+1,mid+1,r,L,R)); } */ int dp[201][201][2][201],x[201],y[201],t[201]; signed main(){ AC; int n,l; cin>>n>>l; FOR(i,1,n+1){ cin>>x[i]; y[n-i+1]=l-x[i]; } FOR(i,1,n+1) cin>>t[i]; FOR(i,0,n+1)FOR(j,0,n+1)FOR(k,0,2)FOR(s,0,i+j+1) dp[i][j][k][s]=INF; dp[0][0][0][0]=dp[0][0][1][0]=0; int ans=0; FOR(i,0,n+1)FOR(j,0,n+1){ if(i+j>n) break; FOR(k,0,2)FOR(s,0,min(n,i+j)+1)if(dp[i][j][k][s]!=INF){ //cout<<"dp["<<i<<"]["<<j<<"]["<<k<<"]["<<s<<"]="<<dp[i][j][k][s]<<endl; ans=max(ans,s); if(k==0){ if(dp[i][j][k][s]+x[i+1]-x[i]<=t[i+1]){ dp[i+1][j][k][s+1]=min(dp[i+1][j][k][s+1],dp[i][j][k][s]+x[i+1]-x[i]); } else{ dp[i+1][j][k][s]=min(dp[i+1][j][k][s],dp[i][j][k][s]+x[i+1]-x[i]); } if(dp[i][j][k][s]+y[j+1]+x[i]<=t[n-j]){ dp[i][j+1][k^1][s+1]=min(dp[i][j+1][k^1][s+1],dp[i][j][k][s]+y[j+1]+x[i]); } else{ dp[i][j+1][k^1][s]=min(dp[i][j+1][k^1][s],dp[i][j][k][s]+y[j+1]+x[i]); } } else{ if(dp[i][j][k][s]+x[i+1]+y[j]<=t[i+1]){ dp[i+1][j][k^1][s+1]=min(dp[i+1][j][k^1][s+1],dp[i][j][k][s]+x[i+1]+y[j]); } else{ dp[i+1][j][k^1][s]=min(dp[i+1][j][k^1][s],dp[i][j][k][s]+x[i+1]+y[j]); } if(dp[i][j][k][s]+y[j+1]-y[j]<=t[n-j]){ dp[i][j+1][k][s+1]=min(dp[i][j+1][k][s+1],dp[i][j][k][s]+y[j+1]-y[j]); } else{ dp[i][j+1][k][s]=min(dp[i][j+1][k][s],dp[i][j][k][s]+y[j+1]-y[j]); } } } } cout<<ans<<endl; } /* */

Compilation message (stderr)

ho_t3.cpp: In function 'void file()':
ho_t3.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...