Submission #1083799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083799		vjudge1	Flooding Wall (BOI24_wall)	C++17	8 / 100	183 ms	4568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define for1(i,x,n) for(int i=x;i<=n;i++)
#define for2(i,x,n) for(int i=x;i>=n;i--)
#define int ll

typedef long long ll;
typedef pair<int,int> pii;

const ll maxn=2e5+69;
const ll mod=1e9+7;
const ll inf=1e18;

int n,a[maxn],b[maxn];
namespace sub2
{
    int mu2[maxn];
    void sol()
    {
        mu2[0]=1;
        for1(i,1,n) mu2[i]=mu2[i-1]*2%mod;
        int res=0;
        for1(i,1,n)
        {
            res+=mu2[n-1]-mu2[i-1]-mu2[n-i]+1;
        }
        cout << res;
    }
}
namespace sub1
{
    int x[50],pre[50],suf[50];
    void sol()
    {
        int ans=0;
//        for1(mask,6,6)
        for1(mask,0,(1<<n)-1)
        {
            for1(i,1,n)
            {
                if ((mask>>(i-1))&1) x[i]=a[i];
                else x[i]=b[i];
//                cerr<< x[i]<<' ';
            }
//            cerr<< '\n';
            for1(i,1,n) pre[i]=max(pre[i-1],x[i]);
            for2(i,n,1) suf[i]=max(suf[i+1],x[i]);
            for1(i,1,n)
            {
//                if (pre[i-1]<x[i] || suf[i+1]<x[i]) continue;
//                if (min(pre[i],suf[i])-x[i]<0) cerr<< "gg\n";
                ans+=min(pre[i],suf[i])-x[i];
                ans%=mod;
            }
        }
        cout << ans;
    }
}
void sol()
{
    cin >> n;
    for1(i,1,n) cin >> a[i];
    bool is_sub2=1;
    for1(i,1,n)
    {
        cin >> b[i];
        if (b[i]<a[i]) swap(a[i],b[i]);
        if (a[i]!=1 || b[i]!=2) is_sub2=0;
    }
    if (is_sub2)
    {
        sub2::sol();
        return;
    }
    if (n<=20)
    {
        sub1::sol();
        return;
    }

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("wall.inp","r",stdin);
//    freopen("wall.out","w",stdout);
    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
*/

• Subtask 1: 8 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 19
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30