Submission #1275018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275018		aryan	Visiting Singapore (NOI20_visitingsingapore)	C++20	100 / 100	716 ms	1336 KiB

VisitingSingapore

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

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

int main(){

int tt = 1;
// cin >> tt;
while(tt --){
    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];
    }

    // int dp[m + 5][n + 5][3];
    // vector<vector<vector<int>>> dp(m + 5,vector<vector<int>>(n + 5,vector<int>(3,-inf)));
    /*
        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
    */

    // for(int i = 0;i <= n + 4;i++){
    //     for(int j = 0;j <= m + 4;j++){
    //         for(int x = 0;x <= 2;x++){
    //             dp[i][j][x] = -inf;
    //         }
    //     }
    // }

    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);
                }

                // attend t[i]
                // for(int e : hs[t[j]]){
                //    if(e < i) continue;
                //    int sub = (e - i) * b + ((e > i) ? a : 0);
                //    // tot = max(tot,ndp[e + 1][1] - sub + v[t[j]]); 
                //    // tot = max(tot,ndp2[e + 1][2] - sub + v[t[j]] + (j + 1) * b - a);
                //    // leave at eth day
                //    // tot = max(tot,v[t[j]] - sub - (m - j) * b - ((m > j) ? a : 0));
                // }

                // 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,ndp[e + 1][1] - sub + v[t[j]]);
                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;
                // cout << i << " " << j << " " << x << " : " << tot << '\n'; 
                
            }
            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