제출 #679730

#제출 시각아이디문제언어결과실행 시간메모리
679730DP_196Visiting Singapore (NOI20_visitingsingapore)C++14
22 / 100
215 ms524 KiB
#include <bits/stdc++.h> using namespace std; #define sz(x) (int)x.size() #define MASK(i) ((1LL) << (i)) #define all(x) x.begin(), x.end() #define BIT(x, i) ((x) >> (i) & (1LL)) #define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \ << "] = [" ,DBG(__VA_ARGS__) string to_string(const string& s) { return '"' + s + '"'; } void DBG() { cerr << "]" << endl; } template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); } template <class T> inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); } template <class T> inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); } const int MAXN = 1e5 + 6; const int INF = 1e9; const int MOD = 1e9 + 7; int k, n, m, a, b, v[5005], s[5005], t[5005]; int g[5005][5005], f[105][105], dp[2][5005][2][2]; void sub1() { if (m <= n) return (void) (cout << (v[1] * m)); cout << v[1] * n + (a + (m - n) * b); } void sub2() { int res = m * b; for (int j = 0; j <= m; j++) g[0][j] = j * b; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { g[i][j] = max(g[i - 1][j], g[i][j - 1]) + b; if (s[i] == t[j]) maximize(g[i][j], g[i - 1][j - 1] + v[s[i]]); maximize(res, g[i][j] + (m - j) * b); } cout << res; } void sub6() { int res = a + m * b; for (int j = 0; j <= m; j++) f[0][j] = j * b; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s[i] != t[j]) continue; f[i][j] = v[s[i]] + (j > 1 ? a + (j - 1) * b : 0); for (int x = 1; x < i; x++) for (int y = 1; y < j; y++) if (s[x] == t[y]) maximize(f[i][j], v[s[i]] + f[x][y] + (j - y >= 2 ? a + (j - y - 1) * b : 0) + (i - x >= 2 ? a + (i - x - 1) * b : 0)); maximize(res, f[i][j] + (m != j ? a + (m - j) * b : 0)); } } cout << res; } void subAC() { int res = a + m * b; memset(dp, -0x3f, sizeof (dp)); for (int i = 0; i <= m; i++) { dp[0][i][0][1] = a + m * b; dp[0][i][0][0] = a + m * b; } dp[0][0][0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[1][j][0][0] = max({dp[0][j][0][0] + b, dp[1][j - 1][0][0] + b, dp[0][j - 1][1][1] + 2 * b}); dp[1][j][0][1] = max(dp[0][j][0][1], dp[0][j][1][1]) + b; dp[1][j][1][0] = max(dp[1][j - 1][1][0], dp[1][j - 1][1][1]) + b; if (s[i] == t[j]) { dp[1][j][1][1] = v[s[i]] + (j > 1 ? a + (j - 1) * b : 0); maximize(dp[1][j][1][1], dp[0][j - 1][0][0] + 2 * a + v[s[i]]); maximize(dp[1][j][1][1], dp[0][j - 1][0][1] + a + v[s[i]]); maximize(dp[1][j][1][1], dp[0][j - 1][1][0] + a + v[s[i]]); maximize(dp[1][j][1][1], dp[0][j - 1][1][1] + v[s[i]]); } maximize(res, dp[1][j][1][1] + (m - j >= 1 ? a + (m - j) * b : 0)); } for (int j = 0; j <= m; j++) { swap(dp[0][j][0][0], dp[1][j][0][0]); swap(dp[0][j][0][1], dp[1][j][0][1]); swap(dp[0][j][1][0], dp[1][j][1][0]); swap(dp[0][j][1][1], dp[1][j][1][1]); } } cout << res; } void solve() { 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]; subAC(); } #define TASK "FUNTOUR" int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); int ntest = 1; //cin >> ntest; while (ntest--) solve(); return 0; } //612
#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...