Submission #1172626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172626		_ncng.nyr	Nile (IOI24_nile)	C++20	67 / 100	2099 ms	8880 KiB

nile

#include<bits/stdc++.h>

#define tp tuple<int, int, int>

using namespace std;

const int N = 2e5 + 5;
const long long oo = 1e16;

int n, Q, chk1 = 1, chk2 = 1, chk3 = 1;
long long a[N], b[N], w[N], e[N];

namespace sub1 {
  vector<long long> solve() {
    vector<long long> ans;

    for(int i = 1; i <= Q; ++i) {
      int D = e[i];
      long long res = 0;
      for(int i = 1; i <= n; ++i) res += b[i];

      if(n & 1) {
        long long sub = oo;
        for(int i = 1; i <= n; ++i) sub = min(sub, a[i] - b[i]);
        res += sub;
      }

      ans.push_back(res);
    }

    return ans;
  }
}

namespace sub2 {
  long long pref[N];
  vector<long long> solve() {
    vector<long long> ans;
    for(int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + b[i];

    for(int i = 1; i <= Q; ++i) {
      int D = e[i];
      long long res = oo;

      if(n & 1) {
        if(D > 1) for(int j = 1; j <= n; ++j) res = min(res, pref[n] + a[j] - b[j]);
        else {
          for(int j = 1; j <= n; ++j)
            if(j & 1) res = min(res, pref[n] + a[j] - b[j]);
        }
      }

      else res = pref[n];
      ans.push_back(res);
    }

    return ans;
  }
}

namespace sub3 {
  tp item[N];

  vector<long long> solve() {
    vector<long long> ans;

    for(int i = 1; i <= n; ++i) item[i] = {w[i], a[i], b[i]};
    sort(item + 1, item + n + 1);

    for(int idx = 1; idx <= Q; ++idx) {
      int D = e[idx];
      vector<long long> f(n + 1);
      f[1] = 2;

      for(int i = 2; i <= n; ++i) {
        auto [nw, na, nb] = item[i - 1];
        auto [w, a, b] = item[i];
        f[i] = f[i - 1] + 2;
        if(w - nw <= D) f[i] = min(f[i], f[i - 2] + 2);
      }

      ans.push_back(f[n]);
    }

    return ans;
  }
}

namespace sub5 {
  tp item[N];

  vector<long long> solve() {
    vector<long long> ans;

    for(int i = 1; i <= n; ++i) item[i] = {w[i], a[i], b[i]};
    sort(item + 1, item + n + 1);

    vector<long long> pref(n + 1);
    for(int i = 1; i <= n; ++i) {
      auto [w, a, b] = item[i];
      pref[i] = pref[i - 1] + a;
    }

    for(int idx = 1; idx <= Q; ++idx) {
      int D = e[idx];
      vector<long long> f(n + 1);
      deque<int> q;

      for(int i = 1, j = 1; i <= n; ++i) {
        auto [w, a, b] = item[i];
        f[i] = f[i - 1] + a;

        while(j < i && w - get<0> (item[j]) > D) ++j;
        while(q.size() && q.front() < j) q.pop_front();
        if(q.size()) {
          auto [nw, na, nb] = item[q.front()];
          f[i] = min(f[i], f[q.front() - 1] + b + pref[i - 1] + nb - pref[q.front()]);
        }

        while(q.size() &&
              f[i - 1] + b - pref[i] <= f[q.back() - 1] + get<2> (item[q.back()]) - pref[q.back()])
          q.pop_back();

        q.push_back(i);
      }

      ans.push_back(f[n]);
    }

    return ans;
  }
}

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

  n = W.size(); Q = E.size();

  for(int i = 1; i <= n; ++i) {
    w[i] = W[i - 1], a[i] = A[i - 1], b[i] = B[i - 1];
    if(w[i] != 1) chk1 = 0;
    if(w[i] != i) chk2 = 0;
    if(a[i] != 2 || b[i] != 1) chk3 = 0;
  }

  for(int i = 1; i <= Q; ++i) e[i] = E[i - 1];

  if(chk1) return sub1 :: solve();
  if(chk2) return sub2 :: solve();
  if(chk3) return sub3 :: solve();
  if(n <= 2'000 && Q <= 5) return sub5 :: solve();
}

//#define ntc
#ifdef ntc
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if(fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if(fopen("NILE.inp", "r")) {
    freopen("NILE.inp", "r", stdin);
    freopen("NILE.out", "w", stdout);
  }

  vector<int> W, A, B, E;

  cin >> n;
  for(int i = 1; i <= n; ++i) {
    int w, a, b; cin >> w >> a >> b;
    W.push_back(w); A.push_back(a); B.push_back(b);
  }

  cin >> Q;
  for(int i = 1; i <= Q; ++i) {
    int D; cin >> D;
    E.push_back(D);
  }

  vector<long long> ans = calculate_costs(W, A, B, E);
  for(auto x : ans) cout << x << '\n';
}
#endif

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:153:1: warning: control reaches end of non-void function [-Wreturn-type]
  153 | }
      | ^

• 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