# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1110005 | InvMOD | Skyscraper (JOI16_skyscraper) | C++14 | 2 ms | 2896 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;
#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
#define int long long
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}
const int N = 1e2+5;
const int L = 1e3+5;
const int mod = 1e9+7;
int n, MxL, a[N];
namespace Subtask1{
int answer, vis[10];
vector<int> vec;
void backtrack(int pos = 0){
if(pos == n){
int sum = 0;
for(int i = 1; i < n; i++){
sum += abs(vec[i] - vec[i-1]);
}
answer += (sum <= MxL);
return;
}
for(int i = 1; i <= n; ++i){
if(vis[i]) continue;
vis[i] = true;
vec.pb(a[i]);
backtrack(pos+1);
vec.pop_back();
vis[i] = false;
}
return;
}
void process()
{
answer = 0;
backtrack();
cout << answer <<"\n";
}
}
namespace Subtask3{
int dp[N][N][L][3];
void process()
{
// Thanks a Zero_OP <3
// Base case: [0]: just put insert a[1] into an cc, [1]: create new cc that contain endpoint (can locate at first or last)
dp[1][1][0][0] = 1;
dp[1][1][0][1] = 2;
for(int i = 1; i < n; i++){
for(int j = 1; j <= i; j++){
for(int cost = 0; cost <= MxL; cost++){
for(int m = 0; m <= 2; m++){
int nxt_cost = (2*j - m) * (a[i+1] - a[i]);
if(nxt_cost > MxL) continue;
// Insert a[i] to any exist cc
(dp[i+1][j][nxt_cost][m] += dp[i][j][cost][m] * (2*j - m)) %= mod;
// Insert a[i] to create endpoint
if(m < 2) (dp[i+1][j][nxt_cost][m+1] += dp[i][j][cost][m] * (2 - m)) %= mod;
// Insert a[i] to create new cc that does not has endpoint
(dp[i+1][j+1][nxt_cost][m] += dp[i][j][cost][m] * (j+1 - m)) %= mod;
// Insert a[i] to create new cc with endpoint
if(m < 2) (dp[i+1][j+1][nxt_cost][m+1] += dp[i][j][cost][m] * (2 - m)) %= mod;
// Merge 2 cc
if(j > 1) (dp[i+1][j-1][nxt_cost][m] += dp[i][j][cost][m] * (j-1)) %= mod;
}
}
}
}
int answer = 0;
for(int i = 0; i <= MxL; i++) (answer += dp[n][1][i][2]) %= mod;
cout << answer <<"\n";
return;
}
}
void solve()
{
cin >> n >> MxL;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a+1, a+1+n);
if(n < 8) Subtask1::process();
else
Subtask3::process();
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define name "InvMOD"
if(fopen(name".INP", "r")){
freopen(name".INP","r",stdin);
freopen(name".OUT","w",stdout);
}
int t = 1; //cin >> t;
while(t--) solve();
return 0;
}
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... |