Submission #693256

#TimeUsernameProblemLanguageResultExecution timeMemory
693256true22Visiting Singapore (NOI20_visitingsingapore)C++14
16 / 100
199 ms195868 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; typedef pair<ll, ll> pl; typedef vector<ll> vl; typedef vector<pl> vp; #define nl "\n" #define fr first #define sc second #define pb push_back #define all(x) x.begin(), x.end() #define fur(i, a, b) for(ll i = a; i <= b; ++i) #define ruf(i, a, b) for(ll i = a; i >= b; --i) #define pv(x) for(auto k : x){cout << k << " ";} cout << nl const ll inf = 1e17; ll K, n, m, A, B; vl val, s, t; /* There are K types of events We know the values of each type of event N of them will occur M of them you want to attend (in the given order, you can attend a type of event more than once) if you miss x consecutive normal events, you will lose points if you miss x consecutive special events, you will lose points now, what is the maximum score you can get? */ void solve(){ // a = b = 0; ll dp[n + 1][m + 1]; fur(i, 0, n) fur(j, 0, m) dp[i][j] = -inf; fur(i, 0, n) dp[i][0] = 0; fur(i, 0, m) dp[0][i] = 0; fur(i, 1, n){ fur(j, 1, m){ if (s[i] == t[j]) dp[i][j] = val[t[j]] + dp[i-1][j-1]; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } cout << dp[n][m] << nl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> K >> n >> m >> A >> B; val.resize(K + 1); s.resize(n + 1); t.resize(m + 1); fur(i, 1, K) cin >> val[i]; fur(i, 1, n) cin >> s[i]; fur(i, 1, m) cin >> t[i]; solve(); return 0; }
#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...