Submission #774136

#	Time	Username	Problem	Language	Result	Execution time	Memory
774136		qwerasdfzxcl	Card Scoring (CCO19_day2problem1)	C++17	25 / 100	629 ms	99124 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, k;

struct Func{
	int p;
	double q;

	Func(){}
	Func(int _p, double _q): p(_p), q(_q) {}

	double operator()(int x) const{
		double tmp = x-p;
		if (k==3) return sqrt(tmp*tmp*tmp) + q;
		return tmp*tmp + q;
	}
};

int cross(const Func &f, const Func &g){
	int l = g.p + 1, r = n, ans = n+1;
	
	while(l<=r){
		int mid = (l+r)>>1;
		if (f(mid) >= g(mid)) ans = mid, r = mid-1;
		else l = mid+1;
	}

	return ans;
}

struct Hull{
	vector<Func> st;
	vector<double> C;

	void insert(Func g){
		// printf("insert %d %f\n", g.p, g.q);
		double tmp = 0;
		while(st.size() >= 2){
			tmp = cross(st.back(), g);
			if (C.back() > tmp) break;
			st.pop_back();
			C.pop_back();
		}

		if (st.size() >= 2) C.push_back(tmp);
		else if (st.size() == 1) C.push_back(cross(st.back(), g));
		st.push_back(g);
	}

	double query(int x){
		int l = 0, r = (int)st.size()-2, ans = (int)st.size()-1;
		while(l<=r){
			int mid = (l+r)>>1;
			if (x >= C[mid]) ans = mid, r = mid-1;
			else l = mid+1;
		}

		// for (int i=0;i<(int)st.size();i++) printf("%f ", st[i](x));
		// printf("\n");
		// printf("return: %f \n", st[ans](x));

		return st[ans](x);
	}
}H[1001000];

int a[1001000], idx[1001000], cnt[1001000];
double dp[1001000];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> k >> n;
	for (int i=1;i<=n;i++){
		cin >> a[i];
		cnt[a[i]]++;
		idx[i] = cnt[a[i]];
	}
	if (k==2){
		printf("%.15f\n", (double)n);
		return 0;
	}

	for (int i=1;i<=n;i++){
		// printf(" ok %d %f\n", idx[i]-1, dp[i-1]);
		H[a[i]].insert(Func(idx[i]-1, dp[i-1]));
		dp[i] = H[a[i]].query(idx[i]);
		// printf("%d -> %.15f\n", i, dp[i]);
	}

	printf("%.15f\n", dp[n]);
}

• Subtask 1: 4 / 4
• Subtask 2: 1 / 1
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 3 / 3
• Subtask 6: 9 / 9