# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1227444 | PVM_pvm | Message (IOI24_message) | C++20 | 0 ms | 0 KiB |
#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100'007
int n;
struct art
{
long long w,a,b;
} ar[MAXN];
bool cmp(art &a, art &b)
{
return a.w<b.w;
}
long long dp[MAXN];
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
int Q = (int)E.size();
n=A.size();
for (int q=0;q<n;q++) ar[q]={W[q],A[q],B[q]};
sort(ar,ar+n,cmp);
vector<long long> R(Q);
for (int curq=0;curq<Q;curq++)
{
int d=E[curq];
dp[0]=0;
dp[1]=ar[0].a;
for (int q=2;q<=n;q++) ///
{
dp[q]=dp[q-1]+ar[q-1].a;
long long buf=0;
for (int w=q-2;w>=max(0,q-3);w--)
{
if ((ar[q-1].w-ar[w].w)>d) break;
long long cur=dp[w]+(ar[q-1].b)+ar[w].b+buf;
if (cur<dp[q]) dp[q]=cur;
buf+=ar[w].a;
}
//cout<<dp[q]<<" t ";
}
//cout<<"\n";
R[curq]=dp[n];
}
return R;
}