제출 #1219819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219819		nikulid	Nile (IOI24_nile)	C++20	67 / 100	2095 ms	10824 KiB

nile

// nikulid
// written in neovim

#include "nile.h"
#include <algorithm>

// #include <iostream>


using namespace std;

/*


   !!! REMEMBER TO REMOVE #include <iostream> BEFORE SUBMITTING !!!

 --- WEIRD CASES TO CONSIDER ---
    > multiple artifacts of the same weight
    > 

*/

#define ll long long
#define pb push_back
#define mp make_pair

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
	
	int n = (int)W.size();
	int Q = (int)E.size();

	vector<ll> R(Q, 0);

	// W[] is the weights
  
	// start by sorting W in ascending order
	vector<pair<int, pair<int, int>>> ns(n);
	pair<int, pair<int, int>> p;
	int base_cost=0;
	for(int i=0; i<n; i++){
		p = mp(W[i], mp(A[i], B[i]));
		base_cost += A[i];
		ns[i] = p;
	}
	sort(ns.begin(), ns.end());
	
	vector<pair<ll, ll>> dp(n);
	vector<ll> w(n),a(n),b(n);
	for(int i=0; i<n; i++){
		w[i] = ns[i].first;
		a[i] = ns[i].second.first;
		b[i] = ns[i].second.second;
	}

	ll D;
	ll possible;
	pair<ll,ll> hereA;
	
	// ---
	/*
	if(0==1){
		cout<<"<--- INIT START --->\n";
		cout<<"w[] >> \t";
		for(int i=0; i<n; i++){
			cout<<w[i]<<",\t";
		}
		cout<<"\na[] >> \t";
		for(int i=0; i<n; i++){
			cout<<a[i]<<",\t";
		}
		cout<<"\nb[] >> \t";
		for(int i=0; i<n; i++){
			cout<<b[i]<<",\t";
		}
		cout<<"\n\n<--- INIT FINISH --->\n";

	}
	*/
	// ---

	for(int _=0; _<Q; _++){

		D = E[_];
		dp = vector<pair<ll,ll>>(n, mp(-1, -1));
		dp[0].first = a[0];

		// dp[i].first = NOT in a pair
		// dp[i].second = IS in a pair

		for(int i=1; i<n; i++){
			// calculate dp[i]..
			
			// [i].first
			possible=69;

			possible = dp[i-1].first + a[i];
			if(dp[i-1].second != -1){
				possible = min(possible, dp[i-1].second + a[i]);
			}
			hereA.first = possible;

			// [i].second

			possible = -1;
			if(abs(w[i-1] - w[i]) <= D){
				// CASE: adjacent
				possible = dp[i-1].first - a[i-1] + b[i-1] + b[i];
				//if(0==1){cout<<"$firstcase:"<<possible<<"| ";}
			}
			/*
			else if(0==1){
				cout<<"firstcase:NONE| ";
			}
			*/
			if(i>1 && abs(w[i-2] - w[i]) <= D){
				// CASE: not adjacent
				possible = min(possible, dp[i-2].first - a[i-2] + b[i-2] + a[i-1] + b[i]);
			}
			hereA.second = possible;

			// cout<<"$hereA:"<<hereA.first<<","<<hereA.second<<"|";
			
			dp[i] = hereA;
		}
		R[_] = dp[n-1].first;
		if(dp[n-1].second != -1){
			R[_] = min(R[_], dp[n-1].second);
		}
		/*
		if(0==1){
			cout<<"\nquery "<<_<<" has the following `dp[]`:\n";
			cout<<"YESPAIR\t";
			for(int i=0; i<n; i++){
				cout<<dp[i].second<<",\t";
			}
			cout<<"\nNOPAIR\t";
			for(int i=0; i<n; i++){
				cout<<dp[i].first<<",\t";
			}
			cout<<"\n\n";
		}
		*/
	}
	return R;
}

• 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