oj.uz

Submission #60918

# Submission time Handle Problem Language Result Execution time Memory
60918 2018-07-25T01:32:38 Z spencercompton Homecoming (BOI18_homecoming) C++14
62 / 100
 1000 ms 78836 KB 
#include <bits/stdc++.h>
#include "homecoming.h"

using namespace std;
typedef long long ll;
ll pre[4000001];
long long int solve(int N, int K, int *A, int *B){
	ll ans = 0LL;
	for(int z = 0; z<=K; z++){
		ll here = 0LL;
		for(int i = 0; i<z; i++){
			here -= B[i];
		}
		pre[0] = 0LL;
		for(int i = 1; i<=N; i++){
			if(i<=z){
				pre[i] = 0LL;
				pre[i+N] = 0LL;
			}
			else{
				pre[i] = B[i-1];
				pre[i+N] = B[i-1];
			}
		}
		for(int i = 1; i<=2*N; i++){
			pre[i] += pre[i-1];
		}
		ll f[N];
		//choosing to buy whole thing
		ll g[N];
		//choosing to add last one

		//[i,i+K-1]
		for(int i = N-1; i>=0; i--){
			f[i] = 0;
			g[i] = 0;
			//F
			ll takeF = pre[i+K] - pre[i];
			takeF = -takeF;
			takeF += A[i];
			if(i<N-1){
				takeF += g[i+1];
			}
			f[i] = max(f[i],takeF);
			if(i<N-1){
				f[i] = max(f[i],f[i+1]);
			}

			//G

			int aft = i+K-1;
			int ind = aft;
			if(ind>=N){
				ind -= N;
			}
			//take it
			ll takeG = A[i];
			if(ind>=z){
				takeG -= B[ind];
			}
			if(i<N-1){
				takeG += g[i+1];
			}
			g[i] = max(takeG,g[i]);
			if(aft+1<N){
				g[i] = max(g[i],f[aft+1]);
			}

		}
		here += f[0];
		ans = max(ans,here);
	}
	return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 5 ms 484 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 4 ms 536 KB Output is correct
5 Correct 3 ms 540 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 5 ms 484 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 4 ms 536 KB Output is correct
5 Correct 3 ms 540 KB Output is correct
6 Correct 417 ms 832 KB Output is correct
7 Correct 300 ms 832 KB Output is correct
8 Correct 45 ms 832 KB Output is correct
9 Correct 13 ms 832 KB Output is correct
10 Correct 4 ms 832 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 20220 KB Output is correct
2 Correct 30 ms 20220 KB Output is correct
3 Correct 288 ms 78796 KB Output is correct
4 Correct 37 ms 78796 KB Output is correct
5 Correct 56 ms 78796 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 5 ms 484 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 4 ms 536 KB Output is correct
5 Correct 3 ms 540 KB Output is correct
6 Correct 417 ms 832 KB Output is correct
7 Correct 300 ms 832 KB Output is correct
8 Correct 45 ms 832 KB Output is correct
9 Correct 13 ms 832 KB Output is correct
10 Correct 4 ms 832 KB Output is correct
11 Correct 87 ms 20220 KB Output is correct
12 Correct 30 ms 20220 KB Output is correct
13 Correct 288 ms 78796 KB Output is correct
14 Correct 37 ms 78796 KB Output is correct
15 Correct 56 ms 78796 KB Output is correct
16 Execution timed out 1068 ms 78836 KB Time limit exceeded
17 Halted 0 ms 0 KB -