This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define PB push_back
#define PPB pop_back
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef long double ld;
const int MAXN = 47;
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const ll INF = 1e18 + 7;
int x[MAXN], n, k, t;
vll lef, rig;
vpll L, R;
bool check(ll mid){
lef.clear();
rig.clear();
L.clear();
R.clear();
for(int i=k; i<n; i++) rig.PB(2 * mid * t - (x[i + 1] - x[i]) / 2);
for(int i=1; i<k; i++) lef.PB(2 * mid * t - (x[i + 1] - x[i]) / 2);
reverse(all(lef));
ll csu = 0, mi = 0;
for(auto &y : rig){
csu += y;
mi = min(mi, csu);
if(csu >= 0){
R.PB({csu, mi});
csu = mi = 0;
}
}
if(csu or mi) R.PB({csu, mi});
csu = mi = 0;
for(auto &y : lef){
csu += y;
mi = min(mi, csu);
if(csu >= 0){
L.PB({csu, mi});
csu = mi = 0;
}
}
if(csu or mi) L.PB({csu, mi});
int li = 0, ri = 0;
csu = 0;
while(1){
pll c1 = {-inf, -inf}, c2 = {-inf, -inf};
if(li < (int)L.size()) c1 = L[li];
if(ri < (int)R.size()) c2 = R[ri];
if(c1.X == -inf and c2.X == -inf) return 1;
if(c1.X > 0 and csu + c1.Y >= 0){
csu += c1.X;
li++;
continue;
}
if(c2.X > 0 and csu + c2.Y >= 0){
csu += c2.X;
ri++;
continue;
}
if(csu + c1.Y >= 0){
csu += c1.X;
li++;
continue;
}
if(csu + c2.Y >= 0){
csu += c2.X;
ri++;
continue;
}
return 0;
}
}
void solve(){
cin >> n >> k >> t;
for(int i=1; i<=n; i++) cin >> x[i], x[i] *= 2;
int lo = 1, hi = ((1e9 + 1) / t) + 1, ret = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(check(mid)) hi = mid - 1, ret = mid;
else lo = mid + 1;
}
cout << ret << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
//cin >> t;
while(tt--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |