oj.uz

답안 #543396

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
543396 2022-03-30T13:16:56 Z fcw Feast (NOI19_feast) C++17
71 / 100
 1000 ms 21580 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

using dbl = long double;
const lint INF = 3.1e14;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, k;
	cin>>n>>k;
	vector<lint>a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	dbl lo = 0, hi = INF;
	for(int z=0;z<150;z++){
		dbl mid = (lo + hi) / 2;
		vector<array<pair<dbl, lint>, 2>>dp(n+1); 
		dp[0][0] = {0, 0}, dp[0][1] = {-INF, 0};
		for(int i=0;i<n;i++){
			dp[i+1][1] = max(make_pair(dp[i][1].st + a[i], dp[i][1].nd), 
					make_pair(dp[i][0].st + a[i] - mid, dp[i][0].nd + 1));
				
			dp[i+1][0] = max(dp[i][0], dp[i][1]);	
		}
		if(max(dp[n][0], dp[n][1]).nd >= k) lo = mid;
		else hi = mid; 
	}
	dbl mid = hi;
	vector<array<dbl, 2>>dp(n+1); 
	dp[0][0] = 0, dp[0][1] = -INF;
	for(int i=0;i<n;i++){
		dp[i+1][1] = max(dp[i][1] + a[i], dp[i][0] + a[i] - mid);
		dp[i+1][0] = max(dp[i][0], dp[i][1]);	
	}
	cout<< lint(round(max(dp[n][0], dp[n][1]) + mid * k))<<"\n";	
	
		
	
	

	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 787 ms 20912 KB Output is correct
2 Correct 867 ms 21304 KB Output is correct
3 Correct 872 ms 21568 KB Output is correct
4 Correct 809 ms 21344 KB Output is correct
5 Correct 815 ms 21260 KB Output is correct
6 Correct 817 ms 20892 KB Output is correct
7 Correct 783 ms 20932 KB Output is correct
8 Correct 886 ms 21256 KB Output is correct
9 Correct 799 ms 20964 KB Output is correct
10 Correct 798 ms 21212 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 763 ms 21076 KB Output is correct
2 Correct 798 ms 21580 KB Output is correct
3 Correct 781 ms 20944 KB Output is correct
4 Correct 777 ms 21196 KB Output is correct
5 Correct 821 ms 20876 KB Output is correct
6 Correct 772 ms 20996 KB Output is correct
7 Correct 790 ms 21520 KB Output is correct
8 Correct 797 ms 21388 KB Output is correct
9 Correct 788 ms 20844 KB Output is correct
10 Correct 777 ms 21396 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 927 ms 21364 KB Output is correct
2 Correct 895 ms 21072 KB Output is correct
3 Correct 923 ms 21280 KB Output is correct
4 Correct 929 ms 21088 KB Output is correct
5 Correct 907 ms 21268 KB Output is correct
6 Correct 881 ms 21424 KB Output is correct
7 Correct 935 ms 21500 KB Output is correct
8 Correct 985 ms 21248 KB Output is correct
9 Correct 933 ms 21556 KB Output is correct
10 Correct 904 ms 21384 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 7 ms 468 KB Output is correct
22 Correct 6 ms 468 KB Output is correct
23 Correct 6 ms 468 KB Output is correct
24 Correct 6 ms 468 KB Output is correct
25 Correct 7 ms 460 KB Output is correct
26 Correct 6 ms 460 KB Output is correct
27 Correct 6 ms 468 KB Output is correct
28 Correct 5 ms 356 KB Output is correct
29 Correct 6 ms 468 KB Output is correct
30 Correct 6 ms 468 KB Output is correct

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 787 ms 20912 KB Output is correct
2 Correct 867 ms 21304 KB Output is correct
3 Correct 872 ms 21568 KB Output is correct
4 Correct 809 ms 21344 KB Output is correct
5 Correct 815 ms 21260 KB Output is correct
6 Correct 817 ms 20892 KB Output is correct
7 Correct 783 ms 20932 KB Output is correct
8 Correct 886 ms 21256 KB Output is correct
9 Correct 799 ms 20964 KB Output is correct
10 Correct 798 ms 21212 KB Output is correct
11 Correct 763 ms 21076 KB Output is correct
12 Correct 798 ms 21580 KB Output is correct
13 Correct 781 ms 20944 KB Output is correct
14 Correct 777 ms 21196 KB Output is correct
15 Correct 821 ms 20876 KB Output is correct
16 Correct 772 ms 20996 KB Output is correct
17 Correct 790 ms 21520 KB Output is correct
18 Correct 797 ms 21388 KB Output is correct
19 Correct 788 ms 20844 KB Output is correct
20 Correct 777 ms 21396 KB Output is correct
21 Correct 927 ms 21364 KB Output is correct
22 Correct 895 ms 21072 KB Output is correct
23 Correct 923 ms 21280 KB Output is correct
24 Correct 929 ms 21088 KB Output is correct
25 Correct 907 ms 21268 KB Output is correct
26 Correct 881 ms 21424 KB Output is correct
27 Correct 935 ms 21500 KB Output is correct
28 Correct 985 ms 21248 KB Output is correct
29 Correct 933 ms 21556 KB Output is correct
30 Correct 904 ms 21384 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 316 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 2 ms 340 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 1 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 2 ms 340 KB Output is correct
49 Correct 2 ms 340 KB Output is correct
50 Correct 2 ms 340 KB Output is correct
51 Correct 7 ms 468 KB Output is correct
52 Correct 6 ms 468 KB Output is correct
53 Correct 6 ms 468 KB Output is correct
54 Correct 6 ms 468 KB Output is correct
55 Correct 7 ms 460 KB Output is correct
56 Correct 6 ms 460 KB Output is correct
57 Correct 6 ms 468 KB Output is correct
58 Correct 5 ms 356 KB Output is correct
59 Correct 6 ms 468 KB Output is correct
60 Correct 6 ms 468 KB Output is correct
61 Execution timed out 1085 ms 20944 KB Time limit exceeded
62 Halted 0 ms 0 KB -