oj.uz

Submission #743178

# Submission time Handle Problem Language Result Execution time Memory
743178 2023-05-17T08:37:59 Z bgnbvnbv Zoltan (COCI16_zoltan) C++14
70 / 140
 28 ms 2760 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];
    if(n>1000) return ;
    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;
        }
        else
        {
            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]&&dp[j][0]>0)
                {
                    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]&&dp[j][1]>0)
                {
                    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;
    ll cur=0;
    for(int i=1;i<=2*n-1;i++)
    {
        cur=ans;
        if(dp[i][0]==mx)
        {
            ans+=cnt[i][0]*pw(2,n-mx-1)%mod;
        }
        if(dp[i][1]==mx)
        {
            ans+=cnt[i][1]*pw(2,n-mx)%mod;
        }
        ans%=mod;
        //cout << i<<' '<<ans-cur<<'\n';
    }
    //cout << dp[4][0]<<'\n';
    cout <<mx <<' '<<ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

zoltan.cpp: In function 'void solve()':
zoltan.cpp:105:8: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  105 |     ll cur=0;
      |        ^~~

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 244 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 18 ms 340 KB Output is correct
9 Correct 16 ms 448 KB Output is correct
10 Correct 15 ms 340 KB Output is correct
11 Incorrect 18 ms 2360 KB Output isn't correct
12 Incorrect 19 ms 2228 KB Output isn't correct
13 Incorrect 15 ms 2220 KB Output isn't correct
14 Incorrect 16 ms 2252 KB Output isn't correct
15 Incorrect 21 ms 2512 KB Output isn't correct
16 Incorrect 28 ms 2748 KB Output isn't correct
17 Incorrect 19 ms 2724 KB Output isn't correct
18 Incorrect 18 ms 2756 KB Output isn't correct
19 Incorrect 19 ms 2760 KB Output isn't correct
20 Incorrect 26 ms 2704 KB Output isn't correct