Submission #832901

#TimeUsernameProblemLanguageResultExecution timeMemory
832901NK_Visiting Singapore (NOI20_visitingsingapore)C++17
100 / 100
533 ms588 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define pf push_front #define mp make_pair #define f first #define s second #define sz(x) int(x.size()) template<class T> using V = vector<T>; using pi = pair<int, int>; using vi = V<int>; using vpi = V<pi>; using ll = long long; using pl = pair<ll, ll>; using vpl = V<pl>; using vl = V<ll>; using db = long double; template<class T> using pq = priority_queue<T, V<T>, greater<T>>; const int MOD = 1e9 + 7; const ll INFL = ll(1e17); int main() { cin.tie(0)->sync_with_stdio(0); int K, N, M, A, B; cin >> K >> N >> M >> A >> B; vi H(K); for(auto& x : H) cin >> x; vi S(N); for(auto& x : S) { cin >> x; --x; } vi T(M); for(auto& x : T) { cin >> x; --x; } int dp[2][M+1][2], ndp[2][M+1][2]; memset(dp, 0xc0, sizeof(dp)); memset(ndp, 0xc0, sizeof(ndp)); int ans = -MOD; for(int x = 0; x <= N; x++) { // can start on any day dp[1][0][1] = 0; for(int y = 0; y <= M; y++) for(int ys = 0; ys <= 1; ys++) for(int xs = 0; xs <= 1; xs++) { if (y == M) ans = max(dp[xs][y][ys], ans); // go to event if (x < N && y < M && S[x] == T[y]) ndp[1][y+1][1] = max(dp[xs][y][ys] + H[T[y]], ndp[1][y+1][1]); // skip next event in S (x) if (x < N) ndp[0][y][ys] = max(dp[xs][y][ys] + B + xs * A, ndp[0][y][ys]); // skip next event in T (y) if (y < M) dp[xs][y+1][0] = max(dp[xs][y][ys] + B + ys * A, dp[xs][y+1][0]); } for(int y = 0; y <= M; y++) for(int ys = 0; ys <= 1; ys++) for(int xs = 0; xs <= 1; xs++) { swap(dp[ys][y][xs], ndp[ys][y][xs]); ndp[ys][y][xs] = -MOD; } } cout << ans << nl; 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...