Submission #1274478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274478		aryan	Visiting Singapore (NOI20_visitingsingapore)	C++20	13 / 100	2096 ms	1268 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),s(n + 1),t(m + 1);
    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--){
        for(int i = n;i >= 1;i--){
            for(int x = 0;x <= 2;x++){
                int tot = -inf;

                // attend t[i]
                for(int e : hs[t[j]]){
                   if(e < i) continue;
                   // taking eth day
                   // int sub = (e - i) * b + ((e > i) ? a : 0);
                   // tot = max(tot,dp[j + 1][e + 1][1] - sub + v[t[j]]);  
                   // tot = max(tot,dp[j + 2][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));

                   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));
                }
                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: 0 / 4
• Subtask 2: 0 / 6
• Subtask 3: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 13 / 13
• Subtask 7: 0 / 50