제출 #551081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551081		ala2	Bali Sculptures (APIO15_sculpture)	C++14	21 / 100	241 ms	262144 KiB

sculpture

    #include <bits/stdc++.h>
        #define int long long
        #define pb push_back
        #define F first
        #define S second
        #define B begin()
        #define E end()
        using namespace std;
        int n,l,r;
        int a[100100];
        int p[100010];
        int suf[100000];
        int dp[104][104][2004];
        int sum(int i,int j)
        {
            return p[j]-p[i]+a[i];
        }
        int f(int i,int k,int x)
        {
            if(i==n&&k>=l&&k<=r)
                return x;
            else if(i==n)return 1e18;
            if(k==r)
            {
                return (x|suf[i]);
            }
            if(dp[i][k][x]!=-1)
                return dp[i][k][x];
            int mn=1e18;
            if(k>=l)
                mn=min(mn,(suf[i]|x));
            for(int j=i;j<n;j++)
            {
                mn=min(mn,f(j+1,k+1,(x|sum(i,j))));
            }
            return dp[i][k][x]=mn;
     
        }
        signed main()
        {
             memset(dp,-1,sizeof dp);
            cin>>n>>l>>r;
            
            l--;
            r--;
            for(int i=0;i<n;i++)
                cin>>a[i];
            a[n]=0;
            n++;
            p[0]=a[0];
            for(int i=1;i<n;i++)
                p[i]=p[i-1]+a[i];
            suf[n-1]=a[n-1];
            for(int i=n-2;i>=0;i--)
            {
                suf[i]=suf[i+1]+a[i];
            }
     
            int mn=1e18;
            mn=min(mn,f(0,0,0));
     
            cout<<mn<<endl;
        }

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29