oj.uz

Submission #365310

# Submission time Handle Problem Language Result Execution time Memory
365310 2021-02-11T12:25:08 Z kostia244 Homecoming (BOI18_homecoming) C++17
0 / 100
 1000 ms 15980 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;
vector<int> tooka, tookb;
ll naive1() {
	ll ans = 0, cur = 0;
	while(true) {
		array<ll, 2> best = {-(1ll<<60), -1};
		ll sm = 0;
		for(int i = 0; i < k; i++) {
			sm += b[i]*!tookb[i];
		}
		for(int i = 0; i < n; i++) {
			if(!tooka[i]) {
				best = max(best, {a[i]-sm, i});
			}
			sm -= b[i]*!tookb[i];
			sm += b[(i+k)%n]*!tookb[(i+k)%n];
		}
		if(best[1] == -1) break;
		cur += best[0];
		tooka[best[1]] = 1;
		for(int i = 0; i < k; i++) tookb[(best[1]+i)%n]=1;
		ans = max(ans, cur);
	}
	return ans;
}
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);
	tooka = tookb = vector<int>(n, 0);
	return naive1();
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 15980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

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