oj.uz

Submission #341779

# Submission time Handle Problem Language Result Execution time Memory
341779 2020-12-31T01:45:01 Z rrrr10000 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 425636 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

int main(){
    ll n,L;cin>>n>>L;
    if(n==1)dame(1);
    vi v(n);rep(i,n)cin>>v[i];
    rsort(v);
    ll k=n+1,mx=3000*n+5;
    vvvvi dp(2,vvvi(2,vvi(k,vi(mx))));
    dp[0][0][0][0]=1;
    ll ans=0;
    rep(i,n){
        vvvvi ndp(2,vvvi(2,vvi(k,vi(mx))));
        rep(a,2)rep(b,2)rep(j,k)rep(t,mx)if(dp[a][b][j][t]){
            if(j>1)ndp[a][b][j-1][t-2*v[i]]+=dp[a][b][j][t]*((j-a-b)*(j-b-1)+b*(j-a-b))%mod;
            if(i==n-1&&a+b==2&&j==2&&t-2*v[i]<=L)ans+=dp[a][b][j][t];
            ndp[a][b][j][t]+=dp[a][b][j][t]*(j*2-a-b)%mod;
            if(a==0&&t-v[i]>=0)ndp[a+1][b][j][t-v[i]]+=dp[a][b][j][t]*(j-a-b)%mod;
            if(b==0&&t-v[i]>=0)ndp[a][b+1][j][t-v[i]]+=dp[a][b][j][t]*(j-a-b)%mod;
            if(i==n-1&&a+b==1&&j==1&&t-v[i]<=L)ans+=dp[a][b][j][t];
            if(j!=k-1)ndp[a][b][j+1][t+2*v[i]]+=dp[a][b][j][t];
            if(j!=k-1&&a==0)ndp[a+1][b][j+1][t+v[i]]+=dp[a][b][j][t];
            if(j!=k-1&&b==0)ndp[a][b+1][j+1][t+v[i]]+=dp[a][b][j][t];
        }
        rep(a,2)rep(b,2)rep(j,k)rep(t,mx)dp[a][b][j][t]=ndp[a][b][j][t]%mod;
        ans%=mod;
    }
    out(ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 2 ms 1900 KB Output is correct
3 Correct 4 ms 3540 KB Output is correct
4 Correct 24 ms 11476 KB Output is correct
5 Correct 50 ms 19296 KB Output is correct
6 Correct 58 ms 19172 KB Output is correct
7 Correct 52 ms 19168 KB Output is correct
8 Correct 50 ms 19192 KB Output is correct
9 Correct 49 ms 19172 KB Output is correct
10 Correct 51 ms 19168 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 41124 KB Output is correct
2 Correct 240 ms 55256 KB Output is correct
3 Correct 235 ms 55312 KB Output is correct
4 Correct 232 ms 55204 KB Output is correct
5 Correct 238 ms 55280 KB Output is correct
6 Correct 230 ms 55244 KB Output is correct
7 Correct 229 ms 55388 KB Output is correct
8 Correct 230 ms 55380 KB Output is correct
9 Correct 234 ms 55204 KB Output is correct
10 Correct 239 ms 55196 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 2 ms 1900 KB Output is correct
3 Correct 4 ms 3540 KB Output is correct
4 Correct 24 ms 11476 KB Output is correct
5 Correct 50 ms 19296 KB Output is correct
6 Correct 58 ms 19172 KB Output is correct
7 Correct 52 ms 19168 KB Output is correct
8 Correct 50 ms 19192 KB Output is correct
9 Correct 49 ms 19172 KB Output is correct
10 Correct 51 ms 19168 KB Output is correct
11 Correct 154 ms 41124 KB Output is correct
12 Correct 240 ms 55256 KB Output is correct
13 Correct 235 ms 55312 KB Output is correct
14 Correct 232 ms 55204 KB Output is correct
15 Correct 238 ms 55280 KB Output is correct
16 Correct 230 ms 55244 KB Output is correct
17 Correct 229 ms 55388 KB Output is correct
18 Correct 230 ms 55380 KB Output is correct
19 Correct 234 ms 55204 KB Output is correct
20 Correct 239 ms 55196 KB Output is correct
21 Execution timed out 2111 ms 425636 KB Time limit exceeded
22 Halted 0 ms 0 KB -