Submission #954534

#	Time	Username	Problem	Language	Result	Execution time	Memory
954534		vjudge1	Žarulje (COI15_zarulje)	C++17	0 / 100	39 ms	37200 KiB

zarulje

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1<<20;
int H[501],fac[N],inv[N],M=1e9+7,mn[501][501],mx[501][501];
int pw(int x,int k){
    if(!k) return 1;
    int y=pw(x,k/2);
    y=y*y%M;
    if(k&1)y=y*x%M;
    return y;
}
inline int P(int a,int b){
    if(a<b) return 0;
    return fac[a]*inv[a-b]%M;
}
inline int C(int a,int b){
    return P(a,b)*inv[b]%M;
}
map<tuple<int,int,int,int>,int> dp;
int Get(int l, int r, int m, int k){
    if(!k) return 1;
    if(k>r-l+1) return 0;
    if(dp.count({l,r,m,k}))
        return dp[{l,r,m,k}];
    int &x=dp[{l,r,m,k}],a=mn[l][r],b=mx[l][r];
    if(H[b]==m)
        x=0;
    else if(H[a]==m)
        for(int i=0;i<=k;i++)
            x=(x+Get(l,a-1,m,i)*Get(a+1,r,m,k-i))%M;
    else
        for(int i=0;i<=k;i++)
            x=(x+Get(l,r,H[a],k-i)*C(H[a]-m,i)%M*P(r-l+1,i))%M;
    return x;
}
signed main(){
    fac[0]=1;
    for(int i=1;i<N;i++)
        fac[i]=fac[i-1]*i%M;
    inv[N-1]=pw(fac[N-1],M-2);
    for(int i=N;--i;)
        inv[i-1]=inv[i]*i%M;
    cin.tie(0)->sync_with_stdio(0);
    int n, k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>H[i];
    for(int i=1,j;i<=n;i++)
        for(j=i,mn[i][i]=mx[j][j]=i;j<=n;mx[i][++j]=mx[i][j],mn[i][j]=mn[i][j-1])
            if(H[mx[i][j]]<H[j])
                mx[i][j]=j;
            else if(H[mn[i][j]]>H[j])
                mn[i][j]=j;
    cout<<Get(1,n,0,k);
}

Compilation message (stderr)

zarulje.cpp: In function 'int main()':
zarulje.cpp:50:48: warning: operation on 'j' may be undefined [-Wsequence-point]
   50 |         for(j=i,mn[i][i]=mx[j][j]=i;j<=n;mx[i][++j]=mx[i][j],mn[i][j]=mn[i][j-1])
      |                                                ^~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 38
• Subtask 3: 0 / 40