제출 #1274469

#제출 시각아이디문제언어결과실행 시간메모리
1274469aryanVisiting Singapore (NOI20_visitingsingapore)C++17
0 / 100
2096 ms327680 KiB

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

    int ans = -m * b - a;
    for(int i = n;i >= 1;i--){
        for(int j = m;j >= 1;j--){
            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[e + 1][j + 1][1] - sub + v[t[j]]);  
                   tot = max(tot,dp[e + 1][j + 2][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[i]
                if(x == 2) tot = max(tot,dp[i][j + 1][2]);
                
                dp[i][j][x] = tot;
                // cout << i << " " << j << " " << x << " : " << tot << '\n'; 
            }
            ans = max(ans,dp[i][j][0] - (j - 1) * b - ((j > 1) ? a : 0));
        }
    }

    cout << ans << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...