이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIM 110
#define DIML 1010
#define MOD 1000000007
using namespace std;
int dp[DIM][DIM][DIML][3],v[DIM];
int n,i,comp,nr,cost,L;
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>L;
for (i=1;i<=n;i++)
cin>>v[i];
sort (v+1,v+n+1);
/// dp[i][j][l][0/1/2] - nr de permutari cu i elemente, j comp conexe, cost l
/// si 0 1 sau 2 capete fixate
dp[0][0][0][0] = 1;
for (i=1;i<=n;i++)
for (comp=1;comp<=n;comp++)
for (cost=0;cost<=L;cost++)
for (nr=0;nr<=2;nr++){ /// marginile
/// creez componenta noua
int val = (2 * (comp-1) - nr) * (v[i] - v[i-1]);
if (val <= cost){
dp[i][comp][cost][nr] += 1LL * dp[i-1][comp-1][cost-val][nr] * (comp - nr) % MOD;
if (dp[i][comp][cost][nr] >= MOD)
dp[i][comp][cost][nr] -= MOD;
}
/// leg de o componenta
val = (2 * comp - nr) * (v[i] - v[i-1]);
if (val <= cost){
dp[i][comp][cost][nr] += 1LL * dp[i-1][comp][cost-val][nr] * (comp * 2 - nr) % MOD;
if (dp[i][comp][cost][nr] >= MOD)
dp[i][comp][cost][nr] -= MOD;
}
/// unesc doua componente
val = (2 * (comp + 1) - nr) * (v[i] - v[i-1]);
if (val <= cost){
dp[i][comp][cost][nr] += 1LL * dp[i-1][comp+1][cost-val][nr] * comp % MOD;
if (dp[i][comp][cost][nr] >= MOD)
dp[i][comp][cost][nr] -= MOD;
}
/// creez componenta in margine
val = (2 * (comp-1) - (nr - 1)) * (v[i] - v[i-1]);
if (val <= cost && nr >= 1){
dp[i][comp][cost][nr] += 1LL * dp[i-1][comp-1][cost-val][nr-1] * (2 - (nr-1)) % MOD;
if (dp[i][comp][cost][nr] >= MOD)
dp[i][comp][cost][nr] -= MOD;
}
/// leg de o componenta si fixez marginea
val = (2 * comp - (nr - 1)) * (v[i] - v[i-1]);
if (val <= cost && nr >= 1){
dp[i][comp][cost][nr] += 1LL * dp[i-1][comp][cost-val][nr-1] * (2 - (nr-1)) % MOD;
if (dp[i][comp][cost][nr] >= MOD)
dp[i][comp][cost][nr] -= MOD;
}
}
long long sol = 0;
for (i=0;i<=L;i++)
sol = (sol + dp[n][1][i][2]) % MOD;
cout<<sol;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |