oj.uz

Submission #61493

# Submission time Handle Problem Language Result Execution time Memory
61493 2018-07-26T05:36:16 Z khsoo01 Homecoming (BOI18_homecoming) C++11
0 / 100
 77 ms 20072 KB 
#include"homecoming.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 2000005;

ll n, k, s[2*N], dt[N], dt2[N];

ll solve (int _N, int _K, int *A, int *B) {
	n = _N;
	k = _K;
	ll R = 0;
	for(ll i=0;i<n;i++) {
		R += A[i] - B[i];
	}
	for(int i=0;i<2*n;i++) {
		s[i+1] = s[i] + B[i%n];
	}
	R = max(R, 0ll);
	ll M = 0;
	dt[0] = A[0] - s[k];
	R = max(R, dt[0]);
	M = max(M, dt[0]);
	for(ll i=1;i<n;i++) {
		dt[i] = max(M + A[i] - s[k+i] + s[i], dt[i-1] + A[i] - B[(i+k-1)%n]);
		R = max(R, dt[i]);
		M = max(M, dt[i]);
	}
	for(ll C=0,i=1;i<=n-k;i++) {
		C += A[n-i] - B[n-i];
		dt2[i] = max(dt2[i-1], C);
	}
	R = max(R, dt[0] + dt2[n-k]);
	M = dt[0];
	for(ll i=1;i<=n-k;i++) {
		dt[i] = max(M + A[i] - s[k+i] + s[i], dt[i-1] + A[i] - B[i]);
		R = max(R, dt[i] + dt2[n-k-i]);
		M = max(M, dt[i]);
	}
	return R;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Incorrect 3 ms 492 KB Output isn't correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Incorrect 3 ms 492 KB Output isn't correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 20072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Incorrect 3 ms 492 KB Output isn't correct