Submission #691597

#TimeUsernameProblemLanguageResultExecution timeMemory
691597penguin133Visiting Singapore (NOI20_visitingsingapore)C++17
0 / 100
101 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif int S[5005], T[5005], V[5005], memo[5005][5005][2][2], n, m, k, a, b; int dp(int x, int y, bool f, bool f2){ if(y == m + 1)return 0; if(x == n + 1)return b * (m - y + 1) + (!f2 ? a : 0); if(memo[x][y][f][f2] != -1)return memo[x][y][f][f2]; int res = max(dp(x+1, y, 1, f2) + b + (!f ? a : 0), dp(x, y+1, f, 1) + b + (!f2 ? a : 0)); if(S[x] == T[y])res = max(res, dp(x+1, y+1, 0, 0) + V[S[x]]); return memo[x][y][f][f2] = 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]; memset(memo, -1, sizeof(memo)); int res = -1e18; for(int i=1;i<=n;i++)res = max(res, dp(i, 1, 0, 0)); cout << res; } main(){ ios::sync_with_stdio(0);cin.tie(0); int tc = 1; //cin >> tc; for(int tc1=1;tc1<=tc;tc1++){ // cout << "Case #" << tc1 << ": "; solve(); } }

Compilation message (stderr)

VisitingSingapore.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | 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...