#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct BitSet
{
unsigned long long A[32];
unsigned long long h;
BitSet()
{
h = 0;
fill_n(A, 32, 0ull);
}
bool operator<(const BitSet& o)const
{
if (h != o.h)
return h < o.h;
for (int i = 0; i < 32; i++)
{
if (A[i] != o.A[i])
return A[i] < o.A[i];
}
return false;
}
void set(int i)
{
int t = i / 64;
i %= 64;
A[t] |= (1ull << i);
h ^= (1ull << i);
return;
}
void unset(int i)
{
int t = i / 64;
i %= 64;
A[t] &= (~(1ull << i));
h ^= (1ull << i);
return;
}
void andas(BitSet &o)
{
h =
(A[0] &= o.A[0]) ^
(A[1] &= o.A[1]) ^
(A[2] &= o.A[2]) ^
(A[3] &= o.A[3]) ^
(A[4] &= o.A[4]) ^
(A[5] &= o.A[5]) ^
(A[6] &= o.A[6]) ^
(A[7] &= o.A[7]) ^
(A[8] &= o.A[8]) ^
(A[9] &= o.A[9]) ^
(A[10] &= o.A[10]) ^
(A[11] &= o.A[11]) ^
(A[12] &= o.A[12]) ^
(A[13] &= o.A[13]) ^
(A[14] &= o.A[14]) ^
(A[15] &= o.A[15]) ^
(A[16] &= o.A[16]) ^
(A[17] &= o.A[17]) ^
(A[18] &= o.A[18]) ^
(A[19] &= o.A[19]) ^
(A[20] &= o.A[20]) ^
(A[21] &= o.A[21]) ^
(A[22] &= o.A[22]) ^
(A[23] &= o.A[23]) ^
(A[24] &= o.A[24]) ^
(A[25] &= o.A[25]) ^
(A[26] &= o.A[26]) ^
(A[27] &= o.A[27]) ^
(A[28] &= o.A[28]) ^
(A[29] &= o.A[29]) ^
(A[30] &= o.A[30]) ^
(A[31] &= o.A[31]);
}
int First(int t)
{
int ret = 64 * t;
for (; t < 32; t++)
{
if (A[t] == 0)
{
ret += 64;
}
else
{
return ret + __builtin_ctzll(A[t]);
}
}
return ret;
}
};
BitSet ok[2000];
map<BitSet, int>M;
int dp(BitSet x, int nuo = 0)
{
int i = x.First(nuo / 64);
if (i >= 2000)
return 0;
int &ans = M[x];
if (ans != 0)
return ans;
x.unset(i);
ans = dp(x, i + 1);
x.andas(ok[i]);
ans = max(ans, 1 + dp(x, i + 1));
return ans;
}
int maximum_deevs(vector<int> y)
{
BitSet deevs;
for (ll i = 0; i < (ll)y.size(); i++)
{
ll k = i + 1;
for (ll j = i + 1; j < (ll)y.size(); j++)
{
if ((y[j] - y[i]) * (k - i) >= (y[k] - y[i]) * (j - i))
k = j;
if (k != j)
ok[i].set(j);
}
deevs.set(i);
}
return dp(deevs);
}
int main()
{
cout << maximum_deevs({ 6, 1, 5, 2, 3, 1}) << endl;//3
cout << maximum_deevs({ 0, 1, 2}) << endl;//1
}/**/
Compilation message
/tmp/ccs2yICQ.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccLIMU7p.o:mountains.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
