oj.uz

Submission #774131

# Submission time Handle Problem Language Result Execution time Memory
774131 2023-07-05T12:15:53 Z qwerasdfzxcl Card Scoring (CCO19_day2problem1) C++17
25 / 100
 1990 ms 99100 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;
	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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47408 KB Output is correct
2 Correct 21 ms 47340 KB Output is correct
3 Correct 21 ms 47352 KB Output is correct
4 Correct 21 ms 47312 KB Output is correct
5 Correct 22 ms 47276 KB Output is correct
6 Correct 22 ms 47316 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 24 ms 47364 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47336 KB Output is correct
2 Correct 24 ms 47324 KB Output is correct
3 Correct 22 ms 47304 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47336 KB Output is correct
2 Correct 24 ms 47324 KB Output is correct
3 Correct 22 ms 47304 KB Output is correct
4 Correct 24 ms 47336 KB Output is correct
5 Correct 24 ms 47324 KB Output is correct
6 Correct 22 ms 47304 KB Output is correct
7 Correct 26 ms 47360 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 23 ms 47332 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47336 KB Output is correct
2 Correct 24 ms 47324 KB Output is correct
3 Correct 22 ms 47304 KB Output is correct
4 Correct 24 ms 47336 KB Output is correct
5 Correct 24 ms 47324 KB Output is correct
6 Correct 22 ms 47304 KB Output is correct
7 Correct 26 ms 47360 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 23 ms 47332 KB Output is correct
10 Correct 30 ms 47368 KB Output is correct
11 Correct 28 ms 47444 KB Output is correct
12 Correct 28 ms 47332 KB Output is correct
13 Correct 28 ms 47468 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1720 ms 62972 KB Output is correct
2 Correct 1741 ms 62920 KB Output is correct
3 Correct 765 ms 55064 KB Output is correct
4 Correct 873 ms 55584 KB Output is correct
5 Correct 896 ms 82500 KB Output is correct
6 Correct 955 ms 80744 KB Output is correct
7 Correct 998 ms 80836 KB Output is correct
8 Correct 975 ms 80644 KB Output is correct
9 Correct 960 ms 80620 KB Output is correct
10 Correct 957 ms 80640 KB Output is correct
11 Correct 1601 ms 63004 KB Output is correct
12 Correct 1593 ms 63372 KB Output is correct
13 Correct 1548 ms 63000 KB Output is correct
14 Correct 1806 ms 63348 KB Output is correct
15 Correct 1797 ms 63444 KB Output is correct
16 Correct 1774 ms 63372 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47408 KB Output is correct
2 Correct 21 ms 47340 KB Output is correct
3 Correct 21 ms 47352 KB Output is correct
4 Correct 21 ms 47312 KB Output is correct
5 Correct 22 ms 47276 KB Output is correct
6 Correct 22 ms 47316 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 24 ms 47364 KB Output is correct
9 Correct 24 ms 47336 KB Output is correct
10 Correct 24 ms 47324 KB Output is correct
11 Correct 22 ms 47304 KB Output is correct
12 Correct 24 ms 47336 KB Output is correct
13 Correct 24 ms 47324 KB Output is correct
14 Correct 22 ms 47304 KB Output is correct
15 Correct 26 ms 47360 KB Output is correct
16 Correct 23 ms 47316 KB Output is correct
17 Correct 23 ms 47332 KB Output is correct
18 Correct 30 ms 47368 KB Output is correct
19 Correct 28 ms 47444 KB Output is correct
20 Correct 28 ms 47332 KB Output is correct
21 Correct 28 ms 47468 KB Output is correct
22 Correct 1720 ms 62972 KB Output is correct
23 Correct 1741 ms 62920 KB Output is correct
24 Correct 765 ms 55064 KB Output is correct
25 Correct 873 ms 55584 KB Output is correct
26 Correct 896 ms 82500 KB Output is correct
27 Correct 955 ms 80744 KB Output is correct
28 Correct 998 ms 80836 KB Output is correct
29 Correct 975 ms 80644 KB Output is correct
30 Correct 960 ms 80620 KB Output is correct
31 Correct 957 ms 80640 KB Output is correct
32 Correct 1601 ms 63004 KB Output is correct
33 Correct 1593 ms 63372 KB Output is correct
34 Correct 1548 ms 63000 KB Output is correct
35 Correct 1806 ms 63348 KB Output is correct
36 Correct 1797 ms 63444 KB Output is correct
37 Correct 1774 ms 63372 KB Output is correct
38 Correct 725 ms 99100 KB Output is correct
39 Correct 1790 ms 62996 KB Output is correct
40 Correct 1862 ms 63040 KB Output is correct
41 Correct 777 ms 55176 KB Output is correct
42 Correct 929 ms 55532 KB Output is correct
43 Correct 866 ms 82520 KB Output is correct
44 Correct 1067 ms 80748 KB Output is correct
45 Correct 1594 ms 62972 KB Output is correct
46 Correct 1589 ms 62908 KB Output is correct
47 Correct 1560 ms 62928 KB Output is correct
48 Correct 1962 ms 62948 KB Output is correct
49 Correct 1990 ms 63004 KB Output is correct
50 Correct 1940 ms 63028 KB Output is correct