Submission #1214735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214735		Gray	Nile (IOI24_nile)	C++20	67 / 100	2095 ms	7632 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;

const ll INF=2e18;

vector<long long> calculate_costs(vector<int> W, vector<int> A,
                                       vector<int> B, vector<int> E) {
  int q = (int)E.size(); int n = W.size();
  vector<ll> res(q);
  for (ll i=0; i<q; i++){
      vector<array<ll, 3>> a(n+1);
      for (ll j=1; j<=n; j++) a[j] = {W[j-1], A[j-1], B[j-1]};
      sort(a.begin(), a.end()); a[0] = {0, INF, INF};
      vector<ll> dp(n+1);
      for (ll j=1; j<=n; j++){
          dp[j] = dp[j-1]+a[j][1];
          if (j-2>=0 and a[j][0]-a[j-1][0]<=E[i]) dp[j] = min(dp[j], dp[j-2]+a[j][2]+a[j-1][2]);
          if (j-3>=0 and a[j][0]-a[j-2][0]<=E[i]) dp[j] = min(dp[j], dp[j-3]+a[j][2]+a[j-2][2]+a[j-1][1]);
      }
      res[i] = dp[n];
  }
  return res;
}

• 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