#include "nile.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
std::vector<long long> calculate_costs(std::vector<signed> W, std::vector<signed> A,
std::vector<signed> B, std::vector<signed> E) {
int Q = big(E);
int N = big(W);
vi inds(N);
iota(all(inds),0ll);
sort(all(inds),[&](int x,int y) {return W[x] < W[y];});
vi benefit(N);
int sm = 0;
for (int i = 0;i<N;i++) {
sm+=A[inds[i]];
benefit[i] = A[inds[i]]-B[inds[i]];
}
std::vector<long long> R(Q, 0);
for (int ii = 0;ii<Q;ii++) {
int D = E[ii];
vi dp(N,0);
dp[0] = 0;
for (int i=1;i<N;i++) {
dp[i] = dp[i-1];
if (W[inds[i]]-W[inds[i-1]] <= D) {
if (i == 1) dp[i] = benefit[i]+benefit[i-1];
else dp[i] = benefit[i]+benefit[i-1]+dp[i-2];
}
if (i>=2 && W[inds[i]]-W[inds[i-2]] <= D) {
dp[i] = max(dp[i],benefit[i]+benefit[i-2]+((i>2)?dp[i-3]:0ll));
}
}
R[ii] = sm-dp[N-1];
}
return R;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |