#1959399

Solution for 2638: Hyperrectangle by btk

Source Code Status Test Cases
    Policy: public     Reviewed: 105    
00.25 sec    5636 KB    43 lines     852 bytes    2016-08-11 23:11
#include<bits/stdc++.h>

using namespace std;

struct I{I(){ios::sync_with_stdio(false);cin.tie(0);}}init;

typedef long long LL;
typedef vector<LL> V;
typedef vector<V> VV;
const LL MOD=1e9+7;

LL f(LL v,int n){
    if(n==0)return 1;
    else return v*f(v,n-1)%MOD;
}
int main(){
    int d;cin>>d;
    V l(d);for(auto &it:l)cin>>it;
    int s;cin>>s;
    sort(l.begin(),l.end());
    VV dp(2,V(s+1,0));
    dp[0][s]=1;
    for(int i=0;i<d;i++){
        VV nxt=dp;
        for(int j=0;j<2;j++)
            for(int k=l[i]+1;k<=s;k++){
                (nxt[1-j][k-l[i]]+=dp[j][k])%=MOD;
            }
        swap(nxt,dp);
    }
    LL res=0;
    for(int i=1;i<=s;i++){
        LL mul=f(i,d);
        V sgn({1,-1});
        for(int j=0;j<2;j++){
            (res+=MOD+sgn[j]*(mul*dp[j][i]%MOD))%=MOD;
        }
    }
    cout<<res<<endl;
    return 0;
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 33/33 C++14 CPU: 00.25 sec Memory: 5636 KB Length: 852 B 2016-08-11 23:11 2016-08-11 23:11
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.03 sec 3208 KB
Case #2: : Accepted 00.12 sec 4348 KB
Case #3: : Accepted 00.06 sec 3572 KB
Case #4: : Accepted 00.00 sec 3152 KB
Case #5: : Accepted 00.12 sec 4276 KB
Case #6: : Accepted 00.00 sec 3156 KB
Case #7: : Accepted 00.08 sec 3820 KB
Case #8: : Accepted 00.25 sec 5636 KB
Case #9: : Accepted 00.05 sec 3416 KB
Case #10: : Accepted 00.05 sec 3452 KB
Case #11: : Accepted 00.04 sec 3600 KB
Case #12: : Accepted 00.00 sec 3288 KB
Case #13: : Accepted 00.00 sec 3236 KB
Case #14: : Accepted 00.00 sec 3056 KB
Case #15: : Accepted 00.00 sec 3244 KB
Case #16: : Accepted 00.00 sec 3120 KB
Case #17: : Accepted 00.00 sec 3120 KB
Case #18: : Accepted 00.00 sec 3124 KB
Case #19: : Accepted 00.00 sec 3244 KB
Case #20: : Accepted 00.00 sec 3152 KB
Case #21: : Accepted 00.00 sec 3040 KB
Case #22: : Accepted 00.00 sec 3112 KB
Case #23: : Accepted 00.00 sec 3152 KB
Case #24: : Accepted 00.00 sec 3112 KB
Case #25: : Accepted 00.00 sec 3184 KB
Case #26: : Accepted 00.00 sec 3156 KB
Case #27: : Accepted 00.00 sec 3116 KB
Case #28: : Accepted 00.00 sec 3144 KB
Case #29: : Accepted 00.00 sec 3032 KB
Case #30: : Accepted 00.00 sec 3072 KB
Case #31: : Accepted 00.00 sec 3132 KB
Case #32: : Accepted 00.00 sec 3148 KB
Case #33: : Accepted 00.00 sec 3080 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags