Submission #337376

#	Time	Username	Problem	Language	Result	Execution time	Memory
337376		iulia13	Visiting Singapore (NOI20_visitingsingapore)	C++14	100 / 100	333 ms	620 KiB

VisitingSingapore

#include <iostream>

using namespace std;
int v[1005];
int s[5005];
int t[5005];
int dp[2][5005][2][2];
void maxi (int &a, int b)
{
    a = max(a, b);
}
int main()
{
    int k, n, m, a, b, j, i, ans = 0;
    cin >> k >> n >> m >> a >> b;
    ans = a + m * b;
    for (i = 1; i <= k; i++)
        cin >> v[i];
    for (i = 1; i <= n; i++)
        cin >> s[i];
    for (i = 1; i <= m; i++)
        cin >> t[i];
    for (j = 1; j <= m; j++)
        for (int st1 = 0; st1 < 2; st1++)
            for (int st2 = 0; st2 < 2; st2++)
                dp[0][j][st1][st2] = -1e9;
    for (i = 1; i <= n; i++)
    {
        for (int st1 = 0; st1 < 2; st1++)
            for (int st2 = 0; st2 < 2; st2++)
                dp[i % 2][0][st1][st2] = -1e9;
        for (j = 1; j <= m; j++)
            for (int st1 = 0; st1 < 2; st1++)
                for (int st2 = 0; st2 < 2; st2++)
                {
                    if (st1 && st2)
                    {
                        if (s[i] == t[j])
                        {
                            int var = - 2e9;
                            maxi(var, dp[1 - i % 2][j - 1][0][0] + v[s[i]]);
                            maxi(var, dp[1 - i % 2][j - 1][0][1] + v[s[i]]);
                            maxi(var, dp[1 - i % 2][j - 1][1][0] + v[s[i]]);
                            maxi(var, dp[1 - i % 2][j - 1][1][1] + v[s[i]]);
                            if (j == 1)
                                maxi(var, v[s[i]]);
                            else
                                maxi(var, a + b * (j - 1) + v[s[i]]);
                            dp[i % 2][j][st1][st2] = var;
                        }
                        else
                            dp[i % 2][j][st1][st2] = -1e9;
                    }
                    else
                    if (st2)
                        dp[i % 2][j][st1][st2] = max(dp[1 - i % 2][j][0][1] + b, dp[1 - i % 2][j][1][1] + a + b);
                    else
                    if (st1)
                        dp[i % 2][j][st1][st2] = max(dp[i % 2][j - 1][1][0] + b, dp[i % 2][j - 1][1][1] + a + b);
                    else
                        dp[i % 2][j][st1][st2] = max(dp[i % 2][j - 1][0][0] + b, dp[i % 2][j - 1][0][1] + a + b);

                    if (j == m)
                        maxi(ans, dp[i % 2][j][st1][st2]);
                }
    }

    cout << ans;
    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