Submission #1176713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176713		ASN49K	Sparklers (JOI17_sparklers)	C++20	50 / 100	71 ms	16276 KiB

sparklers

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
const int inf=1e9;
using i64 = long long;
const i64 INF=1e18;
#define int long long

const int N_MAX=1000;
int a[N_MAX],n,k,t;
int min[N_MAX][N_MAX],max[N_MAX][N_MAX];

bool test(int s)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            min[i][j]=INF;
            max[i][j]=-INF;
        }
    }
        min[k][k]=max[k][k]=a[k];
        for(int l=n-1;l>=0;l--)
        {
            for(int r=l+1;r<n;r++)
            {
                min[l][r]=INF;
                max[l][r]=-INF;
                if(min[l][r-1]!=INF)
                {
                    min[l][r]=std::min(min[l][r] , std::max(min[l][r-1]-s*t , a[r]-(r-l)*s*t));
                    max[l][r]=std::max(max[l][r] , std::min(max[l][r-1]+s*t , a[r]+(r-l)*s*t));
                }
                if(min[l+1][r]!=INF)
                {
                    min[l][r]=std::min(min[l][r] , std::max(min[l+1][r]-s*t , a[l]-(r-l)*s*t));
                    max[l][r]=std::max(max[l][r] , std::min(max[l+1][r]+s*t , a[l]+(r-l)*s*t));
                }

                if(min[l][r]>max[l][r])
                {
                    min[l][r]=INF;
                    max[l][r]=-INF;
                }
            }
        }

        //std::cout<<min[1][2]<<' '<<max[1][2]<<'\n';
        return min[0][n-1]!=INF;
}
main()
{
    std::cin>>n>>k>>t;
    k--;

    for(int i=0;i<n;i++)
    {
        std::cin>>a[i];
    }
    //std::cout<<test(1);
    //return 0;

    int st=0,dr=a[n-1],rez=-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(test(mid))
        {
            dr=mid-1;
            rez=mid;
        }
        else
        {
            st=mid+1;
        }
    }
    assert(rez!=-1);

    std::cout<<rez;
    return 0;
}
/*
2 1 10
200
300
*/

Compilation message (stderr)

sparklers.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main()
      | ^~~~

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