Submission #1230585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230585		kilikuma	Nile (IOI24_nile)	C++20	67 / 100	2096 ms	5704 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std; 

vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
  int n = w.size(); 
  vector<pair<int, int>> arti(n, {0ll, 0ll});
  long long sum = 0; 
  for (int i = 0; i < n; i ++) {
    arti[i] = {w[i], a[i] - b[i]};
    sum += a[i];  
  }
  sort(arti.begin(), arti.end()); 
  int q = e.size(); 
  vector<long long> ans(q, 0); 
  for (int i = 0; i < q; i ++) {
    vector<long long> dp(n + 1, 0ll); 
    dp[n] = 0ll; 
    for (int j = n - 1; j >= 0; j --) {
      dp[j] = dp[j + 1]; 
      for (int k = j + 1; k < n; k ++) {
        if (k - j > 2) 
          break; 
        if (arti[k].first - arti[j].first <= e[i]) 
          dp[j] = max(dp[j], dp[k + 1] + arti[k].second + arti[j].second); 
      }
    }
    ans[i] = sum - dp[0]; 
  }
  return ans; 
}

• 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