oj.uz

답안 #61510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61510 2018-07-26T06:13:04 Z koosaga(#1775) Homecoming (BOI18_homecoming) C++11
0 / 100
 1000 ms 20328 KB 
#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
using lint = long long;
const int MAXN = 4000005;

lint a[MAXN], b[MAXN], dp[MAXN];

long long solve(int N, int K, int *A, int *B){
	if(1ll * N * K > 2000000) return -1;
	for(int i=1; i<=N; i++){
		a[i] = a[i+N] = A[i-1];
		b[i] = b[i+N] = B[i-1];
	}
	for(int i=1; i<=2*N; i++){
		a[i] += a[i-1];
		b[i] += b[i-1];
	}
	if(K == N){
		return max(0ll, a[N] - b[N]);
	}
	// First DP : Go across the interval
	lint ans = 0;
	for(int i=N; i; i--){
		dp[i] = a[N] - a[i-1] - (b[N] - b[i-1]); // [i, N]
		dp[i] = max(dp[i], dp[i+1]); // Fuck it
		for(int j=i+1; j+K-2<=N; j++){
			dp[i] = max(dp[i], dp[j] - (b[j + K - 2] - b[i-1]) + (a[j-1] - a[i-1]));
		}
		if(i + K - 2 <= N) ans = max(ans, dp[i] + a[i-1] - b[i + K - 2]);
	}
	// Second DP : Act like it never existed
	for(int i=N; i; i--){
		dp[i] = dp[i+1];
		for(int j=i+1; j+1<=N; j++){
			dp[i] = max(dp[i], dp[j] - (b[j+K-2] - b[i-1]) + (a[j-1] - a[i-1]));
		}
	}
	ans = max(ans, dp[1]);
	return ans;
}

/*
int main() {
  int T; assert(scanf("%d", &T) == 1);
  for(int t = 0; t < T; t++) {
    int N, K; assert(scanf("%d%d", &N, &K) == 2);
    int *A = new int[N];
    int *B = new int[N];
    for(int i = 0; i < N; i++) assert(scanf("%d", &A[i]) == 1);
    for(int i = 0; i < N; i++) assert(scanf("%d", &B[i]) == 1);
    printf("%lld\n", solve(N, K, A, B));
    delete[] A;
    delete[] B;
  }
  return 0;
}*/

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1081 ms 20328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -