oj.uz

Submission #774114

# Submission time Handle Problem Language Result Execution time Memory
774114 2023-07-05T12:07:05 Z qwerasdfzxcl Card Scoring (CCO19_day2problem1) C++17
25 / 100
 3811 ms 113524 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;
	for (int i=1;i<=n;i++){
		cin >> a[i];
		V[a[i]].push_back(i);
		idx[i] = (int)V[a[i]].size()-1;
	}
	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 23 ms 47264 KB Output is correct
2 Correct 23 ms 47288 KB Output is correct
3 Correct 25 ms 47332 KB Output is correct
4 Correct 22 ms 47340 KB Output is correct
5 Correct 23 ms 47272 KB Output is correct
6 Correct 22 ms 47248 KB Output is correct
7 Correct 22 ms 47244 KB Output is correct
8 Correct 23 ms 47272 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47240 KB Output is correct
2 Correct 22 ms 47216 KB Output is correct
3 Correct 22 ms 47360 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47240 KB Output is correct
2 Correct 22 ms 47216 KB Output is correct
3 Correct 22 ms 47360 KB Output is correct
4 Correct 22 ms 47240 KB Output is correct
5 Correct 22 ms 47216 KB Output is correct
6 Correct 22 ms 47360 KB Output is correct
7 Correct 27 ms 47316 KB Output is correct
8 Correct 23 ms 47264 KB Output is correct
9 Correct 22 ms 47340 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47240 KB Output is correct
2 Correct 22 ms 47216 KB Output is correct
3 Correct 22 ms 47360 KB Output is correct
4 Correct 22 ms 47240 KB Output is correct
5 Correct 22 ms 47216 KB Output is correct
6 Correct 22 ms 47360 KB Output is correct
7 Correct 27 ms 47316 KB Output is correct
8 Correct 23 ms 47264 KB Output is correct
9 Correct 22 ms 47340 KB Output is correct
10 Correct 30 ms 47552 KB Output is correct
11 Correct 33 ms 47404 KB Output is correct
12 Correct 28 ms 47452 KB Output is correct
13 Correct 27 ms 47564 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2391 ms 67024 KB Output is correct
2 Correct 2559 ms 68684 KB Output is correct
3 Correct 1004 ms 57312 KB Output is correct
4 Correct 1663 ms 58224 KB Output is correct
5 Correct 1272 ms 96264 KB Output is correct
6 Correct 1548 ms 97568 KB Output is correct
7 Correct 1539 ms 97572 KB Output is correct
8 Correct 1608 ms 97584 KB Output is correct
9 Correct 1486 ms 97576 KB Output is correct
10 Correct 1483 ms 97552 KB Output is correct
11 Correct 2375 ms 68284 KB Output is correct
12 Correct 2407 ms 67056 KB Output is correct
13 Correct 2099 ms 66948 KB Output is correct
14 Correct 3049 ms 68700 KB Output is correct
15 Correct 2903 ms 70964 KB Output is correct
16 Correct 3187 ms 69268 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47264 KB Output is correct
2 Correct 23 ms 47288 KB Output is correct
3 Correct 25 ms 47332 KB Output is correct
4 Correct 22 ms 47340 KB Output is correct
5 Correct 23 ms 47272 KB Output is correct
6 Correct 22 ms 47248 KB Output is correct
7 Correct 22 ms 47244 KB Output is correct
8 Correct 23 ms 47272 KB Output is correct
9 Correct 22 ms 47240 KB Output is correct
10 Correct 22 ms 47216 KB Output is correct
11 Correct 22 ms 47360 KB Output is correct
12 Correct 22 ms 47240 KB Output is correct
13 Correct 22 ms 47216 KB Output is correct
14 Correct 22 ms 47360 KB Output is correct
15 Correct 27 ms 47316 KB Output is correct
16 Correct 23 ms 47264 KB Output is correct
17 Correct 22 ms 47340 KB Output is correct
18 Correct 30 ms 47552 KB Output is correct
19 Correct 33 ms 47404 KB Output is correct
20 Correct 28 ms 47452 KB Output is correct
21 Correct 27 ms 47564 KB Output is correct
22 Correct 2391 ms 67024 KB Output is correct
23 Correct 2559 ms 68684 KB Output is correct
24 Correct 1004 ms 57312 KB Output is correct
25 Correct 1663 ms 58224 KB Output is correct
26 Correct 1272 ms 96264 KB Output is correct
27 Correct 1548 ms 97568 KB Output is correct
28 Correct 1539 ms 97572 KB Output is correct
29 Correct 1608 ms 97584 KB Output is correct
30 Correct 1486 ms 97576 KB Output is correct
31 Correct 1483 ms 97552 KB Output is correct
32 Correct 2375 ms 68284 KB Output is correct
33 Correct 2407 ms 67056 KB Output is correct
34 Correct 2099 ms 66948 KB Output is correct
35 Correct 3049 ms 68700 KB Output is correct
36 Correct 2903 ms 70964 KB Output is correct
37 Correct 3187 ms 69268 KB Output is correct
38 Correct 795 ms 113524 KB Output is correct
39 Correct 2647 ms 69032 KB Output is correct
40 Correct 3633 ms 71588 KB Output is correct
41 Correct 986 ms 58248 KB Output is correct
42 Correct 1960 ms 60072 KB Output is correct
43 Correct 1305 ms 100668 KB Output is correct
44 Correct 2163 ms 102832 KB Output is correct
45 Correct 2367 ms 70772 KB Output is correct
46 Correct 2362 ms 70996 KB Output is correct
47 Correct 2166 ms 69004 KB Output is correct
48 Correct 3454 ms 71492 KB Output is correct
49 Correct 3811 ms 71076 KB Output is correct
50 Correct 3721 ms 72552 KB Output is correct