Submission #1242040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242040		mychecksedad	Nile (IOI24_nile)	C++20	0 / 100	70 ms	7348 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long int
const int N = 1e5+100;

int _n;
ll T[N*2];
void build(int n){
  n = _n;
  for(int j = 0; j <= 2*n+2; ++j) T[j] = 1e18;
}
void upd(int p, ll val){
  ++p;
  T[p += _n] = val;
  for(p >>= 1; p; p >>= 1) T[p] = min(T[p<<1], T[p<<1|1]);
}
ll get(int l, int r){
  if(l > r) return 1e18;
  ll res = 1e18;
  ++l, ++r;
  l += _n;
  r += _n + 1;
  for(; l < r; l >>= 1, r >>= 1){
    if(l&1) res = min(res, T[l++]);
    if(r&1) res = min(res, T[--r]);
  }
  return res;
}

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  int q = (int) E.size();
  int n = (int) W.size();
  build(n);
  vector<array<ll, 3>> C;
  for(int i = 0; i < n; ++i) C.pb({W[i], A[i], B[i]});
  sort(all(C)); 
  
  vector<ll> pref(n);
  pref[0] = C[0][1];
  for(int i = 1; i < n; ++i) pref[i] = pref[i - 1] + C[i][1];

  function<ll(int, int)> get2 = [&](int l, int r){
    return pref[r] - (l <= 0 ? 0 : pref[l - 1]);
  };

  vector<ll> res;
  for(ll D: E){
    vector<ll> DP(n);
    DP[0] = C[0][1];
    build(n);
    upd(0, C[0][2]-pref[0]);
    for(int i = 1; i < n; ++i){
      int j = lower_bound(all(C), array<ll,3>{C[i][0]-D, -1ll, -1ll}) - C.begin();
      DP[i] = min(DP[i - 1] + C[i][1], pref[i-1] + get(j, i-1) + C[i][2]);
      upd(i, DP[i-1] - pref[i] + C[i][2]);
    }
    res.pb(DP.back());
  }

  return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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