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 int long long
pair<int,int> memo[1005][1005];
int arr[100005];
int K,T,N;
int M;
pair<int,int> func(int a, int b){
if (a==b) return a==K?make_pair(arr[K]-M*T,arr[K]+M*T):make_pair(999999999999999999LL,-999999999999999999LL);
if (memo[a][b]!=make_pair(-1LL,-1LL)) return memo[a][b];
if (b<K || a>K) return {999999999999999999LL,-999999999999999999LL};
auto opt1 = func(a,b-1);
auto opt2 = func(a+1,b);
//printf("opt1 = %lld %lld, \n",opt1);
// printf("optw = %lld %lld, ab = %lld %lld\n",opt2,a,b);
if (opt1.second<opt1.first){
if (opt2.second<opt2.first) return memo[a][b] = {999999999999999999LL,-999999999999999999LL};
int sz = (b-a);
if (sz*T*M+arr[a]<opt2.first) return memo[a][b] = {999999999999999999LL,-999999999999999999LL};
return memo[a][b] = {opt2.first-T*M,(sz+1)*T*M+arr[a]};
}
else {
int sz = (b-a);
if (-sz*T*M+arr[b]>opt1.second) return memo[a][b] = {999999999999999999LL,-999999999999999999LL};
return memo[a][b] = {-(sz+1)*T*M+arr[b],opt1.second+T*M};
}
}
bool test(int val){
M = val;
memset(memo,-1,sizeof(memo));
auto res = func(0,N-1);
//printf("val = %lld, res = %lld %lld\n",val,res);
return res.second>res.first;
}
main(){
scanf("%lld%lld%lld",&N,&K,&T);
K--;
for (int x = 0; x<N; x++){
scanf("%lld",&arr[x]);
}
int r = 1000000000LL;
int l = -1LL;
while (l+1<r){
int mid = (l+r)/2;
if (test(mid)){
r = mid;
}
else l = mid;
}
printf("%lld\n",r);
}
Compilation message (stderr)
sparklers.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
41 | main(){
| ^~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%lld%lld%lld",&N,&K,&T);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%lld",&arr[x]);
| ~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |