Submission #1176661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176661		ASN49K	Sparklers (JOI17_sparklers)	C++20	30 / 100	2021 ms	16892 KiB

sparklers

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

struct interval
{
    int l,r;
};


std::vector<interval> add_range(std::vector<interval> a,int k)
{
    std::vector<interval>rez;
    std::map<int,int>mp;
    for(auto &c:a)
    {
        mp[c.l-k]++;
        mp[c.r+k+1]--;
    }

    int last=-1,sum=0;
    for(auto &c:mp)
    {
        if(sum==0)
        {
            last=c.first;
        }
        sum+=c.second;
        if(sum==0)
        {
            rez.push_back({last , c.first-1});
        }
    }
    return rez;
}
std::vector<interval> unite(std::vector<interval>a,std::vector<interval> b)
{
    std::vector<interval>rez;
    std::map<int,int>mp;
    for(auto &c:a)
    {
        mp[c.l]++;
        mp[c.r+1]--;
    }
    for(auto &c:b)
    {
        mp[c.l]++;
        mp[c.r+1]--;
    }

    int last=-1,sum=0;
    for(auto &c:mp)
    {
        if(sum==0)
        {
            last=c.first;
        }
        sum+=c.second;
        if(sum==0)
        {
            rez.push_back({last , c.first-1});
        }
    }
    return rez;
}

std::vector<interval> intersect(std::vector<interval>a,std::vector<interval> b)
{
    std::vector<interval>rez;
    std::map<int,int>mp;
    for(auto &c:a)
    {
        mp[c.l]++;
        mp[c.r+1]--;
    }
    for(auto &c:b)
    {
        mp[c.l]++;
        mp[c.r+1]--;
    }

    int last=-1,sum=0;
    for(auto &c:mp)
    {
        int last_sum=sum;
        sum+=c.second;
        if(last_sum<2 && sum==2)
        {
            last=c.first;
        }
        if(sum<2 && last_sum==2)
        {
            rez.push_back({last,c.first-1});
        }
    }
    return rez;
}
main()
{
    int n,k,t;
    std::cin>>n>>k>>t;
    k--;

    std::vector<int>a(n);
    for(auto &c:a)
    {
        std::cin>>c;
    }
    auto test=[&](int s)->bool
    {
        std::vector<std::vector<std::vector<interval>>>dp(n,std::vector<std::vector<interval>>(n));
        dp[k][k]={{a[k],a[k]}};
        for(int l=n-1;l>=0;l--)
        {
            for(int r=l+1;r<n;r++)
            {
                auto ll=intersect(add_range(dp[l][r-1],t*s) , {{a[r]-(r-l)*t*s,a[r]+(r-l)*t*s}});
                auto rr=intersect(add_range(dp[l+1][r],t*s) , {{a[l]-(r-l)*t*s,a[l]+(r-l)*t*s}});
                dp[l][r]=unite(ll , rr);
                assert(dp[l][r].size()<=1);
            }
        }

        return dp[0][n-1].size()>0;
    };
    int st=0,dr=a.back(),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:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main()
      | ^~~~

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