Submission #1369846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1369846		moha1111	Nile (IOI24_nile)	C++20	6 / 100	2095 ms	4772 KiB

nile

//#include "nile.h"
#include "bits/stdc++.h"
using namespace std;

std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a , std::vector<int> b, std::vector<int> e) {
  
    long long n = a.size() , q = e.size() , sum = accumulate(a.begin() , a.end() , 0LL);
    vector<int> dif(n + 5);
    vector<pair<int , int>> W;
    for(int i = 0 ; i < n ; i++)
        W.push_back({w[i] , i});

    sort(W.begin() , W.end());
    sort(w.begin() , w.end());
    for(int i = 1 ; i <= n ; i++)
        dif[i] = a[W[i - 1].second] - b[W[i - 1].second];
    
    vector<long long> ans;
    while(q--)
    {
        long long d = e.back();
        e.pop_back();
        vector<long long> dp(n + 5 , 0);
        for(int i = 1 ; i <= n ; i++)
        {
            dp[i] = dp[i - 1];
            for(int j = 1 ; j < i ; j++)
            {
              if(abs(w[i - 1] - w[j - 1]) <= d)
                  dp[i] = max(dp[i] , dp[j - 1] + dif[i] + dif[j]);
            }
        }
        ans.push_back(sum - dp[n]);
    }
    return ans;
}

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