제출 #955806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955806		vjudge1	Sparklers (JOI17_sparklers)	C++17	50 / 100	48 ms	8660 KiB

sparklers

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const long long maxn=1000+10;
const long long logn=25;

long long n,k,t;
long long x[maxn];
long long dp[maxn][maxn];
long long kol=0;

long long f(long long L,long long R)
{
    if(L==0 && R==n-1)
    {
        return true;
    }
    if(dp[L][R]!=-1)
    {
        return dp[L][R];
    }
    long long rez=0;
    if(R<n-1 && (x[R+1]-x[L])<=(R-L+1)*t*(2*kol))
    {
        rez=max(rez,f(L,R+1));
    }
    if(L>0 && (x[R]-x[L-1])<=(R-L+1)*t*(2*kol))
    {
        rez=max(rez,f(L-1,R));
    }
    return dp[L][R]=rez;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k>>t;
    k--;
    for(long long i=0;i<n;i++)
    {
        cin>>x[i];
    }
    long long l=0;
    long long r=x[n-1]-x[0];
    long long ans=0;
    while(l<=r)
    {
        memset(dp,-1,sizeof dp);
        long long mid=l+(r-l)/2;
        kol=mid;
        if(f(k,k))
        {
            ans=mid;
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<ans<<endl;

    /*long long m,n;
    cin>>m>>n;
    long long mi=2e9;
    long long mx=-1;
    vector<pair<pair<long long,long long>,pair<long long,long long>>>p;
    vector<pair<pair<long long,long long>,pair<long long,long long>>>x;
    for(long long i=0;i<m;i++)
    {
        long long a,b,c,d;
        cin>>a>>b>>c>>d;
        p.push_back({{a,b},{c,d}});
        mi=min(mi,a);
        mx=max(mx,b);
    }
    n=mx-mi+1;
    map<long long,long long>m;
    long long cnt=0;
    for(long long i=mi;i<=mx;i++)
    {
        m[i]=cnt;
        cnt++;
    }
    for(long long i=0;i<m;i++)
    {
        long long a=p.first.first;
        long long b=p.first.second;
        long long c=p.second.first;
        long long d=p.second.second;
        x.push_back({{m[a],m[b]},{m[c],m[d]}});
    }*/

    return 0;
}

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