Submission #1274149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274149		aryan	Visiting Singapore (NOI20_visitingsingapore)	C++20	10 / 100	248 ms	98500 KiB

VisitingSingapore

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
const int inf = 1e9;

int main(){

    int k,n,m,a,b;
    cin >> k >> n >> m >> a >> b;
    a *= -1;
    b *= -1;
    vector<int> v(k + 1);
    for(int i = 1;i <= k;i++){
        cin >> v[i];
    }
    vector<int> s(n + 1);
    vector<vector<int>> hs(k + 1);
    for(int i = 1;i <= n;i++){
        cin >> s[i];
        hs[s[i]].push_back(i);
    }
    vector<int> t(m + 1);
    for(int i = 1;i <= m;i++){
        cin >> t[i];
    }

    vector<vector<int>> dp(m + 2,vector<int>(n + 2,-inf));
    /* dp[i][j] = max value if currently at i(on t) and prev was j (on s) and taking it
    
    */
    vector<int> mi(n + 1,-inf);
    for(int i = m;i >= 1;i--){
        for(int j = n;j >= 0;j--){
            int next = upper_bound(hs[t[i]].begin(),hs[t[i]].end(),j) - hs[t[i]].begin();
            if(next == (int) hs[t[i]].size()){
                // not possible
                mi[j] = max(mi[j],dp[i + 1][j] - (i + 1) * b);
                continue;
            }
            next = hs[t[i]][next];
            int sub = (next - j - 1) * b + ((next - j - 1) > 0 ? a : 0); // s subraction
            // if(j == 0) sub = 0;
            // for(int p = i + 2;p <= m;p++){
            //     dp[i][j] = max(dp[i][j],dp[p][next] - (p - i - 1) * b - a); // t subtraction
            // }
            dp[i][j] = max(dp[i][j],mi[next] + (i + 1) * b - a);
            dp[i][j] = max(dp[i][j],dp[i + 1][next]);
            dp[i][j] += v[t[i]];
            dp[i][j] -= sub;
            mi[j] = max(mi[j],dp[i + 1][j] - (i + 1) * b);
            // leave today
            dp[i][j] = max(dp[i][j],v[t[i]] - sub - ((m - i) * b + ((m - i) > 0 ? a : 0)));
        }
    }

    int ans = -inf;
    for(int i = 1;i <= m;i++){
        for(int j = 0;j <= n;j++){
            ans = max(ans,dp[i][j] - (i - 1) * b - ((i > 1) ? a : 0));
            // cout << dp[i][j] - (i - 1) * b - ((i > 1) ? a : 0) << " ";
        }
        // cout << '\n';
    }
    cout << ans << '\n';

    return 0;
}

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