Submission #232892

#	Time	Username	Problem	Language	Result	Execution time	Memory
232892		thebes	Sparklers (JOI17_sparklers)	C++14	50 / 100	304 ms	7544 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
#define F first
#define S second
#define pb push_back

const int MN = 1005;
int N, K, T, i, j, lo, hi, mid, arr[MN];
double dp[MN][MN]; bitset<MN> vs[MN];

double solve(int l,int r){
    if(vs[l][r]) return dp[l][r];
    else if(l==r){
        if(l==K) return T;
        else return -1;
    }
    vs[l][r]=1;
    dp[l][r]=-1;
    if(solve(l,r-1)>=(arr[r]-arr[r-1])/(double)(2*mid))
        dp[l][r]=max(dp[l][r],solve(l,r-1)-(arr[r]-arr[r-1])/(double)(2*mid)+T);
    if(solve(l+1,r)>=(arr[l+1]-arr[l])/(double)(2*mid))
        dp[l][r]=max(dp[l][r],solve(l+1,r)-(arr[l+1]-arr[l])/(double)(2*mid)+T);
    return dp[l][r];
}

int main(){
    scanf("%d%d%d",&N,&K,&T);
    for(i=1;i<=N;i++)
        scanf("%d",&arr[i]);
    if(arr[N]==0){
        printf("0\n");
        return 0;
    }
    lo = 1, hi = 1e9;
    while(lo<hi){
        mid = (lo+hi)>>1;
        for(i=1;i<=N;i++)
            vs[i].reset();
        if(solve(1,N)>=0) hi=mid;
        else lo=mid+1;
    }
    printf("%d\n",lo);
    return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&N,&K,&T);
     ~~~~~^~~~~~~~~~~~~~~~~~~
sparklers.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[i]);
         ~~~~~^~~~~~~~~~~~~~

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