题目大意
一个舰队有$n$艘飞船，每艘飞船有一个武力值$w_i$，现需要把飞船分成两队。
对于任意两艘不在同一队的飞船，且它们的武力值之和不小于$m$，那么这两艘飞船配合默契。
求出最多能有多少对飞船配合默契，并求出有多少种分队方案可以达到此效果。
$n leq 2000,w_i leq 10^6,m leq 2*10^6$
题解
看完题第一步显然是给 $w_i$ 排个序了显然将来会有用的
观察题目可知，这个数据范围仿佛在呼唤一个 $O(n^2)$ 做法，比如dp。
但是由于飞船之间的是否默契情况，貌似并没有什么好的dp方法。
观察排好序的 $w_i$ ，可以发现，与每个飞船配合默契的飞船都是一段后缀。
那么考虑据此搞出一个方便dp的东西来。
于是考虑建出一个遍历节点的顺序。
考虑区间 $[1,n]$ 的情况:
取出 $w_1$ 和 $w_n$ ，计算它们的和 $sum$ 与 $m$ 的大小关系。
如果 $s < m$，那么显然 $w_1$ 和目前区间内剩下的位置都无法默契了，因此咱们将 $w_1$ 加入序列，递归做 $[2,n]$。
如果 $s geq m$，那么 $w_n$ 和目前区间内剩下的位置都配合默契，因此咱们将 $w_n$ 加入序列，递归做 $[1,n-1]$。
然后得到了一个序列！
考虑它的含义，对于每个位置，要么和后面的位置均不默契，要么均默契。
于是得到了一个可以用来dp的条件很强的顺序。
那么翻转整个新数组，按顺序dp。
设$f[i][j]$代表，考虑完前$i$艘飞船，其中有$j$艘属于$A$队的最大默契数。
设当前位置与前面的位置均默契时，$c[i]=1$，否则$c[i]=0$，那么有转移方程:
$$f[i][j]=max(f[i-1][j-1]+c[i]*(i-j), f[i-1][j]+c[i]*j)$$
方案可以同理统计。
于是做完了!
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0' || '9'<ch)ch=getchar();
while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
return x;
}
typedef long long ll;
const int N=2009;
const int md=1e9+7;
int n,m,ans;
int w[N],c[N];
ll f[N][N],g[N][N];
inline bool chkmin(ll &a,ll b){if(a>b)return a=b,1;return 0;}
inline bool chkmax(ll &a,ll b){if(a<b)return a=b,1;return 0;}
inline ll qpow(ll a,ll b)
{
ll ret=1;
while(b)
{
if(b&1)ret=ret*a%md;
a=a*a%md;b>>=1;
}
return ret;
}
inline void update(ll &a,ll &b,ll c,ll d)
{
if(chkmax(a,c))b=d;
else if(a==c)(b+=d)%=md;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
w[i]=read();
sort(w+1,w+n+1);
int l=1,r=n;
for(int i=n;i>=1;i--)
{
if(w[l]+w[r]<m)
c[i]=0,l++;
else
c[i]=1,r--;
}
memset(f,128,sizeof(f));
f[0][0]=0;g[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++)
{
f[i][j]=f[i-1][j]+c[i]*j;g[i][j]=g[i-1][j];
if(j)
update(f[i][j],g[i][j],f[i-1][j-1]+c[i]*(i-j),g[i-1][j-1]);
}
ll ans=-1e18,cnt=0;
for(int i=0;i<=n;i++)
update(ans,cnt,f[n][i],g[n][i]);
printf("%lld %lld
",ans,cnt);
return 0;
}