제출 #1245745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245745		YassirSalama	나일강 (IOI24_nile)	C++20	67 / 100	2092 ms	11440 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
const int maxn = 1e5+100;
int par[maxn];
vector<int> a,b,w;
void init(){
	for(int i = 0;i<maxn;i++){
		par[i] = i;
	}
}
int find(int node){
	return node==par[node]?node:par[node] = find(par[node]);
}
void merge(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b) return;
	par[b] = a;
}

vector<ll> calculate_costs(vector<int> W, vector<int> A,vector<int> B, vector<int> E) {
	a = A;
	b = B;
	w = W;
	vector<vector<ll>> v;
	int n = w.size();
	for(int i = 0;i<n;i++){
		v.pb({(ll)w[i],(ll)a[i],(ll)b[i]});
	}
	vector<ll> ans;
	sort(all(v));
	for(auto d : E){
		init();
		ll dp[n];memset(dp,0,sizeof(dp));
		for(int i =1;i<n;i++){
			dp[i] = 1e18;
		}
		dp[0] = v[0][1];
		for(int i=1;i<n;i++){
			dp[i] = min(dp[i],dp[i-1]+v[i][1]);
			if(abs(v[i-1][0]-v[i][0])<=d){
				dp[i] = min(dp[i],(i>=2?dp[i-2]:0LL)+(ll)v[i-1][2]+(ll)v[i][2]);
			}
			if(i>=2&&abs(v[i-2][0]-v[i][0])<=d){
				dp[i] = min(dp[i],(i>=3?dp[i-3]:0LL)+(ll)v[i-2][2]+(ll)v[i][2]+(ll)v[i-1][1]);
			}
		}
		ans.pb(dp[n-1]);
	}
	return ans;
}

• 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