Submission #74422

#	Time	Username	Problem	Language	Result	Execution time	Memory
74422		gs18115	요리 강좌 (KOI17_cook)	C++14	100 / 100	581 ms	296536 KiB

cook

#include<iostream>
#include<deque>
using namespace std;
typedef long long LL;
const LL MAXN=3010;
const LL INF=1e18;
const LL inf=1e15;
struct STRUCT
{
    LL aa,cost;
}mini[MAXN][3];
LL NA[MAXN];
inline bool chk(const LL&day,const LL&X,const LL&i)
{
    return mini[day][i].aa!=X&&mini[day][i].aa!=NA[X];
}
inline LL mincost(const LL&day,const LL&X)
{
    if(chk(day,X,0))
        return mini[day][0].cost;
    else if(chk(day,X,1))
        return mini[day][1].cost;
    return mini[day][2].cost;
}
inline void minch(const LL&day,const LL&aa,const LL&cost)
{
    if(cost<mini[day][0].cost)
    {
        mini[day][2]=mini[day][1];
        mini[day][1]=mini[day][0];
        mini[day][0]={aa,cost};
    }
    else if(cost<mini[day][1].cost)
    {
        mini[day][2]=mini[day][1];
        mini[day][1]={aa,cost};
    }
    else if(cost<mini[day][2].cost)
        mini[day][2]={aa,cost};
    return;
}
deque<STRUCT>deq[MAXN];
LL N,M,s,e,T;
LL i,j;
LL MIN,t;
LL cost;
LL S[MAXN][MAXN];
LL dp[MAXN][MAXN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>N>>M>>s>>e>>T;
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=M;j++)
        {
            cin>>cost;
            S[i][j]=S[i][j-1]+cost;
        }
    }
    for(i=1;i<=N;i++)
        cin>>NA[i];
    mini[0][0]=mini[0][1]=mini[0][2]={0,0};
    for(i=1;i<=M;i++)
        mini[i][0]=mini[i][1]=mini[i][2]={0,INF};
    for(i=1;i<=M;i++)
    {
        for(j=1;j<=N;j++)
        {
            while(!deq[j].empty())
            {
                if(deq[j].front().aa<i-e)
                    deq[j].pop_front();
                else
                    break;
            }
            if(i>=s)
            {
                t=mincost(i-s,j)-S[j][i-s];
                while(!deq[j].empty())
                {
                    if(deq[j].back().cost>=t)
                        deq[j].pop_back();
                    else
                        break;
                }
                if(t<inf)
                    deq[j].push_back({i-s,t});
            }
            if(deq[j].empty())
                dp[i][j]=INF;
            else
            {
                dp[i][j]=deq[j].front().cost+S[j][i]+T;
                minch(i,j,dp[i][j]);
            }
        }
    }
    MIN=INF;
    for(i=M-e;i<M;i++)
    {
        for(j=1;j<=N;j++)
        {
            t=mincost(i,j)+T+S[j][M]-S[j][i];
            if(MIN>t)
                MIN=t;
        }
    }
    cout<<MIN-T<<endl;
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 9 / 9
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 44 / 44