제출 #1275020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275020		aryan	Visiting Singapore (NOI20_visitingsingapore)	C++20	100 / 100	705 ms	1504 KiB

VisitingSingapore

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

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

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    /*
        dp[i][j][x] -> max happiness if start at day i and at index j(on t)
        x = 0 -> no behind in t
        x = 1 -> just behind in t
        x = 2 -> far behind in t
    */


    vector<vector<int>> dp(n + 4,vector<int>(3,-inf));
    vector<vector<int>> ndp(n + 4,vector<int>(3,-inf));
    vector<vector<int>> ndp2(n + 4,vector<int>(3,-inf));

    int ans = -m * b - a;
    for(int j = m;j >= 1;j--){
        int hs2 = -1;
        int nx1 = -inf;
        int nx2 = -inf;
        for(int i = n;i >= 1;i--){
            for(int x = 0;x <= 2;x++){
                int tot = -inf;

                if(s[i] == t[j]) hs2 = i;
                if(s[i + 1] == t[j]){
                    nx1 = max(nx1,ndp[i + 2][1] - (i + 1) * b);
                }
                if(s[i + 1] == t[j]){
                    nx2 = max(nx2,ndp2[i + 2][2] - (i + 1) * b);
                }

                // leave at eth day
                if(hs2 != -1){
                    int sub = (hs2 - i) * b + ((hs2 > i) ? a : 0);
                    tot = max(tot,v[t[j]] - sub - (m - j) * b - ((m > j) ? a : 0));
                }    

                tot = max(tot,nx1 + i * b + v[t[j]] - a);
                if(s[i] == t[j]){
                    tot = max(tot,ndp[i + 1][1] + v[t[j]]);
                }

                tot = max(tot,nx2 + i * b + v[t[j]] - a + (j + 1) * b - a);
                if(s[i] == t[j]){
                    tot = max(tot,ndp2[i + 1][2] + v[t[j]] + (j + 1) * b - a);
                }

                if(x == 2){
                    tot -= j * b;
                }
                
                // skip t[j]
                if(x == 2) tot = max(tot,ndp[i][2]);
                    
                dp[i][x] = tot;
                
            }
            ans = max(ans,dp[i][0] - (j - 1) * b - ((j > 1) ? a : 0));
           
        }
        ndp2 = ndp;
        ndp = dp;
    }

    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