oj.uz

Submission #731695

# Submission time Handle Problem Language Result Execution time Memory
731695 2023-04-27T19:50:30 Z Huseyn123 Magneti (COCI21_magneti) C++14
110 / 110
 302 ms 205768 KB 
#include <bits/stdc++.h>
#define MAX 300001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
    for(int i=0;i<b;i++){\
        cin >> a[i];\
    }\
}
#define inputvec(a,b){\
    for(int i=0;i<b;i++){\
        ll num;\
        cin >> num;\
        a.pb(num);\
    }\
}
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << "\n";\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << x << " ";\
    }\
    cout << "\n";\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
ll n,q,t=1,m,n2,m2,k,cnt=0,a[MAX],d[MAX],d2[MAX],x,y,z,x2,y2,z2,res1=0,cnt1,cnt2,cnt3;
ll c[1001][1001];
ll c2[1001][1001];
ll fact[MAX];
ll inv_fact[MAX];
//char c;
string str[MAX];
string s1,s2;
const int mod = 998244353;
ll modmul(ll x,ll y,ll md){
    if(y==1){
        return x;
    }
    if(y%2){
        return (x+modmul(x,y-1,md))%md;
    }
    else{
        return (modmul((x+x)%md,y/2,md))%md;
    }
}
ll powmod(ll x,ll y,ll md){
    x%=md;
    if(x==0){
        return 0;
    }
    ll res=1;
    while(y){
        if(y%2==1){
            res*=x;
            res%=md;
        }
        x*=x;
        x%=md;
        y/=2;
    }
    return res;
}
ll pow2(ll x,ll y){
    if(x==0){
        return 0;
    }
    ll res=1;
    while(y>0){
        if(y%2==1){
            if(res>=1e18/x){
                res=1e18;
            }
            else{
                res*=x;
            }
        }
        if(x>=1e18/x){
            x=1e18;
        }
        else{
            x*=x;
        }
        y/=2;
    }
    return res;
}
ll inv(ll n,ll md){
    return powmod(n,md-2,md);
}
ll nCkm(ll n,ll k,ll md){
    if(n-k<0){
        return 0;
    }
    return (((fact[n]*inv(fact[k],md))%md)*inv(fact[n-k],md))%md;
}
ll nCk(ll x,ll y){
    if(x<y){
        return 0;
    }
    ll res=1;
    if(y>x-y){
        for(int i=y+1;i<=x;i++){
            res*=i;
        }
        for(int i=2;i<=x-y;i++){
            res/=i;
        }
    }
    else{
        for(int i=x-y+1;i<=x;i++){
            res*=i;
        }
        for(int i=2;i<=y;i++){
            res/=i;
        }
    }
    return res;
}
ll countbits(ll x){
    ll cnt=0;
    while(x){
        cnt+=x&1;
        x>>=1;
    }
    return cnt;
}
ll gcd(ll x,ll y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
ll lcm(ll x,ll y){
    return x*y/gcd(x,y);
}
bool alpha(char c1,char c2){
    ll h1,h2;
    if(c1>='a'){
        h1=c1-'a';
    }
    else{
        h1=c1-'A';
    }
    if(c2>='a'){
        h2=c2-'a';
    }
    else{
        h2=c2-'A';
    }
    if(h1==h2){
        return c1<c2;
    }
    else{
        return h1<h2;
    }
}
ll dx[4]={1,0,0,-1};
ll dy[4]={0,1,-1,0};
struct custom_hash {
   static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
struct data{
    ll dt[2][2];
};
data f(data x,data y){
    data res;
    res.dt[0][0]=res.dt[0][1]=res.dt[1][0]=res.dt[1][1]=INF;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            ll h=x.dt[i][0];
            if(y.dt[1][j]<=INF-h){
                h+=y.dt[1][j];
            }
            else{
                h=INF;
            }
            res.dt[i][j]=min(res.dt[i][j],h);
            h=x.dt[i][1];
            if(y.dt[0][j]<=INF-h){
                h+=y.dt[0][j];
            }
            else{
                h=INF;
            }
            res.dt[i][j]=min(res.dt[i][j],h);
            h=x.dt[i][1];
            if(y.dt[1][j]<=INF-h){
                h+=y.dt[1][j];
            }
            else{
                h=INF;
            }
            res.dt[i][j]=min(res.dt[i][j],h);
        }
    }
    return res;
}
struct segtree{
    int size;
    vector<data> dp;
    void build(vector<ll> &a,int x,int lx,int rx){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                dp[x].dt[1][1]=a[lx];
                dp[x].dt[0][0]=0;
            }
            return;
        }
        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        dp[x]=f(dp[2*x+1],dp[2*x+2]);
    }
    void build(vector<ll> &a){
        build(a,0,0,size);
    }
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        data h;
        h.dt[0][1]=h.dt[1][0]=INF;
        h.dt[0][0]=h.dt[1][1]=INF;
        dp.assign(2*size,h);
    }
    data get_res(int l,int r,int x,int lx,int rx){
        if(lx>=r || rx<=l){
            data h;
            h.dt[0][1]=h.dt[1][0]=0;
            h.dt[0][0]=h.dt[1][1]=INF;
            return h;
        }
        if(lx>=l && rx<=r){
            //cout << lx << " " << rx << " " << dp[x].dt[0][0] << " " << dp[x].dt[0][1] << " " << dp[x].dt[1][0] << " " << dp[x].dt[1][1]  << "\n";
            return dp[x];
        }
        data s1,s2;
        int m=(lx+rx)/2;
        s1=get_res(l,r,2*x+1,lx,m);
        s2=get_res(l,r,2*x+2,m,rx);
        data h=f(s1,s2);
        //cout << lx << " " << rx << " " << h.dt[0][0] << " " << h.dt[0][1]  << " " << h.dt[1][0] << " " << h.dt[1][1] << "\n";
        return f(s1,s2);
    }
    data get_res(int l,int r){
        return get_res(l,r,0,0,size);
    }
    void set(int i,int v,int x,int lx,int rx){
        if(rx-lx==1){
            dp[x].dt[1][1]=v;
            dp[x].dt[0][0]=0;
            return;
        }
        int m=(lx+rx)/2;
        if(i<m){
            set(i,v,2*x+1,lx,m);
        }
        else{
            set(i,v,2*x+2,m,rx);
        }
        dp[x]=f(dp[2*x+1],dp[2*x+2]);
        //cout << lx << " " << rx << " " << dp[x].dt[0][0] << " " << dp[x].dt[0][1] << " " << dp[x].dt[1][0] << " " << dp[x].dt[1][1]  << "\n";
    }
    void set(int i,int v){
        set(i,v,0,0,size);
    }
};
struct dsu{
    vector<ll> e;
    void init(int n){
        e.resize(n+1,-1);
    }
    int get(int x){
        if(e[x]<0){
            return x;
        }
        else{
            return e[x]=get(e[x]);
        }
    }
    int size(int x){
        return -e[get(x)];
    }
    bool same_set(int x,int y){
        return (get(x)==get(y));
    }
    bool unite(int x,int y){
        x=get(x);
        y=get(y);
        if(x==y){
            return false;
        }
        if(e[x]>e[y]){
            swap(x,y);
        }
        e[x]+=e[y];
        e[y]=x;
        return true;
    }
};
ll b[10001][51];
ll dp[51][51][10001];
void solve(){
    cin >> n >> m;
    vector<ll> c;
    inputvec(c,n);
    fact[0]=1;
    for(int i=1;i<=n+m;i++){
        fact[i]=fact[i-1]*i;
        fact[i]%=MOD;
    }
    b[0][0] = 1;
    for (ll i = 1; i <= m; i++){
        b[i][0] = 1;
        for (ll j = 1; j <= min(n,i) ; j++){
            b[i][j] = b[i - 1][j - 1] + b[i - 1][j];
            b[i][j] %= MOD;
        }
    }
    sortv(c);
    dp[0][1][1]=1;
    for(int i=1;i<n;i++){
        for(int j=1;j<=n;j++){
            for(int z=1;z<=m;z++){
                if(j>=2){
                    dp[i][j][z]+=dp[i-1][j-1][z];
                    dp[i][j][z]%=MOD;
                }
                if(z>=c[i]){
                    dp[i][j][z]+=dp[i-1][j][z-c[i]]*2*j;
                    dp[i][j][z]%=MOD;
                }
                if(j<n && z>=2*c[i]){
                    dp[i][j][z]+=dp[i-1][j+1][z-2*c[i]]*(j*(j+1));
                    dp[i][j][z]%=MOD;
                }
            }
        }
    }
    ll res=0;
    for(int i=1;i<=m;i++){
        res+=(dp[n-1][1][i]*b[n+m-i][n])%MOD;
        res%=MOD;
    }
    cout << res << "\n";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //USACO("poetry");
    //freopen("input.txt","r",stdin);
    //cin >> t;
    ll cnt1=1;
    while(t--){
        solve();
        cnt1++;
    }
}
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
ll b[51][51];
b[0][0] = 1;
    for (int n = 1; n <= 50; ++n){
        b[n][0] = b[n][n] = 1;
        for (int k = 1; k < n; ++k)
            b[n][k] = b[n - 1][k - 1] + b[n - 1][k];
    }
*/

Compilation message

Main.cpp: In member function 'data segtree::get_res(int, int, int, int, int)':
Main.cpp:278:14: warning: variable 'h' set but not used [-Wunused-but-set-variable]
  278 |         data h=f(s1,s2);
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 205768 KB Output is correct
2 Correct 12 ms 20856 KB Output is correct
3 Correct 17 ms 20692 KB Output is correct
4 Correct 10 ms 14592 KB Output is correct
5 Correct 28 ms 22336 KB Output is correct
6 Correct 86 ms 70212 KB Output is correct
7 Correct 94 ms 115248 KB Output is correct
8 Correct 6 ms 10708 KB Output is correct
9 Correct 46 ms 60196 KB Output is correct
10 Correct 7 ms 10964 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20820 KB Output is correct
2 Correct 7 ms 12160 KB Output is correct
3 Correct 16 ms 20888 KB Output is correct
4 Correct 8 ms 13560 KB Output is correct
5 Correct 19 ms 20828 KB Output is correct
6 Correct 9 ms 12668 KB Output is correct
7 Correct 16 ms 20848 KB Output is correct
8 Correct 6 ms 11132 KB Output is correct
9 Correct 7 ms 12676 KB Output is correct
10 Correct 6 ms 11504 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15556 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 10 ms 15572 KB Output is correct
4 Correct 7 ms 12628 KB Output is correct
5 Correct 10 ms 15572 KB Output is correct
6 Correct 7 ms 11216 KB Output is correct
7 Correct 10 ms 15572 KB Output is correct
8 Correct 8 ms 10452 KB Output is correct
9 Correct 9 ms 12448 KB Output is correct
10 Correct 5 ms 10324 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 205768 KB Output is correct
2 Correct 12 ms 20856 KB Output is correct
3 Correct 17 ms 20692 KB Output is correct
4 Correct 10 ms 14592 KB Output is correct
5 Correct 28 ms 22336 KB Output is correct
6 Correct 86 ms 70212 KB Output is correct
7 Correct 94 ms 115248 KB Output is correct
8 Correct 6 ms 10708 KB Output is correct
9 Correct 46 ms 60196 KB Output is correct
10 Correct 7 ms 10964 KB Output is correct
11 Correct 17 ms 20820 KB Output is correct
12 Correct 7 ms 12160 KB Output is correct
13 Correct 16 ms 20888 KB Output is correct
14 Correct 8 ms 13560 KB Output is correct
15 Correct 19 ms 20828 KB Output is correct
16 Correct 9 ms 12668 KB Output is correct
17 Correct 16 ms 20848 KB Output is correct
18 Correct 6 ms 11132 KB Output is correct
19 Correct 7 ms 12676 KB Output is correct
20 Correct 6 ms 11504 KB Output is correct
21 Correct 11 ms 15556 KB Output is correct
22 Correct 7 ms 12116 KB Output is correct
23 Correct 10 ms 15572 KB Output is correct
24 Correct 7 ms 12628 KB Output is correct
25 Correct 10 ms 15572 KB Output is correct
26 Correct 7 ms 11216 KB Output is correct
27 Correct 10 ms 15572 KB Output is correct
28 Correct 8 ms 10452 KB Output is correct
29 Correct 9 ms 12448 KB Output is correct
30 Correct 5 ms 10324 KB Output is correct
31 Correct 294 ms 205704 KB Output is correct
32 Correct 187 ms 137164 KB Output is correct
33 Correct 288 ms 205692 KB Output is correct
34 Correct 63 ms 52968 KB Output is correct
35 Correct 277 ms 205744 KB Output is correct
36 Correct 22 ms 23136 KB Output is correct
37 Correct 298 ms 205692 KB Output is correct
38 Correct 58 ms 49968 KB Output is correct
39 Correct 271 ms 205644 KB Output is correct
40 Correct 82 ms 71248 KB Output is correct
41 Correct 262 ms 205604 KB Output is correct
42 Correct 7 ms 11860 KB Output is correct
43 Correct 283 ms 205636 KB Output is correct
44 Correct 35 ms 31308 KB Output is correct
45 Correct 302 ms 205748 KB Output is correct
46 Correct 7 ms 13652 KB Output is correct
47 Correct 86 ms 70600 KB Output is correct
48 Correct 32 ms 40948 KB Output is correct
49 Correct 9 ms 15736 KB Output is correct
50 Correct 7 ms 10696 KB Output is correct