답안 #337078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337078	2020-12-18T06:42:33 Z	blue	선물상자 (IOI15_boxes)	C++11	20 / 100	1 ms	512 KB

boxes

#include "boxes.h"
#include <iostream>
using namespace std;

//#teams, capacity, #sections, position of each team
long long delivery(int N, int K, int L, int positions[])
{
    long long dp_inc[N]; //minimum time needed to cover all 0, 1, ... i and end up at positions[[i]

    dp_inc[0] = positions[0];
    for(int i = 1; i < N; i++)
    {
        if(i % K == 0)
        {
            dp_inc[i] = dp_inc[i-1] + positions[i-1] + positions[i];
        }
        else
        {
            dp_inc[i] = dp_inc[i-1] + (positions[i] - positions[i-1]);
        }
    }

    // for(int i = 0; i < N; i++) cout << dp_inc[i] << ' ';
    // cout << '\n';

    long long dp_dec[N];

    dp_dec[N-1] = L - positions[N-1];
    for(int i = N-2; i >= 0; i--)
    {
        if((N - 1 - i) % K == 0)
        {
            dp_dec[i] = dp_dec[i+1] + (L - positions[i+1]) + (L - positions[i]);
        }
        else
        {
            dp_dec[i] = dp_dec[i+1] + (positions[i+1] - positions[i]);
        }
    }


    //for(int i = 0; i < N; i++) cout << dp_dec[i] << ' ';
    //cout << '\n';

    long long res = (long long)(1000 * 1000 * 1000) * (long long)(1000 * 1000 * 1000);
    for(int i = 0; i < N-1; i++)
        res = min(res, dp_inc[i] + dp_dec[i+1] + positions[i] + (L - positions[i+1]));

    for(int i = 0; i < N; i++)
    {
        res = min(res, dp_inc[i] + dp_dec[i]);
    }

    res = min(res, dp_inc[N-1] + min(positions[N-1], L - positions[N-1]));
    res = min(res, dp_dec[0] + min(positions[0], L - positions[0]));

    return res;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct

Subtask #3

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Incorrect	0 ms	364 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	0 ms	364 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Incorrect	0 ms	364 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	0 ms	364 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Incorrect	0 ms	364 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	0 ms	364 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Incorrect	0 ms	364 KB	Output isn't correct
21	Halted	0 ms	0 KB	-