oj.uz

Submission #774111

# Submission time Handle Problem Language Result Execution time Memory
774111 2023-07-05T12:05:17 Z qwerasdfzxcl Card Scoring (CCO19_day2problem1) C++17
3 / 100
 3031 ms 102800 KB 
#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{
		return pow(x-p, (double)k/2) + 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;

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

		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 (st[mid](x) >= st[mid+1](x)) 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];
vector<int> V[1001000];
double dp[1001000];

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

	cin >> k >> n;
	ll S = 0;
	for (int i=1;i<=n;i++){
		cin >> a[i];
		V[a[i]].push_back(i);
		idx[i] = (int)V[a[i]].size()-1;

		S += a[i];
	}
	if (k==2){
		printf("%.15f\n", (double)S);
		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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47316 KB Output is correct
2 Correct 24 ms 47260 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Incorrect 23 ms 47316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47344 KB Output is correct
2 Incorrect 21 ms 47352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47344 KB Output is correct
2 Incorrect 21 ms 47352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47344 KB Output is correct
2 Incorrect 21 ms 47352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2445 ms 69248 KB Output is correct
2 Correct 2547 ms 71688 KB Output is correct
3 Correct 999 ms 58276 KB Output is correct
4 Correct 1654 ms 60040 KB Output is correct
5 Correct 1239 ms 100688 KB Output is correct
6 Correct 1508 ms 102700 KB Output is correct
7 Correct 1505 ms 102728 KB Output is correct
8 Correct 1459 ms 102772 KB Output is correct
9 Correct 1469 ms 102800 KB Output is correct
10 Correct 1509 ms 102732 KB Output is correct
11 Correct 2364 ms 71064 KB Output is correct
12 Correct 2344 ms 70732 KB Output is correct
13 Correct 2096 ms 68952 KB Output is correct
14 Correct 3031 ms 72416 KB Output is correct
15 Correct 2913 ms 74720 KB Output is correct
16 Correct 2997 ms 73020 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47316 KB Output is correct
2 Correct 24 ms 47260 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Incorrect 23 ms 47316 KB Output isn't correct
6 Halted 0 ms 0 KB -