# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
963273 | noobcodur | Skyscraper (JOI16_skyscraper) | C++14 | 231 ms | 186036 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ld = long double;
#define int long long
#define pii pair<int,int>
#define forn(i,j) for(int i = 0; i < j; ++i)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
const int MOD = 1e9+7; const int INF = 1e17+1; const int maxN = 2e5+1;
void setIO(string name){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(!name.empty()){
freopen((name + ".in").c_str(),"r",stdin);
freopen((name + ".out").c_str(),"w",stdout);
}
}
int a[14];
vector<vector<vi>> dp;
signed main(){
setIO("");
int n,L;
cin >> n >> L;
dp = vector<vector<vi>>((1 << n),vector<vi>(n,vi(L+1)));
forn(i,n){
cin >> a[i];
}
int res = 0;
forrange(mask,1,1 << n){
forn(i,n){
if(!(mask & (1 << i))) continue;
if(__builtin_popcount(mask) == 1){
dp[mask][i][0] = 1;
continue;
}
forn(j,n){
if(!(mask & (1 << j)) || j == i) continue;
int dist = abs(a[i]-a[j]);
forn(l,L-dist+1){
int mask2 = mask - (1 << i);
dp[mask][i][l+dist] += dp[mask2][j][l];
dp[mask][i][l+dist] %= MOD;
}
}
}
}
forn(i,n){
forn(l,L+1){
res += dp[(1 << n)-1][i][l];
res %= MOD;
}
}
cout << res << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |