Submission #1303736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303736		JahonaliX	Arranging Shoes (IOI19_shoes)	C++20	30 / 100	1134 ms	1052528 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

long long count_swaps(vector<int> s) {
    int n = s.size();
    vector<int> dp(1 << n, 100000000000000000ll);
    dp[0] = 0;
    for (int mask = 0; mask < (1 << n); ++mask) {
        int l = -1;
        for (int i = 0; i < n; ++i) {
            l += mask >> i & 1;
            int r = -1;
            for (int j = 0; j < n; ++j) {
                r += mask >> j & 1;
                if (mask >> i & 1 && mask >> j & 1 && s[i] == -s[j] && s[i] > 0) {
                    dp[mask] = min(dp[mask], dp[mask ^ (1 << i) ^ (1 << j)] + l + r + (r > l) - 1);
                }
            }
        }
    };
    return dp.back();
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:8:28: warning: overflow in conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '100000000000000000' to '1569325056' [-Woverflow]
    8 |     vector<int> dp(1 << n, 100000000000000000ll);
      |                            ^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15