Submission #428699

#	Time	Username	Problem	Language	Result	Execution time	Memory
428699		oolimry	Sparklers (JOI17_sparklers)	C++17	50 / 100	303 ms	34740 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
#define l first
#define r second
typedef long long lint;
typedef pair<lint,lint> ii;

const lint inf = 1e17;
lint n, K, TT, T; 
lint pos[100005];

ii memo[1005][1005];

ii dp(int l, int r){
	if(r < K) return ii(inf,-inf);
	if(l > K) return ii(inf,-inf);
	if(l == K and r == K) return ii(pos[K], pos[K]);
	if(memo[l][r] != ii(-1,-1)) return memo[l][r];
	
	lint dis = r-l;
	
	ii A = dp(l, r-1);
	A.l -= T, A.r += T;
	ii B = ii(pos[r] - dis*T, pos[r] + dis*T);
	
	ii res1 = ii(max(A.l, B.l), min(A.r, B.r));
	if(res1.l > res1.r) res1 = ii(inf,-inf);
	
	A = dp(l+1,r);
	A.l -= T, A.r += T;
	B = ii(pos[l] - dis*T, pos[l] + dis*T);
	ii res2 = ii(max(A.l, B.l), min(A.r, B.r));
	if(res2.l > res2.r) res2 = ii(inf,-inf);
	
	//show2(l,r);
	//show2(res1.l, res1.r);
	//show2(res2.l, res2.r);
	
	if(res1.l > res2.l) swap(res1, res2);
	
	
	if(res2.l <= 1e15 and res1.r >= -1e15) assert(res2.l <= res1.r + 1);
	ii newres = ii(min(res1.l,res2.l), max(res1.r,res2.r));
	
	if(newres.l > newres.r) newres = ii(inf,-inf);
	memo[l][r] = newres;
	//show2(newres.l, newres.r);
	return newres;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> K >> TT; K--;
	for(int i = 0;i < n;i++) cin >> pos[i];
	
	lint low = -1, high = 1e10 / TT;
	while(low != high-1){
		lint mid = (low+high)/2;
		T = mid * TT;
		for(int i = 0;i < n;i++) fill(memo[i], memo[i]+n, ii(-1,-1));
		
		ii res = dp(0,n-1);
		if(res.l <= res.r) high = mid;
		else low = mid;
		
	}
	
	cout << high;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50