Submission #1198528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198528		Muhammad_Aneeq	Holiday (IOI14_holiday)	C++17	0 / 100	122 ms	7868 KiB

holiday

#include"holiday.h"
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<ld,ll>
#define fi first
#define se second
ll const N=1e5+10;
vector<ll>a;
ll s;
ll n;
pii dp[N][2]={};
pii check(ld mid)
{
    dp[s][0]={0,0};
    dp[s][1]={a[s]-mid,1};
    for (ll i=s-1;i>=0;i--)
    {
        dp[i][0]=max(make_pair(dp[i+1][0].first-mid,dp[i+1][0].se+1),make_pair(dp[i+1][1].first-mid,dp[i+1][1].se+1));
        dp[i][1]=max(make_pair(dp[i+1][0].first-2*mid+a[i],dp[i+1][0].se+2),make_pair(dp[i+1][1].first-2*mid+a[i],dp[i+1][1].se+2));
    }
    if (s+1<n)
    {
        dp[s+1][0]={-1e9,0};
        dp[s+1][1]={-1e9,0};
        for (ll j=0;j<=s;j++)
        {
            dp[s+1][0]=max(dp[s+1][0],max(make_pair(dp[j][0].first-(s+1-j)*mid,dp[j][0].se+(s+1-j)),make_pair(dp[j][1].first-(s+1-j)*mid,dp[j][1].se+(s+1-j))));
            dp[s+1][1]=max(dp[s+1][1],max(make_pair(dp[j][0].first-(s+1-j+1)*mid+a[s+1],dp[j][0].se+(s+1-j)+1),make_pair(dp[j][1].first-(s+1-j+1)*mid+a[s+1],dp[j][1].se+(s+1-j+1))));
        }
    }
    for (ll i=s+2;i<n;i++)
    {
        dp[i][0]=max(make_pair(dp[i-1][0].first-mid,dp[i-1][0].se+1),make_pair(dp[i-1][1].first-mid,dp[i-1][1].se+1));
        dp[i][1]=max(make_pair(dp[i-1][0].first-2*mid+a[i],dp[i-1][0].se+2),make_pair(dp[i-1][1].first-2*mid+a[i],dp[i-1][1].se+2));
    }
    pii ans={0,0};
    for (ll i=0;i<n;i++)
        ans=max(ans,max(dp[i][0],dp[i][1]));
    return ans;
}
pii check2(ld mid)
{
    dp[s][0]={0,0};
    dp[s][1]={a[s]-mid,1};
    for (ll i=s+1;i<n;i++)
    {
        dp[i][0]=max(make_pair(dp[i-1][0].first-mid,dp[i-1][0].se+1),make_pair(dp[i-1][1].first-mid,dp[i-1][1].se+1));
        dp[i][1]=max(make_pair(dp[i-1][0].first-2*mid+a[i],dp[i-1][0].se+2),make_pair(dp[i-1][1].first-2*mid+a[i],dp[i-1][1].se+2));
    }
    if (s-1>=0)
    {
        dp[s-1][0]={-1e9,0};
        dp[s-1][1]={-1e9,0};
        for (ll j=s;j<n;j++)
        {
            dp[s-1][0]=max(dp[s-1][0],max(make_pair(dp[j][0].first-(j-s+1)*mid,dp[j][0].se+(j-s+1)),make_pair(dp[j][1].first-(j-s+1)*mid,dp[j][1].se+(j-s+1))));
            dp[s-1][1]=max(dp[s-1][1],max(make_pair(dp[j][0].first-(j-s+2)*mid+a[s-1],dp[j][0].se+(j-s+1)+1),make_pair(dp[j][1].first-(j-s+2)*mid+a[s-1],dp[j][1].se+(j-s+2))));
        }
    }
    for (ll i=s-2;i>=0;i--)
    {
        dp[i][0]=max(make_pair(dp[i+1][0].first-mid,dp[i+1][0].se+1),make_pair(dp[i+1][1].first-mid,dp[i+1][1].se+1));
        dp[i][1]=max(make_pair(dp[i+1][0].first-2*mid+a[i],dp[i+1][0].se+2),make_pair(dp[i+1][1].first-2*mid+a[i],dp[i+1][1].se+2));
    }
    pii ans={0,0};
    for (ll i=0;i<n;i++)
        ans=max(ans,max(dp[i][0],dp[i][1]));
    return ans;
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) 
{
    s=start;
    n=N;
    for (ll i=0;i<n;i++)
        a.push_back(attraction[i]);
    ld epi=1e-6;
    ld st=-1e6,en=1e6+10;
    while (st+epi<en)
    {
        ld mid=(st+en)/2.;
        if (check(mid).se>d)
            st=mid;
        else
            en=mid;
    }
    ld st1=-1e6,en1=1e6+10;
    while (st1+epi<en1)
    {
        ld mid=(st1+en1)/2.;
        if (check2(mid).se>d)
            st1=mid;
        else
            en1=mid;
    }
    return max(check(en).fi+en*check(en).se,check2(en1).fi+en1*check2(en1).se);
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53