답안 #74422 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74422	2018-09-01T07:07:29 Z	gs18115	요리 강좌 (KOI17_cook)	C++14	100 / 100	581 ms	296536 KB

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.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	5 ms	2948 KB	Output is correct
3	Correct	4 ms	3056 KB	Output is correct
4	Correct	4 ms	3056 KB	Output is correct
5	Correct	5 ms	3104 KB	Output is correct
6	Correct	4 ms	3176 KB	Output is correct
7	Correct	5 ms	3180 KB	Output is correct
8	Correct	4 ms	3248 KB	Output is correct
9	Correct	4 ms	3248 KB	Output is correct
10	Correct	4 ms	3264 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	5 ms	2948 KB	Output is correct
3	Correct	4 ms	3056 KB	Output is correct
4	Correct	4 ms	3056 KB	Output is correct
5	Correct	5 ms	3104 KB	Output is correct
6	Correct	4 ms	3176 KB	Output is correct
7	Correct	5 ms	3180 KB	Output is correct
8	Correct	4 ms	3248 KB	Output is correct
9	Correct	4 ms	3248 KB	Output is correct
10	Correct	18 ms	7244 KB	Output is correct
11	Correct	14 ms	7244 KB	Output is correct
12	Correct	22 ms	8336 KB	Output is correct
13	Correct	15 ms	8336 KB	Output is correct
14	Correct	17 ms	8884 KB	Output is correct
15	Correct	20 ms	9364 KB	Output is correct
16	Correct	21 ms	9848 KB	Output is correct
17	Correct	12 ms	9848 KB	Output is correct
18	Correct	20 ms	10688 KB	Output is correct
19	Correct	14 ms	10688 KB	Output is correct
20	Correct	4 ms	3264 KB	Output is correct

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	5 ms	2948 KB	Output is correct
3	Correct	4 ms	3056 KB	Output is correct
4	Correct	4 ms	3056 KB	Output is correct
5	Correct	5 ms	3104 KB	Output is correct
6	Correct	4 ms	3176 KB	Output is correct
7	Correct	5 ms	3180 KB	Output is correct
8	Correct	4 ms	3248 KB	Output is correct
9	Correct	4 ms	3248 KB	Output is correct
10	Correct	18 ms	7244 KB	Output is correct
11	Correct	14 ms	7244 KB	Output is correct
12	Correct	22 ms	8336 KB	Output is correct
13	Correct	15 ms	8336 KB	Output is correct
14	Correct	17 ms	8884 KB	Output is correct
15	Correct	20 ms	9364 KB	Output is correct
16	Correct	21 ms	9848 KB	Output is correct
17	Correct	12 ms	9848 KB	Output is correct
18	Correct	20 ms	10688 KB	Output is correct
19	Correct	14 ms	10688 KB	Output is correct
20	Correct	141 ms	38340 KB	Output is correct
21	Correct	183 ms	43296 KB	Output is correct
22	Correct	162 ms	48052 KB	Output is correct
23	Correct	147 ms	52956 KB	Output is correct
24	Correct	139 ms	57920 KB	Output is correct
25	Correct	168 ms	62900 KB	Output is correct
26	Correct	171 ms	67664 KB	Output is correct
27	Correct	138 ms	72572 KB	Output is correct
28	Correct	167 ms	77484 KB	Output is correct
29	Correct	147 ms	82372 KB	Output is correct
30	Correct	4 ms	3264 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	5 ms	2948 KB	Output is correct
3	Correct	4 ms	3056 KB	Output is correct
4	Correct	4 ms	3056 KB	Output is correct
5	Correct	5 ms	3104 KB	Output is correct
6	Correct	4 ms	3176 KB	Output is correct
7	Correct	5 ms	3180 KB	Output is correct
8	Correct	4 ms	3248 KB	Output is correct
9	Correct	4 ms	3248 KB	Output is correct
10	Correct	18 ms	7244 KB	Output is correct
11	Correct	14 ms	7244 KB	Output is correct
12	Correct	22 ms	8336 KB	Output is correct
13	Correct	15 ms	8336 KB	Output is correct
14	Correct	17 ms	8884 KB	Output is correct
15	Correct	20 ms	9364 KB	Output is correct
16	Correct	21 ms	9848 KB	Output is correct
17	Correct	12 ms	9848 KB	Output is correct
18	Correct	20 ms	10688 KB	Output is correct
19	Correct	14 ms	10688 KB	Output is correct
20	Correct	166 ms	87408 KB	Output is correct
21	Correct	141 ms	92428 KB	Output is correct
22	Correct	153 ms	97100 KB	Output is correct
23	Correct	126 ms	102168 KB	Output is correct
24	Correct	152 ms	107104 KB	Output is correct
25	Correct	129 ms	111868 KB	Output is correct
26	Correct	154 ms	116744 KB	Output is correct
27	Correct	159 ms	121684 KB	Output is correct
28	Correct	146 ms	126576 KB	Output is correct
29	Correct	136 ms	131348 KB	Output is correct
30	Correct	4 ms	3264 KB	Output is correct

Subtask #5
44.0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	5 ms	2948 KB	Output is correct
3	Correct	4 ms	3056 KB	Output is correct
4	Correct	4 ms	3056 KB	Output is correct
5	Correct	5 ms	3104 KB	Output is correct
6	Correct	4 ms	3176 KB	Output is correct
7	Correct	5 ms	3180 KB	Output is correct
8	Correct	4 ms	3248 KB	Output is correct
9	Correct	4 ms	3248 KB	Output is correct
10	Correct	18 ms	7244 KB	Output is correct
11	Correct	14 ms	7244 KB	Output is correct
12	Correct	22 ms	8336 KB	Output is correct
13	Correct	15 ms	8336 KB	Output is correct
14	Correct	17 ms	8884 KB	Output is correct
15	Correct	20 ms	9364 KB	Output is correct
16	Correct	21 ms	9848 KB	Output is correct
17	Correct	12 ms	9848 KB	Output is correct
18	Correct	20 ms	10688 KB	Output is correct
19	Correct	14 ms	10688 KB	Output is correct
20	Correct	141 ms	38340 KB	Output is correct
21	Correct	183 ms	43296 KB	Output is correct
22	Correct	162 ms	48052 KB	Output is correct
23	Correct	147 ms	52956 KB	Output is correct
24	Correct	139 ms	57920 KB	Output is correct
25	Correct	168 ms	62900 KB	Output is correct
26	Correct	171 ms	67664 KB	Output is correct
27	Correct	138 ms	72572 KB	Output is correct
28	Correct	167 ms	77484 KB	Output is correct
29	Correct	147 ms	82372 KB	Output is correct
30	Correct	166 ms	87408 KB	Output is correct
31	Correct	141 ms	92428 KB	Output is correct
32	Correct	153 ms	97100 KB	Output is correct
33	Correct	126 ms	102168 KB	Output is correct
34	Correct	152 ms	107104 KB	Output is correct
35	Correct	129 ms	111868 KB	Output is correct
36	Correct	154 ms	116744 KB	Output is correct
37	Correct	159 ms	121684 KB	Output is correct
38	Correct	146 ms	126576 KB	Output is correct
39	Correct	136 ms	131348 KB	Output is correct
40	Correct	224 ms	142648 KB	Output is correct
41	Correct	510 ms	187480 KB	Output is correct
42	Correct	478 ms	203452 KB	Output is correct
43	Correct	581 ms	219584 KB	Output is correct
44	Correct	213 ms	219584 KB	Output is correct
45	Correct	261 ms	219584 KB	Output is correct
46	Correct	271 ms	234856 KB	Output is correct
47	Correct	354 ms	259172 KB	Output is correct
48	Correct	534 ms	280104 KB	Output is correct
49	Correct	527 ms	296536 KB	Output is correct
50	Correct	4 ms	3264 KB	Output is correct

답안 #74422

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 9.0 / 9.0

Subtask #3 11.0 / 11.0

Subtask #4 23.0 / 23.0

Subtask #5 44.0 / 44.0

Subtask #1
13.0 / 13.0

Subtask #2
9.0 / 9.0

Subtask #3
11.0 / 11.0

Subtask #4
23.0 / 23.0

Subtask #5
44.0 / 44.0