/*
, .
-+-__. _.._ |_
| /_(_][_)[ )____
|
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pqgreater(x) x, vector<x>, greater<x>
#define decimal(x) cout<<fixed<<setprecision(x)
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define printtime cerr<<"\nTime elapsed: "<<1000*clock()/CLOCK_PER_SEC<<"ms\n";
#define sq(x) x*x
#define gc getchar//_unlocked
#define pc putchar//_unlocked
const int mod=1e9+7; //1e9+7 or 998244353, remove const if changing mods
const ld eps=1e-6;
const ld pi=3.1415926535897932384626433832795l;
const int dx4[]={-1, 0, 1, 0};
const int dy4[]={0, 1, 0, -1};
const int dx8[]={-1, 0, 1, 0, -1, -1, 1, 1};
const int dy8[]={0, 1, 0, -1, -1, 1, -1, 1};
const int dxhorse[]={-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[]={1, -1, 2, -2, 2, -2, 1, -1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ld sign(ld x){return (x>0)-(x<0);}
ll sign(ll x){return (x>0)-(x<0);}
int sign(int x){return (x>0)-(x<0);}
struct pt{
ld x, y;
pt(){}
pt(ld _x, ld _y):x(_x), y(_y){}
bool operator<(pt p){return tie(x, y)<tie(p.x, p.y);}
bool operator==(pt p){return tie(x, y)==tie(p.x, p.y);}
pt operator+(pt p){return {x+p.x, y+p.y};}
pt operator-(pt p){return {x-p.x, y-p.y};}
pt operator*(ld d){return {x*d, y*d};}
pt operator/(ld d){return {x/d, y/d};}
ld dot(pt p){return x*p.x+y*p.y;}
ld det(pt p){return x*p.y-y*p.x;}
ld cross(pt p, pt q){return (p-*this).det(q-*this);}
ld dist(){return sqrtl(sq(x)+sq(y));}
pt rot90(){return pt(-y, x);}
pt unit(){return *this/dist();}
ld angle(){return atan2(y, x);}
pt rot(ld an){return {x*cos(an)-y*sin(an), x*sin(an)+y*cos(an)};}
void read(){cin>>x>>y;}
void write(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
struct seg{
pt fi, sc;
seg(){}
seg(pt _fi, pt _sc):fi(_fi), sc(_sc){}
ld dist(pt C){
if(fi==sc) return (C-fi).dist();
ld d=pow((sc-fi).dist(), 2);
ld t=min(d, max((ld)0.0, (C-fi).dot(sc-fi)));
return ((C-fi)*d-(sc-fi)*t).dist()/d;
}
ld len(){return (fi-sc).dist();}
bool on_seg(pt C){
return abs(C.cross(fi, sc))<eps && (fi-C).dot(sc-C)<=eps;
}
vector<pt>intersect(seg rhs){
ld oa=rhs.fi.cross(rhs.sc, fi);
ld ob=rhs.fi.cross(rhs.sc, sc);
ld oc=fi.cross(sc, rhs.fi);
ld od=fi.cross(sc, rhs.sc);
if(sign(oa)*sign(ob)<0 && sign(oc)*sign(od)<0)
return {(fi*ob-sc*oa)/(ob-oa)};
vector<pt>ans;
if(rhs.on_seg(fi)) ans.push_back(fi);
if(rhs.on_seg(sc)) ans.push_back(sc);
if(on_seg(rhs.fi)) ans.push_back(rhs.fi);
if(on_seg(rhs.sc)) ans.push_back(rhs.sc);
return ans;
}
};
struct line{
ld a, b, c; //line a*x+b*y=c
line(pt p1, pt p2){
assert(!(p1==p2));
a=p2.y-p1.y;
b=p1.x-p2.x;
c=a*p1.x+b*p1.y;
}
line(){}
line(ld _a, ld _b, ld _c):a(_a), b(_b), c(_c){}
ld dist(pt p){
return fabs(a*p.x+b*p.y-c)/sqrtl(a*a+b*b);
}
pair<int, pt>intersect(line rhs){
ld dett=a*rhs.b-b*rhs.a;
if(fabs(dett)<=eps){
ld det2=c*rhs.a-a*rhs.c;
if(fabs(det2)<=eps)
return {-1, pt()}; //infinte
return {0, pt()}; //no sol
}
return {1, pt((c*rhs.b-rhs.c*b)/dett, (a*rhs.c-c*rhs.a)/dett)};
}
};
pt reflect(pt A, line L){
line perpendicular(-L.b, L.a, -L.b*A.x+L.a*A.y);
pt insect=perpendicular.intersect(L).second;
return insect*(ld)2.0-A;
}
struct mint{
int val;
mint(){val=0;}
mint(const ll& v){
val=(-mod<=v && v<mod)?v:v%mod;
if(val<0) val+=mod;
}
friend ostream& operator<<(ostream&os, const mint&a){return os<<a.val;}
friend bool operator==(const mint&a, const mint&b){return a.val==b.val;}
friend bool operator!=(const mint&a, const mint&b){return a.val!=b.val;}
friend bool operator<(const mint&a, const mint&b){return a.val<b.val;}
friend bool operator>(const mint&a, const mint&b){return a.val>b.val;}
friend bool operator<=(const mint&a, const mint&b){return a.val<=b.val;}
friend bool operator>=(const mint&a, const mint&b){return a.val>=b.val;}
mint operator-(){return mint(-val);}
mint& operator+=(const mint&m){if((val+=m.val)>=mod) val-=mod; return *this;}
mint& operator-=(const mint&m){if((val-=m.val)<0) val+=mod; return *this;}
mint& operator*=(const mint&m){val=(val*1ll*m.val)%mod; return *this;}
friend mint pow(mint a, int p){
mint ans=mint(1);
for(; p; p/=2, a*=a)
if(p%2==1) ans*=a;
return ans;
}
friend mint inv(const mint&a){return pow(a, mod-2);}
mint& operator/=(const mint&m){return (*this)*=inv(m);}
friend mint operator+(mint a, const mint&b){return a+=b;}
friend mint operator-(mint a, const mint&b){return a-=b;}
friend mint operator*(mint a, const mint&b){return a*=b;}
friend mint operator/(mint a, const mint&b){return a/=b;}
};
pair<int, int> extendedEuclid(int a, int b){
if(a==0){return {0, 1};}
pair<int, int>get=extendedEuclid(b%a, a);
pair<int, int>ans;
ans.first=get.second-(b/a)*get.first;
ans.second=get.first;
return ans;
}
int get(){
char c;
for(c=gc(); c<'0' || '9'<c; c=gc());
int nw=c-'0';
for(c=gc(); '0'<=c && c<='9'; c=gc())
nw=(nw<<3)+(nw<<1)+c-'0';
return nw;
}
char number[22];
void put(int nw){
int id=0;
for(; nw; nw/=10) number[id++]=nw%10+'0';
for(int i=id-1; i>=0; i--) pc(number[i]);
}
/////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////
int solve(); void precomp();
#define multitest 0
#define usecase 0
#define usedecimal 0
int main(){ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t=1;
if(multitest) cin>>t;
if(usedecimal) decimal(10);
precomp();
for(int tc=1; tc<=t; tc++){
if(multitest && usecase)
cout<<"Case #"<<tc<<": ";
solve();
}
}
mint dp[105][105][1005][3];
void precomp(){
for(int i=0; i<105; i++) for(int j=0; j<105; j++)
for(int k=0; k<1005; k++) for(int m=0; m<3; m++)
dp[i][j][k][m]=mint(0);
return;
}
//idx, n_cc, sum, endpoints
int n, l, a[105];
int solve(){
scanf("%d%d", &n, &l);
for(int i=0; i<n; i++) scanf("%d", &a[i]);
sort(a, a+n);
if(n==1){printf("1\n"); return 0;}
a[n]=100000;
if(a[1]-a[0]<=l)
dp[1][1][a[1]-a[0]][1]=2; //put at edge
if(2*(a[1]-a[0])<=l)
dp[1][1][2*(a[1]-a[0])][0]=1; //put at mid
for(int i=1; i<n; i++){
int dif=a[i+1]-a[i];
for(int j=1; j<=i; j++) for(int k=0; k<=l; k++) for(int m=0; m<3; m++){
if(dp[i][j][k][m]==mint(0)) continue;
//put at end
if(m<2 && k+dif*(2*j-m-1)<=l){
if(i==n-1)
dp[i+1][j][k+dif*(2*j-m-1)][m+1]+=dp[i][j][k][m]*mint(2-m)*mint(j);
else if(m==0 || j>1)
dp[i+1][j][k+dif*(2*j-m-1)][m+1]+=dp[i][j][k][m]*mint(2-m)*mint(j-m); //add with cc bf end
if(k+dif*(2*j-m+1)<=l)
dp[i+1][j+1][k+dif*(2*j-m+1)][m+1]+=dp[i][j][k][m]*mint(2-m); //create at end
}
//create new
if(k+dif*(2*j-m+2)<=l)
dp[i+1][j+1][k+dif*(2*j-m+2)][m]+=dp[i][j][k][m];
//stick one
if(k+dif*(2*j-m)<=l)
dp[i+1][j][k+dif*(2*j-m)][m]+=dp[i][j][k][m]*mint(2*j-m);
//merge 2 cc
if(k+dif*(2*j-m-2)<=l && j>=2 && !(i!=n-1 && j==2 && m==2)){
if(m==0)
dp[i+1][j-1][k+dif*(2*j-m-2)][m]+=dp[i][j][k][m]*mint(j)*mint(j-1);
if(m==1)
dp[i+1][j-1][k+dif*(2*j-m-2)][m]+=dp[i][j][k][m]*mint(j-1)*mint(j-1);
if(m==2)
if(i==n-1)
dp[i+1][j-1][k+dif*(2*j-m-2)][m]+=dp[i][j][k][m];
else
dp[i+1][j-1][k+dif*(2*j-m-2)][m]+=dp[i][j][k][m]*mint(j-2)*mint(j-1);
}
}
}
mint ans=mint(0);
for(int i=0; i<=l; i++)
ans+=dp[n][1][i][2];
cout<<ans<<endl;
return 0;
}
Compilation message
skyscraper.cpp: In function 'int solve()':
skyscraper.cpp:241:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if(m==2)
^
skyscraper.cpp:207:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &l);
~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:208:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<n; i++) scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
130424 KB |
Output is correct |
| 2 |
Correct |
99 ms |
130424 KB |
Output is correct |
| 3 |
Correct |
93 ms |
130424 KB |
Output is correct |
| 4 |
Correct |
94 ms |
130552 KB |
Output is correct |
| 5 |
Correct |
95 ms |
130424 KB |
Output is correct |
| 6 |
Correct |
92 ms |
130424 KB |
Output is correct |
| 7 |
Correct |
99 ms |
130424 KB |
Output is correct |
| 8 |
Correct |
94 ms |
130424 KB |
Output is correct |
| 9 |
Correct |
99 ms |
130428 KB |
Output is correct |
| 10 |
Correct |
102 ms |
130428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
130552 KB |
Output is correct |
| 2 |
Correct |
99 ms |
130424 KB |
Output is correct |
| 3 |
Correct |
104 ms |
130296 KB |
Output is correct |
| 4 |
Correct |
98 ms |
130424 KB |
Output is correct |
| 5 |
Correct |
98 ms |
130424 KB |
Output is correct |
| 6 |
Correct |
96 ms |
130552 KB |
Output is correct |
| 7 |
Correct |
94 ms |
130424 KB |
Output is correct |
| 8 |
Correct |
97 ms |
130424 KB |
Output is correct |
| 9 |
Correct |
96 ms |
130424 KB |
Output is correct |
| 10 |
Correct |
98 ms |
130428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
130424 KB |
Output is correct |
| 2 |
Correct |
99 ms |
130424 KB |
Output is correct |
| 3 |
Correct |
93 ms |
130424 KB |
Output is correct |
| 4 |
Correct |
94 ms |
130552 KB |
Output is correct |
| 5 |
Correct |
95 ms |
130424 KB |
Output is correct |
| 6 |
Correct |
92 ms |
130424 KB |
Output is correct |
| 7 |
Correct |
99 ms |
130424 KB |
Output is correct |
| 8 |
Correct |
94 ms |
130424 KB |
Output is correct |
| 9 |
Correct |
99 ms |
130428 KB |
Output is correct |
| 10 |
Correct |
102 ms |
130428 KB |
Output is correct |
| 11 |
Correct |
96 ms |
130552 KB |
Output is correct |
| 12 |
Correct |
99 ms |
130424 KB |
Output is correct |
| 13 |
Correct |
104 ms |
130296 KB |
Output is correct |
| 14 |
Correct |
98 ms |
130424 KB |
Output is correct |
| 15 |
Correct |
98 ms |
130424 KB |
Output is correct |
| 16 |
Correct |
96 ms |
130552 KB |
Output is correct |
| 17 |
Correct |
94 ms |
130424 KB |
Output is correct |
| 18 |
Correct |
97 ms |
130424 KB |
Output is correct |
| 19 |
Correct |
96 ms |
130424 KB |
Output is correct |
| 20 |
Correct |
98 ms |
130428 KB |
Output is correct |
| 21 |
Correct |
97 ms |
130424 KB |
Output is correct |
| 22 |
Correct |
146 ms |
130424 KB |
Output is correct |
| 23 |
Correct |
124 ms |
130472 KB |
Output is correct |
| 24 |
Correct |
120 ms |
130400 KB |
Output is correct |
| 25 |
Correct |
126 ms |
130424 KB |
Output is correct |
| 26 |
Correct |
122 ms |
130552 KB |
Output is correct |
| 27 |
Correct |
116 ms |
130424 KB |
Output is correct |
| 28 |
Correct |
112 ms |
130424 KB |
Output is correct |
| 29 |
Correct |
127 ms |
130424 KB |
Output is correct |
| 30 |
Correct |
127 ms |
130424 KB |
Output is correct |
