oj.uz

Submission #412900

# Submission time Handle Problem Language Result Execution time Memory
412900 2021-05-27T18:51:56 Z amoo_safar Sparklers (JOI17_sparklers) C++17
0 / 100
 133 ms 32496 KB 
// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e3 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int n, k;
ll X[N];
vector<ll> A, B;
ll psA[N], psB[N];

int dp[N][N];

bool Check(ll T){
	if(T > 1000000000)
		return true;
	A = {T};
	B = {};
	for(int i = k + 1; i <= n; i++){
		A.pb(X[i - 1] - X[i]);
		A.pb(T);
	}
	for(int i = k - 1; i >= 1; i--){
		B.pb(X[i] - X[i + 1]);
		B.pb(T);
	}
	psA[0] = 0;
	for(int i = 1; i <= (int) A.size(); i++)
		psA[i] = psA[i - 1] + A[i - 1];
	psB[0] = 0;
	for(int i = 1; i <= (int) B.size(); i++)
		psB[i] = psB[i - 1] + B[i - 1];

	// memset(dp, 0, sizeof dp);
	int sa = A.size(), sb = B.size();
	int pa = 0, pb = 0;
	while((pa < sa) || (pb < sb)){
		ll nw = psA[pa] + psB[pb];
		if(nw < 0) return false;
		if(pa == sa){
			pb ++;
			continue;
		}
		if(pb == sb){
			pa ++;
			continue;
		}
		int des = pa;
		for(int nx = pa + 1; nx <= sa; nx ++){
			if(psA[nx] + psB[pb] < 0) break;
			if(psA[pa] <= psA[nx]){
				des = nx;
				break;
			}
		}
		if(des > pa){
			pa++;
			continue;
		}
		des = pb;
		for(int nx = pb + 1; nx <= sb; nx ++){
			if(psA[pa] + psB[nx] < 0) break;
			if(psB[pb] <= psB[nx]){
				des = nx;
				break;
			}
		}
		if(des > pb){
			pb ++;
			continue;
		}
		pa ++;
	}

	return psA[sa] + psB[sb] >= 0;
}

bool Check2(ll T){
	if(T > 1000000000)
		return true;
	A = {T};
	B = {};
	for(int i = k + 1; i <= n; i++){
		A.pb(X[i - 1] - X[i]);
		A.pb(T);
	}
	for(int i = k - 1; i >= 1; i--){
		B.pb(X[i] - X[i + 1]);
		B.pb(T);
	}
	psA[0] = 0;
	for(int i = 1; i <= (int) A.size(); i++)
		psA[i] = psA[i - 1] + A[i - 1];
	psB[0] = 0;
	for(int i = 1; i <= (int) B.size(); i++)
		psB[i] = psB[i - 1] + B[i - 1];
 
	memset(dp, 0, sizeof dp);
	int sa = A.size(), sb = B.size();
	dp[0][0] = 1;
	for(int i = 0; i <= sa; i++){
		for(int j = 0; j <= sb; j++){
			if(i + j == 0) continue;
			if(psA[i] + psB[j] < 0) continue;
			if(i)
				dp[i][j] |= dp[i - 1][j];
			if(j)
				dp[i][j] |= dp[i][j - 1];
		}
	}
	return dp[sa][sb];
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll T;
	cin >> n >> k >> T;
	for(int i = 1; i <= n; i++)
		cin >> X[i];

	int mid, L = -1, R = 1000000000;
	while(L + 1 < R){
		mid = (L + R) >> 1;
		if(Check(2ll * T * mid) != Check2(2ll * T * mid)){
			if(Check2(2ll * T * mid))
				assert(false);
		}
		if(Check2(2ll * T * mid))
			R = mid;
		else L = mid;
	}
	cout << R << '\n';
	return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 16108 KB Output is correct
2 Correct 122 ms 16112 KB Output is correct
3 Correct 117 ms 16076 KB Output is correct
4 Correct 128 ms 16116 KB Output is correct
5 Correct 130 ms 16112 KB Output is correct
6 Correct 129 ms 16112 KB Output is correct
7 Correct 133 ms 16076 KB Output is correct
8 Correct 127 ms 16112 KB Output is correct
9 Correct 127 ms 16112 KB Output is correct
10 Correct 132 ms 16128 KB Output is correct
11 Correct 132 ms 16076 KB Output is correct
12 Runtime error 108 ms 32496 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 16108 KB Output is correct
2 Correct 122 ms 16112 KB Output is correct
3 Correct 117 ms 16076 KB Output is correct
4 Correct 128 ms 16116 KB Output is correct
5 Correct 130 ms 16112 KB Output is correct
6 Correct 129 ms 16112 KB Output is correct
7 Correct 133 ms 16076 KB Output is correct
8 Correct 127 ms 16112 KB Output is correct
9 Correct 127 ms 16112 KB Output is correct
10 Correct 132 ms 16128 KB Output is correct
11 Correct 132 ms 16076 KB Output is correct
12 Runtime error 108 ms 32496 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 16108 KB Output is correct
2 Correct 122 ms 16112 KB Output is correct
3 Correct 117 ms 16076 KB Output is correct
4 Correct 128 ms 16116 KB Output is correct
5 Correct 130 ms 16112 KB Output is correct
6 Correct 129 ms 16112 KB Output is correct
7 Correct 133 ms 16076 KB Output is correct
8 Correct 127 ms 16112 KB Output is correct
9 Correct 127 ms 16112 KB Output is correct
10 Correct 132 ms 16128 KB Output is correct
11 Correct 132 ms 16076 KB Output is correct
12 Runtime error 108 ms 32496 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -