Submission #545311

#TimeUsernameProblemLanguageResultExecution timeMemory
545311balbitVisiting Singapore (NOI20_visitingsingapore)C++14
100 / 100
301 ms836 KiB
#include <bits/stdc++.h> #define int ll using namespace std; #define ll long long #define y1 zck_is_king #define pii pair<ll, ll> #define ull unsigned ll #define f first #define s second #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() #define SQ(x) (x)*(x) #define MN(a,b) a = min(a,(__typeof__(a))(b)) #define MX(a,b) a = max(a,(__typeof__(a))(b)) #define pb push_back #define REP(i,n) for (int i = 0; i<n; ++i) #define RREP(i,n) for (int i = n-1; i>=0; --i) #define REP1(i,n) for (int i = 1; i<=n; ++i) #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #ifdef BALBIT #define IOS() #define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__); template<typename T> void _do(T &&x){cerr<<x<<endl;} template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);} #else #define IOS() ios_base::sync_with_stdio(0);cin.tie(0); #define endl '\n' #define bug(...) #endif const int iinf = 1e9+10; const ll inf = 1ll<<60; const ll mod = 1e9+7 ; void GG(){cout<<"0\n"; exit(0);} ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod ll re=1; while (n>0){ if (n&1) re = re*a %mo; a = a*a %mo; n>>=1; } return re; } ll inv (ll b, ll mo = mod){ if (b==1) return b; return (mo-mo/b) * inv(mo%b,mo) % mo; } const int maxn = 5005+5; ll V[maxn], S[maxn], T[maxn]; ll dp[2][2][maxn][2]; signed main(){ IOS(); int K,n,m,A,B; cin>>K>>n>>m>>A>>B; // assert(A == 0 && B == 0); REP1(i,K) cin>>V[i]; REP1(i,n) cin>>S[i]; REP1(i,m) cin>>T[i]; REP(a,2)REP(b,maxn)REP(c,2) { dp[0][a][b][c] = -inf; if (a == 1 && c == 0) dp[0][a][b][c] = A + B * b; } dp[0][1][0][1] = 0; // calculate cost of not even visiting singapore ll re = (A + B*m); REP1(i,n) { int I = i%2; REP(a,2)REP(b,maxn)REP(c,2) dp[I][a][b][c] = -inf; dp[I][1][0][1] = 0; REP1(j, m) { if (T[j] == S[i]) { // take REP(f1, 2) REP(f2, 2) MX(dp[I][1][j][1], V[S[i]] + dp[I^1][f1][j-1][f2]); } // sacrifice S REP(f2, 2) { MX(dp[I][0][j][f2], dp[I^1][1][j][f2] + A+B); MX(dp[I][0][j][f2], dp[I^1][0][j][f2] + 0+B); } // sacrifice T REP(f1, 2) { MX(dp[I][f1][j][0], dp[I][f1][j-1][1] + A + B); MX(dp[I][f1][j][0], dp[I][f1][j-1][0] + 0 + B); } } // extract dp[i][?][m][?] REP(f1,2)REP(f2,2) { MX(re, dp[I][f1][m][f2]); } } cout<<re<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...