oj.uz

Submission #365369

# Submission time Handle Problem Language Result Execution time Memory
365369 2021-02-11T14:18:54 Z kostia244 Homecoming (BOI18_homecoming) C++17
62 / 100
 1000 ms 91120 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#include"homecoming.h"
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
int n, k;
vector<ll> a, b;
ll naive1(int fil) {
	deque<ll> dp;
	const ll inf = 1ll<<50;
	for(int i = 0; i <= k; i++)
		dp.push_back(i == fil ? 0 : -inf);
	ll best = 0, lazyadd = 0;
	for(int i = 0; i < n; i++) {
		ll bk = dp.back();
		ll ne0 = best+lazyadd;
		dp.pop_back();
		dp.back() = max(dp.back(), bk);
		dp.back() += a[i];
		lazyadd += b[i];
		best = max(best, dp.back());
		if(i < n-fil) {
			dp.push_front(ne0-lazyadd);
			best = max(best, dp.front());
		} else dp.push_front(-inf-lazyadd);
	}
	return best+lazyadd;
}
long long solve(int N, int K, int *A, int *B) {
	n = N, k = K;
	a = vector<ll>(A, A+n);
	b = vector<ll>(B, B+n);
	reverse(all(a));
	reverse(all(b));
	for(auto &i : b) i *= -1;
	ll ans = 0;
	for(int i = 0; i < k; i++) ans = max(ans, naive1(i));
	return ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 236 ms 660 KB Output is correct
7 Correct 165 ms 748 KB Output is correct
8 Correct 30 ms 620 KB Output is correct
9 Correct 5 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 12140 KB Output is correct
2 Correct 16 ms 876 KB Output is correct
3 Correct 176 ms 86892 KB Output is correct
4 Correct 16 ms 1132 KB Output is correct
5 Correct 24 ms 2752 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 236 ms 660 KB Output is correct
7 Correct 165 ms 748 KB Output is correct
8 Correct 30 ms 620 KB Output is correct
9 Correct 5 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 56 ms 12140 KB Output is correct
12 Correct 16 ms 876 KB Output is correct
13 Correct 176 ms 86892 KB Output is correct
14 Correct 16 ms 1132 KB Output is correct
15 Correct 24 ms 2752 KB Output is correct
16 Execution timed out 1087 ms 91120 KB Time limit exceeded
17 Halted 0 ms 0 KB -