oj.uz

Submission #906022

# Submission time Handle Problem Language Result Execution time Memory
906022 2024-01-13T10:03:38 Z PenguinsAreCute Homecoming (BOI18_homecoming) C++17
100 / 100
 144 ms 106436 KB 
#include <bits/stdc++.h>
#include "homecoming.h"
#define int long long
using namespace std;
// val(i+1,j) = (Apre[j] - Apre[i]) - (Bpre[j+k-1] - Bpre[i]) + dp[i]
// maximise dp - Apre + Bpre.
long long solve(signed N, signed K, signed *A, signed *B) {
	int dp[N], Apre[N], Bpre[N+K], best = 0, ans = 0;
	for(int i=0;i<N;i++) Apre[i]=(i?Apre[i-1]:0)+A[i];
	for(int i=0;i<N+K;i++) Bpre[i]=(i?Bpre[i-1]:0)+B[i%N];
	for(int i=0;i<N;i++) {
		dp[i]=max(i?dp[i-1]:0,Apre[i]-Bpre[i+K-1]+best);
		best=max(best,dp[i]-Apre[i]+Bpre[i]);
		ans = max(ans, dp[i]);
	}
	best = 0;
	for(int i=0;i<N;i++) {
		dp[i]=max(i?dp[i-1]:(int)(-2.67e15),Apre[i]-Bpre[min(i+K-1,N-1LL)]+best);
		best=max(best,dp[i]-Apre[i]+Bpre[i]);
	}
	ans = max(ans, dp[N-1]);
	return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 25516 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 143 ms 102448 KB Output is correct
4 Correct 2 ms 1332 KB Output is correct
5 Correct 7 ms 3104 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 38 ms 25516 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 143 ms 102448 KB Output is correct
14 Correct 2 ms 1332 KB Output is correct
15 Correct 7 ms 3104 KB Output is correct
16 Correct 144 ms 106436 KB Output is correct
17 Correct 64 ms 27496 KB Output is correct
18 Correct 112 ms 41296 KB Output is correct
19 Correct 95 ms 59372 KB Output is correct
20 Correct 102 ms 85500 KB Output is correct
21 Correct 98 ms 56356 KB Output is correct