Submission #551076

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
551076	2022-04-19T18:57:51 Z	ala2	Bali Sculptures (APIO15_sculpture)	C++14	37 / 100	242 ms	262144 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	169912 KB	Output is correct
2	Correct	63 ms	169948 KB	Output is correct
3	Correct	64 ms	169852 KB	Output is correct
4	Correct	71 ms	169932 KB	Output is correct
5	Correct	64 ms	169932 KB	Output is correct
6	Correct	60 ms	169888 KB	Output is correct
7	Correct	62 ms	169864 KB	Output is correct
8	Correct	62 ms	169876 KB	Output is correct
9	Correct	63 ms	169932 KB	Output is correct
10	Correct	62 ms	169956 KB	Output is correct
11	Correct	62 ms	169876 KB	Output is correct
12	Correct	63 ms	169924 KB	Output is correct
13	Correct	62 ms	169932 KB	Output is correct
14	Correct	79 ms	169888 KB	Output is correct
15	Correct	65 ms	169956 KB	Output is correct
16	Correct	62 ms	169920 KB	Output is correct
17	Correct	64 ms	169916 KB	Output is correct
18	Correct	66 ms	169960 KB	Output is correct
19	Correct	63 ms	169892 KB	Output is correct
20	Correct	64 ms	169872 KB	Output is correct
21	Correct	66 ms	169932 KB	Output is correct
22	Correct	69 ms	169852 KB	Output is correct
23	Correct	62 ms	169876 KB	Output is correct
24	Correct	63 ms	169960 KB	Output is correct
25	Correct	66 ms	169932 KB	Output is correct
26	Correct	65 ms	169936 KB	Output is correct
27	Runtime error	232 ms	262144 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	169884 KB	Output is correct
2	Correct	64 ms	169924 KB	Output is correct
3	Correct	61 ms	169884 KB	Output is correct
4	Correct	64 ms	169928 KB	Output is correct
5	Correct	66 ms	169968 KB	Output is correct
6	Correct	63 ms	169868 KB	Output is correct
7	Correct	64 ms	169900 KB	Output is correct
8	Correct	64 ms	169960 KB	Output is correct
9	Correct	62 ms	169888 KB	Output is correct
10	Correct	61 ms	169900 KB	Output is correct
11	Correct	64 ms	169928 KB	Output is correct
12	Correct	63 ms	169932 KB	Output is correct
13	Correct	66 ms	170000 KB	Output is correct
14	Correct	65 ms	169952 KB	Output is correct
15	Correct	67 ms	169864 KB	Output is correct
16	Correct	65 ms	169904 KB	Output is correct
17	Correct	71 ms	169948 KB	Output is correct
18	Correct	64 ms	169872 KB	Output is correct
19	Correct	62 ms	169860 KB	Output is correct
20	Correct	68 ms	169892 KB	Output is correct
21	Correct	60 ms	169932 KB	Output is correct
22	Correct	63 ms	169932 KB	Output is correct
23	Correct	67 ms	169888 KB	Output is correct
24	Correct	65 ms	169888 KB	Output is correct
25	Correct	63 ms	169864 KB	Output is correct
26	Correct	64 ms	170072 KB	Output is correct
27	Correct	63 ms	169880 KB	Output is correct
28	Correct	73 ms	169960 KB	Output is correct
29	Correct	63 ms	169956 KB	Output is correct
30	Correct	61 ms	169848 KB	Output is correct
31	Correct	65 ms	169940 KB	Output is correct
32	Correct	64 ms	169856 KB	Output is correct
33	Correct	64 ms	169932 KB	Output is correct
34	Correct	64 ms	169912 KB	Output is correct
35	Correct	67 ms	169892 KB	Output is correct
36	Correct	75 ms	169932 KB	Output is correct

Subtask #3

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	169952 KB	Output is correct
2	Correct	65 ms	169936 KB	Output is correct
3	Correct	61 ms	169916 KB	Output is correct
4	Correct	63 ms	169840 KB	Output is correct
5	Correct	64 ms	169884 KB	Output is correct
6	Correct	73 ms	169916 KB	Output is correct
7	Correct	66 ms	169848 KB	Output is correct
8	Correct	63 ms	169932 KB	Output is correct
9	Correct	61 ms	169872 KB	Output is correct
10	Correct	62 ms	169928 KB	Output is correct
11	Correct	66 ms	169952 KB	Output is correct
12	Correct	63 ms	169940 KB	Output is correct
13	Correct	61 ms	169844 KB	Output is correct
14	Correct	63 ms	169892 KB	Output is correct
15	Correct	70 ms	169960 KB	Output is correct
16	Correct	62 ms	169896 KB	Output is correct
17	Correct	64 ms	169884 KB	Output is correct
18	Correct	64 ms	169928 KB	Output is correct
19	Correct	64 ms	169956 KB	Output is correct
20	Correct	63 ms	169916 KB	Output is correct
21	Correct	67 ms	169872 KB	Output is correct
22	Correct	65 ms	169916 KB	Output is correct
23	Correct	63 ms	169984 KB	Output is correct
24	Correct	67 ms	169932 KB	Output is correct
25	Correct	64 ms	169904 KB	Output is correct
26	Correct	77 ms	169968 KB	Output is correct
27	Correct	99 ms	169972 KB	Output is correct
28	Correct	123 ms	169972 KB	Output is correct
29	Correct	96 ms	169932 KB	Output is correct
30	Correct	72 ms	169920 KB	Output is correct
31	Correct	130 ms	169932 KB	Output is correct
32	Correct	113 ms	169964 KB	Output is correct

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	169840 KB	Output is correct
2	Correct	61 ms	169872 KB	Output is correct
3	Correct	64 ms	169924 KB	Output is correct
4	Correct	64 ms	169960 KB	Output is correct
5	Correct	65 ms	169892 KB	Output is correct
6	Correct	62 ms	169936 KB	Output is correct
7	Correct	62 ms	169920 KB	Output is correct
8	Correct	71 ms	169932 KB	Output is correct
9	Correct	64 ms	169900 KB	Output is correct
10	Correct	66 ms	170004 KB	Output is correct
11	Correct	70 ms	169960 KB	Output is correct
12	Correct	66 ms	169916 KB	Output is correct
13	Correct	62 ms	169868 KB	Output is correct
14	Correct	63 ms	169928 KB	Output is correct
15	Correct	72 ms	169896 KB	Output is correct
16	Correct	63 ms	169932 KB	Output is correct
17	Correct	63 ms	169860 KB	Output is correct
18	Correct	69 ms	169932 KB	Output is correct
19	Correct	64 ms	169888 KB	Output is correct
20	Correct	73 ms	169900 KB	Output is correct
21	Correct	63 ms	169932 KB	Output is correct
22	Correct	64 ms	169924 KB	Output is correct
23	Correct	63 ms	169884 KB	Output is correct
24	Correct	66 ms	169972 KB	Output is correct
25	Correct	70 ms	169932 KB	Output is correct
26	Correct	64 ms	169972 KB	Output is correct
27	Runtime error	228 ms	262144 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	169844 KB	Output is correct
2	Correct	63 ms	169932 KB	Output is correct
3	Correct	64 ms	169956 KB	Output is correct
4	Correct	64 ms	169944 KB	Output is correct
5	Correct	64 ms	169916 KB	Output is correct
6	Correct	66 ms	169952 KB	Output is correct
7	Correct	66 ms	169840 KB	Output is correct
8	Correct	63 ms	169844 KB	Output is correct
9	Correct	62 ms	169920 KB	Output is correct
10	Correct	65 ms	169968 KB	Output is correct
11	Correct	64 ms	169864 KB	Output is correct
12	Correct	67 ms	169936 KB	Output is correct
13	Correct	63 ms	169864 KB	Output is correct
14	Runtime error	242 ms	262144 KB	Execution killed with signal 11
15	Halted	0 ms	0 KB	-