oj.uz

답안 #213332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
213332 2020-03-25T15:31:20 Z patrikpavic2 Sparklers (JOI17_sparklers) C++17
0 / 100
 5 ms 384 KB 
#include <cstdio>
#include <cstring>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 1e5 + 500;
const ll mil = 1e9;

ll dp_L[N], dp_R[N], k, n;
ll X[N], T, tX[N];

void obrni(){
	for(int i = 0;i < n;i++)
		tX[i] = mil - X[i];
	for(int i = 0;i < n;i++)
		X[i] = tX[n - i - 1];
	k = n - k - 1;
}

bool check(ll s){
	ll l = 0, r = 0;
	ll sum = 2LL * s * T;
	vector < pair < ll, ll > > L, R;
	
	for(ll i = k - 1;i >= 0;i--){
		ll cur = 2LL * s * T - X[i + 1] + X[i];
		ll dis = X[i + 1] - X[i];
		while(i > 0 && cur < 0){
			i--; 
			dis = max(dis, X[i + 1] - X[i] - cur);
			cur += 2LL * s * T - X[i + 1] + X[i];
		}
		L.PB({cur, dis});
		//printf("paket dajem %lld trazim %lld\n", cur, dis);
	}
	for(ll i = k + 1;i < n;i++){
		ll cur = 2LL * s * T - X[i] + X[i - 1];
		ll dis = X[i] - X[i - 1];
		while(i + 1 < n && cur < 0){
			i++; 
			dis = max(dis, X[i] - X[i - 1] - cur);
			cur += 2LL * s * T - X[i] + X[i - 1];
		}
		R.PB({cur, dis});
		//printf("paket dajem %lld trazim %lld\n", cur, dis);
	}
	//printf("L %d R %d\n", (int)L.size(), (int)R.size());
	for(;l < (ll)L.size() || r < (ll)R.size();){
		if((l == (ll)L.size() || L[l].Y > sum) && (r == (ll)R.size() || R[r].Y > sum))
			return 0;
		if(l == (ll)L.size() - 1 && r == (ll)R.size() - 1){
			if(sum >= L.back().Y && sum + L.back().X >= R.back().Y)
				return 1;
			if(sum >= R.back().Y && sum + R.back().X >= L.back().Y)
				return 1;
			return 0;
		}
		if((l == (ll)L.size()) || (r == (ll)R.size())){
			if(l == (ll)L.size()){
				sum += R[r].X; r++;
			}
			else{
				sum += L[l].X; l++;
			}
		}
		else{
			if((L[l].Y <= sum) + (R[r].Y <= sum) == 2){
				if(L[l].X > R[r].X){
					sum += L[l].X; l++;
				}
				else{
					sum += R[r].X; r++;
				}
			}
			else if(L[l].Y <= sum){
				sum += L[l].X; l++;
			}
			else{
				sum += R[r].X; r++;
			}
		}
		//printf("l = %lld r = %lld sum = %lld\n", l, r, sum);
	}
	return 1;	
	//printf("vracam 0\n");
}

bool pravi(int s){
	return check(s);
}

int main(){
	scanf("%lld%lld%lld", &n, &k, &T); k--;
	for(int i = 0;i < n;i++)
		scanf("%lld", X + i);
	ll x = 0;
	for(ll i = 30;i >= 0;i--){
		if(!pravi(x + (1LL << i)))
			x += 1LL << i;
	}
	printf("%lld\n", x + 1);
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &n, &k, &T); k--;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", X + i);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 5 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 5 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 5 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -