oj.uz

Submission #61454

# Submission time Handle Problem Language Result Execution time Memory
61454 2018-07-26T04:18:56 Z 김세빈(#1779) Homecoming (BOI18_homecoming) C++11
0 / 100
 287 ms 94540 KB 
#include "homecoming.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[2020202][2][2];
ll S[2020202];

ll solve(int n, int k, int *A, int *B)
{
	int i;
	
	S[0] = B[0];
	for(i=1; i<n; i++){
		S[i] = S[i-1] + B[i];
	}
	
	dp[0][0][0] = 0;
	dp[0][0][1] = dp[0][1][0] = -1e18;
	dp[0][1][1] = A[0] - S[k-1];
	
	for(i=1; i<=n-k; i++){
		dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][0][0]);
		dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][0][1]);
		
		dp[i][1][0] = max(dp[i-1][0][0] + A[i] - S[i+k-1] + S[i-1], dp[i-1][1][0] + A[i] - B[i+k-1]);
		dp[i][1][1] = max(dp[i-1][0][1] + A[i] - S[i+k-1] + S[i-1], dp[i-1][1][1] + A[i] - B[i+k-1]);
	}
	
	for(; i<n; i++){
		dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][0][0]);
		dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][0][1]);
		
		dp[i][1][0] = max(dp[i-1][0][0] + A[i] - S[n-1] + S[i-1] - S[k-n+i-1], dp[i-1][1][0] + A[i] - B[k-n+i-1]);
		dp[i][1][1] = max(dp[i-1][0][1] + A[i] - S[n-1] + S[i-1], dp[i-1][1][1] + A[i]);
	}
	
	return max(max(dp[n-1][0][0], dp[n-1][1][0]), max(dp[n-1][0][1], dp[n-1][1][1]));
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Incorrect 2 ms 484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Incorrect 2 ms 484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 24060 KB Output is correct
2 Correct 6 ms 24060 KB Output is correct
3 Correct 287 ms 94540 KB Output is correct
4 Correct 6 ms 94540 KB Output is correct
5 Incorrect 14 ms 94540 KB Output isn't correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Incorrect 2 ms 484 KB Output isn't correct
4 Halted 0 ms 0 KB -