Submission #545306

#TimeUsernameProblemLanguageResultExecution timeMemory
545306balbitVisiting Singapore (NOI20_visitingsingapore)C++14
12 / 100
121 ms480 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][maxn]; 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]; // dp[0][1][0][1] = 0;- // calculate cost of not even visiting singapore // ll re = (A + B*m); ll re = 0; REP1(i,n) { int I = i%2; REP1(j,m) { dp[I][j] = -inf; dp[I][j] = max(dp[I^1][j], dp[I][j-1]); if (S[i] == T[j]) { MX(dp[I][j], dp[I^1][j-1] + V[S[i]]); } MX(re, dp[I][j]); } } 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...