Submission #1317349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317349		spetr	나일강 (IOI24_nile)	C++20	67 / 100	2094 ms	9856 KiB

nile

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>



std::vector<long long> calculate_costs(
    std::vector<int> W, std::vector<int> A, 
    std::vector<int> B, std::vector<int> E){

    ll n = W.size();
    vll nums;
    for (ll i = 0; i < n; i++){
        nums.push_back({W[i], A[i], B[i]});
    }
    sort(nums.begin(), nums.end());
    vl ans;
    for (ll i = 0; i < E.size(); i++){
        ll k = E[i];
        vl dp (n+5, 1e18); dp[0] = 0;
        for (ll j = 0; j < n; j++){
            if (j < n){
                dp[j+1] = min(dp[j] + nums[j][1], dp[j+1]);
            }
            if (j+1 < n){
                if (nums[j+1][0] - nums[j][0] <= k){
                    dp[j+2] = min(dp[j] + nums[j][2] + nums[j+1][2], dp[j+2]);
                }
            }

            if (j+2 < n){
                if (nums[j+2][0] - nums[j][0] <= k){
                    dp[j+3] = min(dp[j] + nums[j][2] + nums[j+2][2] + nums[j+1][1], dp[j+3]);
                }
            }
        }
        ans.push_back(dp[n]);
    }
    return ans;
}

/*/int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> W, A, B, E;
    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++){
        ll a,b,c;
        cin >>a >> b >> c;
        W.push_back(a);
        A.push_back(b);
        B.push_back(c);
    }
    ll q;
    cin >> q;
    for (ll i = 0; i < q; i++){
        ll a;
        cin >> a;
        E.push_back(a);
    }

    
    vl x = calculate_costs(W, A, B, E);
    for (auto p : x){
        cout << p << "\n";
}   
    return 0;
}
/*/

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18