Submission #1117561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117561		JuanJL	Nile (IOI24_nile)	C++17	67 / 100	2056 ms	21180 KiB

nile

#include <bits/stdc++.h>

using namespace std;
#define fst first
#define snd second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define INF 100000000000000000

typedef long long ll;

const int MAXN = 1000000+5;

struct Objeto{
	ll peso;
	ll costoA;
	ll costoB;
};

bool operator<(const Objeto &a, const Objeto &b){
	if(a.peso<b.peso) return true;
	if(a.peso>b.peso) return false;
	if(a.costoA-a.costoB < b.costoA-b.costoB) return true;
	return false;
}

vector<Objeto> o;

ll e;
ll dp[MAXN];

ll f(ll x){
	ll &res = dp[x];
	if(res!=-1) return res;
	if(x==SZ(o)) return 0;
	res = o[x].costoA+f(x+1);
	ll aux=0;
	if(x+1<SZ(o)&&abs(o[x].peso-o[x+1].peso)<=e) res=min(res,o[x].costoB+o[x+1].costoB+f(x+2));
	if(x+2<SZ(o) && abs(o[x].peso-o[x+2].peso)<=e ) res=min(res,o[x].costoB+o[x+2].costoB+o[x+1].costoA+f(x+3));
	return res;
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
	vector<ll> r;
	
	forn(i,0,SZ(W)){
		Objeto aux;
		o.pb(aux);
		o[i].peso=W[i];
		o[i].costoA=A[i];
		o[i].costoB=B[i];
	}
	
	sort(ALL(o));
	reverse(ALL(o));

	mset(dp,-1);
	
	while(!E.empty()){
		e = E[SZ(E)-1];
		E.pop_back();
		mset(dp,-1);
		r.pb(f(0));
	}
	reverse(ALL(r));
	return r;
}

Compilation message (stderr)

nile.cpp: In function 'll f(ll)':
nile.cpp:40:5: warning: unused variable 'aux' [-Wunused-variable]
   40 |  ll aux=0;
      |     ^~~

• 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