Submission #428844

#	Time	Username	Problem	Language	Result	Execution time	Memory
428844		tqbfjotld	Sparklers (JOI17_sparklers)	C++14	0 / 100	65 ms	16092 KiB

sparklers

#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(){
    long long n,k,t;
    scanf("%lld%lld%lld",&n,&k,&t);
    N = n; K = k; T = t;
    K--;
    for (int x = 0; x<N; x++){
        long long t;
        scanf("%lld",&t);
        arr[x] = t;
    }
    int r = 1000000000LL/T+1;
    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:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%lld%lld%lld",&n,&k,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%lld",&t);
      |         ~~~~~^~~~~~~~~~~

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