Submission #490883

#TimeUsernameProblemLanguageResultExecution timeMemory
490883KienTranVisiting Singapore (NOI20_visitingsingapore)C++14
23 / 100
225 ms262148 KiB
#include <bits/stdc++.h> using namespace std; const int O = 5e3 + 5; const int inf = 1e9; int k, n, m, a, b, v[O], s[O], t[O], f[2][O][O], dp[O][O]; main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> k >> n >> m >> a >> b; for (int i = 1; i <= k; ++ i) cin >> v[i]; for (int i = 1; i <= n; ++ i) cin >> s[i]; for (int i = 1; i <= m; ++ i) cin >> t[i]; for (int i = 0; i <= n; ++ i){ for (int j = 1; j <= m; ++ j){ f[0][i][j] = -inf; f[1][i][j] = -inf; } } for (int j = 0; j <= m; ++ j) dp[0][j] = b * j; f[0][0][0] = f[1][0][0] = 0; for (int i = 1; i <= n; ++ i){ for (int j = 1; j <= m; ++ j){ f[0][i][j] = max(f[0][i - 1][j] + b, f[1][i - 1][j] + a + b); if (s[i] == t[j]) f[1][i][j] = max({dp[i - 1][j - 1] + a, f[0][i - 1][j - 1], f[1][i - 1][j - 1]}) + v[s[i]]; } for (int j = 1; j <= m; ++ j) dp[i][j] = max({dp[i][j - 1], f[1][i][j - 1], f[0][i][j - 1]}) + b; } int res = a + b * m; for (int i = 0; i <= n; ++ i){ for (int j = 0; j <= m; ++ j){ int cost = max(f[0][i][j], f[1][i][j]) + a + b * (m - j); if (j == m) cost -= a; res = max(res, cost); } } cout << res; }

Compilation message (stderr)

VisitingSingapore.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main(){
      | ^~~~
#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...