oj.uz

Submission #138863

# Submission time Handle Problem Language Result Execution time Memory
138863 2019-07-30T15:20:47 Z RiscadoA Roller Coaster Railroad (IOI16_railroad) C++14
0 / 100
 80 ms 7300 KB 
#include "railroad.h"

const int INF = 1000000001;
const int MAX_N = 16;
const int MAX_MASK = 0xFFFF;
int N, S[MAX_N], T[MAX_N];

long long dp[MAX_N + 1][MAX_MASK];

inline long long max(long long a, long long b)
{
        return a > b ? a : b;
}

inline long long min(long long a, long long b)
{
        return a < b ? a : b;
}

long long calc(int next, int mask)
{
        if (dp[next][mask] == -1) {
                int s;
                if (next == MAX_N)
                        s = 0;
                else
                        s = S[next];

                long long v = 0x7FFFFFFFFFFFFFFF;
                for (int i = 0, j = 1; i < MAX_N; ++i, j <<= 1)
                        if (mask & j)
                                v = min(v, max(0, T[i] - s) + calc(i, mask & (~j)));
                dp[next][mask] = v;
        }

        return dp[next][mask];
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
        N = (int)s.size();
        if (N > 16)
                return 0;
        for (int i = 0; i < N; ++i) {
                S[i] = s[i];
                T[i] = t[i];
        }

        for (int i = 0; i <= N; ++i) {
                dp[i][0] = 0;
                for (int m = 1; m < MAX_MASK; ++m)
                        dp[i][m] = -1;
        }
        return calc(MAX_N, 0xFFFF);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB n = 2
2 Correct 3 ms 1784 KB n = 2
3 Correct 3 ms 1912 KB n = 2
4 Correct 3 ms 1784 KB n = 2
5 Correct 3 ms 1912 KB n = 2
6 Incorrect 3 ms 1912 KB answer is not correct: 0 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB n = 2
2 Correct 3 ms 1784 KB n = 2
3 Correct 3 ms 1912 KB n = 2
4 Correct 3 ms 1784 KB n = 2
5 Correct 3 ms 1912 KB n = 2
6 Incorrect 3 ms 1912 KB answer is not correct: 0 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 7300 KB n = 199999
2 Incorrect 80 ms 7292 KB answer is not correct: 0 instead of 1
3 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1912 KB n = 2
2 Correct 3 ms 1784 KB n = 2
3 Correct 3 ms 1912 KB n = 2
4 Correct 3 ms 1784 KB n = 2
5 Correct 3 ms 1912 KB n = 2
6 Incorrect 3 ms 1912 KB answer is not correct: 0 instead of 523688153
7 Halted 0 ms 0 KB -