Submission #259724

#	Time	Username	Problem	Language	Result	Execution time	Memory
259724		IOrtroiii	Visiting Singapore (NOI20_visitingsingapore)	C++14	100 / 100	805 ms	640 KiB

VisitingSingapore

#include <bits/stdc++.h>

using namespace std;

using dp_type = array<array<int, 2>, 2>;
const int INF = 1e9;
const dp_type WORST = dp_type{array<int, 2>{-INF, -INF}, array<int, 2>{-INF, -INF}};

void mxm(int &x, int y) {
   if (x < y) x = y;
}

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int K, N, M, A, B; cin >> K >> N >> M >> A >> B;
   vector<int> V(K), S(N), T(M);
   for (int i = 0; i < K; ++i) cin >> V[i];
   for (int i = 0; i < N; ++i) cin >> S[i], --S[i];
   for (int i = 0; i < M; ++i) cin >> T[i], --T[i];
   int ans = A + B*M;
   vector<dp_type> dp(M + 1, WORST);
   for (int i = 0; i <= N; ++i) {
      vector<dp_type> ndp(M + 1, WORST);
      for (int j = 0; j <= M; ++j) {
         // start
         if (i < N && j < M && S[i] == T[j]) mxm(ndp[j + 1][1][1], V[S[i]] + (j ? A : 0) + j * B);
         for (int ld = 0; ld < 2; ++ld) {
            for (int le = 0; le < 2; ++le) {
               if (dp[j][ld][le] == -INF) continue;
               mxm(ans, dp[j][ld][le] + (M - j ? A : 0) + (M - j) * B);
               // ignore day
               if (i < N) mxm(ndp[j][0][le], dp[j][ld][le] + B + (ld ? A : 0));
               // ignore event
               if (j < M) mxm(dp[j + 1][ld][0], dp[j][ld][le] + B + (le ? A : 0));
               // take
               if (i < N && j < M && S[i] == T[j]) {
                  mxm(ndp[j + 1][1][1], dp[j][ld][le] + V[S[i]]);
               }
            }
         }
      }
      if (i < N) dp = move(ndp);
   }
   cout << ans << '\n';
   return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 12 / 12
• Subtask 4: 7 / 7
• Subtask 5: 8 / 8
• Subtask 6: 13 / 13
• Subtask 7: 50 / 50