Submission #1205977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205977		JakobZorz	Nile (IOI24_nile)	C++20	67 / 100	2093 ms	7560 KiB

nile

#include "nile.h"
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;

ll solve(vector<int>w,vector<int>a,vector<int>b,int D){
	int n=(int)w.size();
	// ce jih je sodo, potem samo sosede povezem
	ll res=0;
	for(int i:b)
		res+=i;
	if(n%2==0)
		return res;
		
	// 2 primera: 
	// [1 2] [3 4] 5 [6 7]
	// 5-ke ne poparckam		
	// [1 2] [3 4 5] [6 7]
	// 4-ke ne poparckam.
	// to lahko, samo ce abs(w[3]-w[5])<=D
	
	// 1. primer:
	ll res2=1e18;
	for(int i=0;i<n;i+=2)
		res2=min(res2,res-b[i]+a[i]);
	// 2. primer
	for(int i=1;i<n;i+=2)
		if(abs(w[i-1]-w[i+1])<=D)
			res2=min(res2,res-b[i]+a[i]);
	return res2;
}

vector<ll>calculate_costs(vector<int>W,vector<int>A,vector<int>B,vector<int>E){
	vector<pair<int,pair<int,int>>>arr; // (W, (A, B))
	int n=(int)W.size();
	for(int i=0;i<n;i++){
		arr.push_back({W[i],{A[i],B[i]}});
	}
	sort(arr.begin(),arr.end());	
	vector<ll>res;
	for(int D:E){
		vector<int>w;			
		vector<int>a;			
		vector<int>b;			
		res.push_back(0);
		for(int i=0;i<n;i++){
			w.push_back(arr[i].first);
			a.push_back(arr[i].second.first);
			b.push_back(arr[i].second.second);
			if(i==n-1||abs(arr[i].first-arr[i+1].first)>D){
				res.back()+=solve(w,a,b,D);
				w.clear();
				a.clear();
				b.clear();
			}
		}
	}
	return res;
}

• 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