Submission #1253293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253293		pasta	Skyscraper (JOI16_skyscraper)	C++17	Compilation error	0 ms	0 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

// #pragma GCC optimize("Ofast,unroll-loops,inline")   
// #pragma GCC target("avx2,bmi2,lzcnt")  

#define pb		push_back
#define all(x)	x.begin(), x.end()
// #define int ll
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn = 20;
const int inf = 1e9 + 10;
const int mod = 1e9 + 7;
const int LOG = 21;

int n, L, a[maxn], b[maxn], dp[(1 << 20)][20][120];

int main() {
	fast_io;
	cin >> n >> L;
	if (n == 1) {
		cout << 1 << '\n';
		return 0;
	}

	for(ll i = 0; i < n; i ++)
		cin >> a[i];
	if (n < 9) {
		for(ll i = 0; i < n; i ++)
			b[i] = i;
		ll ans = 0;
		while(true) {
			ll dif = 0;
			for (ll i = 1; i < n; i ++)
				dif += abs(a[b[i]] - a[b[i - 1]]);
			if (dif <= L)
				ans ++;
			if (next_permutation(b, b + n))
				ans = ans; 
			else
				break;
		}
		return cout << ans << "\n", 0;
	}
	

	for (int msk = 0; msk < (1 << n); msk++) {
		if (__builtin_popcount(msk) == 1)
			continue;

		if (__builtin_popcount(msk) == 2) {
			vector <ll> per;
			for(ll i = 0; i < n; i ++){
				if ((1 << i) & msk)
					per.pb(i);
			}
			ll d = abs(a[per[0]] - a[per[1]]);
			if(d > L)
				continue;
			dp[msk][per[0]][d] = 1;
			dp[msk][per[1]][d] = 1;
			continue;
		}

		for (int i = 0; i < n; i++) {
			if (((1 << i) & msk) == 0) continue;
			for (int j = 0; j < n; j++) {
				if (((1 << j) & msk) ==0) continue;
				if (j == i) continue;

				for (int l = 0; l <= L; l++) {
					if (l + abs(a[i] - a[j]) > L) continue;
					dp[msk][i][l + abs(a[i] - a[j])] += dp[msk ^ (1 << i)][j][l];
					dp[msk][i][l + abs(a[i] - a[j])] %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		for (int cost = 0; cost <= L; cost++) {
			ans += dp[(1 << n) - 1][i][cost];
			ans %= mod;
		}
	}
	cout << ans << '\n';
}

Compilation message (stderr)

/tmp/cc0PVoh7.o: in function `main':
skyscraper.cpp:(.text.startup+0x13): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x33): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc0PVoh7.o
skyscraper.cpp:(.text.startup+0x3d): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x48): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x58): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/cc0PVoh7.o
skyscraper.cpp:(.text.startup+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc0PVoh7.o
skyscraper.cpp:(.text.startup+0x77): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/cc0PVoh7.o
skyscraper.cpp:(.text.startup+0xa6): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc0PVoh7.o
skyscraper.cpp:(.text.startup+0x118): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/cc0PVoh7.o
skyscraper.cpp:(.text.startup+0x23b): relocation truncated to fit: R_X86_64_PC32 against symbol `L' defined in .bss section in /tmp/cc0PVoh7.o
skyscraper.cpp:(.text.startup+0x2c7): additional relocation overflows omitted from the output
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status