oj.uz

Submission #743039

# Submission time Handle Problem Language Result Execution time Memory
743039 2023-05-17T07:35:57 Z bgnbvnbv Zoltan (COCI16_zoltan) C++14
49 / 140
 1000 ms 5772 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 15 ms 336 KB Output isn't correct
8 Incorrect 14 ms 340 KB Output isn't correct
9 Correct 16 ms 444 KB Output is correct
10 Correct 17 ms 340 KB Output is correct
11 Execution timed out 1068 ms 4932 KB Time limit exceeded
12 Execution timed out 1073 ms 4596 KB Time limit exceeded
13 Execution timed out 1039 ms 4556 KB Time limit exceeded
14 Execution timed out 1072 ms 4828 KB Time limit exceeded
15 Execution timed out 1035 ms 5412 KB Time limit exceeded
16 Execution timed out 1082 ms 5772 KB Time limit exceeded
17 Incorrect 19 ms 3140 KB Output isn't correct
18 Incorrect 24 ms 3068 KB Output isn't correct
19 Incorrect 23 ms 3120 KB Output isn't correct
20 Incorrect 20 ms 3156 KB Output isn't correct