제출 #551076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551076		ala2	Bali Sculptures (APIO15_sculpture)	C++14	37 / 100	242 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++)
        {
            if(j+1==n)
            {
                mn=min(mn,f(j+1,k,x+sum(i,j)));
            }
            else
            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];
        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: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29