Submission #1178093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178093		alexander707070	Nile (IOI24_nile)	C++20	67 / 100	2095 ms	6352 KiB

nile

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const long long inf=1e17;

struct item{
	int w;
	int a,b;

	inline friend bool operator < (item fr,item sc){
		return fr.w<sc.w;
	}
};

int n;
item a[MAXN];
long long pref[MAXN];

long long sum(int l,int r){
	return pref[r]-pref[l-1];
}

long long dp[MAXN];

long long calcdp(int delta){
	for(int i=1;i<=n;i++){
		dp[i]=dp[i-1]+a[i].a;

		for(int f=i-1;f>=max(1,i-2);f--){
			if(a[i].w-a[f].w>delta)break;

			dp[i]=min(dp[i],dp[f-1]+a[i].b+a[f].b+sum(f+1,i-1));
		}
	}

	return dp[n];
}

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

	for(int i=1;i<=n;i++){
		a[i]={W[i-1],A[i-1],B[i-1]};
	}
	sort(a+1,a+n+1);

	for(int i=1;i<=n;i++){
		pref[i]=pref[i-1]+a[i].a;
	}

	vector<long long> ans;
	for(int i:E){
		ans.push_back(calcdp(i));
	}

	return ans;
}

/*int main(){

	auto res=calculate_costs({15, 12, 2, 10, 21},
		{5, 4, 5, 6, 3},
		{1, 2, 2, 3, 2},
		{5, 9, 1});

	for(auto s:res)cout<<s<<" ";

	return 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