제출 #1274232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274232		aryan	Visiting Singapore (NOI20_visitingsingapore)	C++17	42 / 100	208 ms	196532 KiB

VisitingSingapore

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

using i64 = long long;
const i64 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<i64>> dp(m + 5,vector<i64>(n + 2,-inf));
    // dp[m + 1][0] = 0;
    vector<i64> mi(n + 1,-inf);
    /* dp[i][j] = max value if currently at i(on t) and prev was j (on s) and taking it
    
    */

    for(int i = m;i >= 1;i--){
        vector<int> nx(k + 1,n + 1);
        for(int j = 0;j <= n;j++){
            // if(dp[i + 2][j] == -inf) continue;
            mi[j] = max(mi[j],dp[i + 2][j] - (i + 2) * b);
        }
        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
            //     continue;
            // }
            int next = nx[t[i]];
            if(next > n){
                nx[s[j]] = j;
                continue;
            }
            // next = hs[t[i]][next];
            int sub = (next - j - 1) * b + ((next - j - 1) > 0 ? a : 0); // s subraction

            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;
            
            // leave today
            dp[i][j] = max(dp[i][j],(i64) v[t[i]] - sub - ((m - i) * b + ((m - i) > 0 ? a : 0)));
            nx[s[j]] = j;
        }
    }

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

    return 0;
}

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