답안 #743178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
743178	2023-05-17T08:37:59 Z	bgnbvnbv	Zoltan (COCI16_zoltan)	C++14	70 / 140	28 ms	2760 KB

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];
    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

#	결과	실행 시간	메모리	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