Submission #1032012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032012		isaachew	Magneti (COCI21_magneti)	C++17	110 / 110	194 ms	8640 KiB

Main

#include <bits/stdc++.h>
/*
 The order of the magnets?
 Placing a smaller magnet
 
 Place last magnet -> place smaller magnets but in two components, each ending in a magnet
 Keep track of currently used space?
 
 Connected component DP
 */
int mod=1000000007;
long long binexp(long long a,int p=mod-2){
    long long r=1;
    while(p){
        if(p&1)r*=a;
        a*=a;
        r%=mod;
        a%=mod;
        p/=2;
    }
    return r;
}
int main(){
    int n,l;
    std::cin>>n>>l;
    std::vector<int> rads;
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        rads.push_back(x);
    }
    std::sort(rads.begin(),rads.end());
    std::vector<std::vector<long long>> spaces(n,std::vector<long long>(l+1));//space used up by magnets
    spaces[0][1]=1;//(0+1)ccs, 1 space used (1st magnet)
    for(int i=1;i<n;i++){
        std::vector<std::vector<long long>> nspaces(n,std::vector<long long>(l+1));
        for(int j=0;j<n;j++){
            for(int k=0;k<=l;k++){
                if(k+2*rads[i]-1<=l&&j>0){
                    nspaces[j-1][k+2*rads[i]-1]+=spaces[j][k]*j;//merge components, 2r-1 space
                    nspaces[j-1][k+2*rads[i]-1]%=1000000007;
                }
                if(k+rads[i]<=l){
                    nspaces[j][k+rads[i]]+=2*(j+1)*spaces[j][k];//at end, r space
                    nspaces[j][k+rads[i]]%=1000000007;
                }
                if(k+1<=l&&j+1<n){
                    nspaces[j+1][k+1]+=(j+2)*spaces[j][k];//new component, 1 space
                    nspaces[j+1][k+1]%=1000000007;
                }
            }
        }
        spaces=nspaces;
    }
    long long curch=1;
    long long result=0;
    for(int i=0;i<l;i++){//C((l-i)+n,n)
        result+=spaces[0][l-i]*curch;//1cc, l-i used space
        /*
         (i+n)!/(n)!(i)!
         */
        result%=mod;
        curch*=(i+n)+1;
        curch%=mod;
        curch*=binexp(i+1);
        curch%=mod;
    }
    std::cout<<result<<'\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50