oj.uz

답안 #412884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
412884 2021-05-27T18:19:48 Z amoo_safar Sparklers (JOI17_sparklers) C++17
0 / 100
 64 ms 16128 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){
			if(psA[pa] + psB[pb + 1] < 0) return false;
			pb ++;
			continue;
		}
		if(pb == sb){
			if(psA[pa + 1] + psB[pb] < 0) return false;
			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 = des;
			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 = des;
			continue;
		}
		pa ++;
	}

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

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))
			R = mid;
		else L = mid;
	}
	cout << R << '\n';
	return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 16076 KB Output is correct
2 Correct 61 ms 16076 KB Output is correct
3 Correct 59 ms 16076 KB Output is correct
4 Correct 63 ms 16128 KB Output is correct
5 Correct 62 ms 16128 KB Output is correct
6 Correct 62 ms 16124 KB Output is correct
7 Correct 62 ms 16076 KB Output is correct
8 Correct 61 ms 16108 KB Output is correct
9 Correct 62 ms 16076 KB Output is correct
10 Correct 63 ms 16108 KB Output is correct
11 Correct 64 ms 16112 KB Output is correct
12 Incorrect 64 ms 16112 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 16076 KB Output is correct
2 Correct 61 ms 16076 KB Output is correct
3 Correct 59 ms 16076 KB Output is correct
4 Correct 63 ms 16128 KB Output is correct
5 Correct 62 ms 16128 KB Output is correct
6 Correct 62 ms 16124 KB Output is correct
7 Correct 62 ms 16076 KB Output is correct
8 Correct 61 ms 16108 KB Output is correct
9 Correct 62 ms 16076 KB Output is correct
10 Correct 63 ms 16108 KB Output is correct
11 Correct 64 ms 16112 KB Output is correct
12 Incorrect 64 ms 16112 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 16076 KB Output is correct
2 Correct 61 ms 16076 KB Output is correct
3 Correct 59 ms 16076 KB Output is correct
4 Correct 63 ms 16128 KB Output is correct
5 Correct 62 ms 16128 KB Output is correct
6 Correct 62 ms 16124 KB Output is correct
7 Correct 62 ms 16076 KB Output is correct
8 Correct 61 ms 16108 KB Output is correct
9 Correct 62 ms 16076 KB Output is correct
10 Correct 63 ms 16108 KB Output is correct
11 Correct 64 ms 16112 KB Output is correct
12 Incorrect 64 ms 16112 KB Output isn't correct
13 Halted 0 ms 0 KB -