oj.uz

Submission #889165

# Submission time Handle Problem Language Result Execution time Memory
889165 2023-12-19T04:43:27 Z Ghulam_Junaid Roller Coaster Railroad (IOI16_railroad) C++17
0 / 100
 33 ms 5832 KB 
#include <bits/stdc++.h>
// #include "grader.cpp"
using namespace std;

typedef long long ll;

const ll MXN = 16;
const ll MXP = (1 << 16);
ll dp[MXN][MXP];

ll plan_roller_coaster (vector<int> S, vector<int> T){
    vector<int> s, t;
    for (auto x : S) s.push_back(x);
    for (auto x : T) t.push_back(x);

    ll n = s.size();

    ll ans = 1e18;
    ll pw = (1 << n);
    for (ll mask = 1; mask < pw; mask++){
        for (ll start = 0; start < n; start++){
            if (((1 << start) & mask) == 0) continue;

            ll nmask = mask ^ (1 << start);
            if (nmask == 0)
                dp[start][mask] = 0;
            else{
                for (ll next = 0; next < n; next++){
                    if (((1 << next) & nmask) == 0) continue;

                    dp[start][mask] = dp[next][nmask] + max(0ll, (ll)(t[start] - s[next]));
                }
            }

            if (mask == pw - 1)
                ans = min(ans, dp[start][mask]);
        }
    }

    return ans;
}

// int main(){
//     return 0;
// }

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB n = 2
2 Correct 1 ms 2396 KB n = 2
3 Correct 0 ms 2396 KB n = 2
4 Correct 1 ms 2396 KB n = 2
5 Correct 1 ms 2396 KB n = 2
6 Correct 1 ms 2396 KB n = 2
7 Correct 0 ms 2396 KB n = 3
8 Incorrect 1 ms 2396 KB answer is not correct: 209372231 instead of 102553483
9 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB n = 2
2 Correct 1 ms 2396 KB n = 2
3 Correct 0 ms 2396 KB n = 2
4 Correct 1 ms 2396 KB n = 2
5 Correct 1 ms 2396 KB n = 2
6 Correct 1 ms 2396 KB n = 2
7 Correct 0 ms 2396 KB n = 3
8 Incorrect 1 ms 2396 KB answer is not correct: 209372231 instead of 102553483
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 5832 KB answer is not correct: 1 instead of 0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB n = 2
2 Correct 1 ms 2396 KB n = 2
3 Correct 0 ms 2396 KB n = 2
4 Correct 1 ms 2396 KB n = 2
5 Correct 1 ms 2396 KB n = 2
6 Correct 1 ms 2396 KB n = 2
7 Correct 0 ms 2396 KB n = 3
8 Incorrect 1 ms 2396 KB answer is not correct: 209372231 instead of 102553483
9 Halted 0 ms 0 KB -