oj.uz

Submission #799629

# Submission time Handle Problem Language Result Execution time Memory
799629 2023-07-31T17:00:26 Z GusterGoose27 Measures (CEOI22_measures) C++17
24 / 100
 1500 ms 3152 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp(int n, vector<int> &x, int d) {
	ll final = 0; // times 2
	ll change = 2*d; // times 2
	for (int i = 1; i < n; i++) {
		int pos = x[i]-x[i-1];
		change -= 2*pos;
		if (change >= final) {
			/*
			(change-npos)+final = npos => npos = (change+final)/2;
			*/
			assert((change&1) == (final&1));
			ll npos = (change+final)/2;
			assert(npos <= change);
			final += change-npos;
			change = npos;
		}
		else if (-change >= final) {
			ll npos = -final;
			assert(npos >= change);
			change = npos;
		}
		change += 2*d;
	}
	return final;
}

void print(ll a) {
	cout << a/2;
	if (a & 1) cout << ".5";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m, d;
	cin >> n >> m >> d;
	vector<int> elems;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		elems.push_back(x);
	}
	for (int j = 0; j < m; j++) {
		int x; cin >> x;
		elems.push_back(x);
		sort(elems.begin(), elems.end()); // appreciate my laziness
		if (j > 0) cout << ' ';
		print(dp(n+j+1, elems, d));
	}
	cout << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 101 ms 3092 KB Output is correct
10 Correct 145 ms 3152 KB Output is correct
11 Correct 41 ms 3088 KB Output is correct
12 Correct 154 ms 3064 KB Output is correct
13 Correct 51 ms 2716 KB Output is correct
14 Correct 98 ms 3112 KB Output is correct
15 Correct 93 ms 2460 KB Output is correct
16 Correct 48 ms 3076 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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