Submission #743039

#	Time	Username	Problem	Language	Result	Execution time	Memory
743039		bgnbvnbv	Zoltan (COCI16_zoltan)	C++14	49 / 140	1082 ms	5772 KiB

zoltan

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,a[maxN],b[maxN],dp[maxN][2],cnt[maxN][2];
ll pw(ll x,ll y)
{
    if(y==0) return 1;
    ll x1=pw(x,y/2);
    x1=x1*x1%mod;
    if(y&1) x1=x1*x%mod;
    return x1;
}
void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) b[i]=a[n-i+1];
    for(int i=n;i<=2*n-1;i++) b[i]=a[i-n+1];
    ll mx=0;
    for(int i=1;i<=2*n-1;i++)
    {
        dp[i][0]=1;
        cnt[i][0]=1;
        if(i==n)
        {
            dp[i][0]=-inf;
            cnt[i][0]=0;
        }
        for(int j=1;j<i;j++)
        {
            if(j==n) continue;
            if(b[j]<b[i])
            {
                if(dp[i][0]<dp[j][0]+1)
                {
                    dp[i][0]=dp[j][0]+1;
                    cnt[i][0]=cnt[j][0];
                }
                else if(dp[i][0]==dp[j][0]+1)
                {
                    cnt[i][0]=cnt[i][0]+cnt[j][0];
                    cnt[i][0]%=mod;
                }
            }
        }
        dp[i][1]=-inf;
        cnt[i][1]=0;
        if(i==n)
        {
            dp[i][1]=1;
            cnt[i][1]=1;
            for(int j=1;j<i;j++)
            {
                if(b[j]<b[i])
                {
                    if(dp[i][1]<dp[j][0]+1)
                    {
                        dp[i][1]=dp[j][0]+1;
                        cnt[i][1]=cnt[j][0];
                    }
                    else if(dp[i][1]==dp[j][0]+1)
                    {
                        cnt[i][1]=cnt[i][1]+cnt[j][0];
                        cnt[i][1]%=mod;
                    }
                }
            }
        }
        else
        {
            for(int j=1;j<i;j++)
            {
                if(b[j]<b[i])
                {
                    if(dp[i][1]<dp[j][1]+1)
                    {
                        dp[i][1]=dp[j][1]+1;
                        cnt[i][1]=cnt[j][1];
                    }
                    else if(dp[i][1]==dp[j][1]+1)
                    {
                        cnt[i][1]=cnt[i][1]+cnt[j][1];
                        cnt[i][1]%=mod;
                    }
                }
            }
        }
        mx=max({mx,dp[i][0],dp[i][1]});
    }
    ll ans=0;
    for(int i=1;i<=2*n-1;i++)
    {
        if(dp[i][0]==mx)
        {
            ans+=cnt[i][0]*pw(2,n-mx-1)%mod;
        }
        else if(dp[i][1]==mx)
        {
            ans+=cnt[i][1]*pw(2,n-mx)%mod;
        }
        ans%=mod;
    }
    cout <<mx <<' '<<ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

• Subtask 1: 49 / 140