oj.uz

Submission #550966

# Submission time Handle Problem Language Result Execution time Memory
550966 2022-04-19T14:13:19 Z ala2 Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 144 ms 219516 KB 
#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[1001000];
int p[1000100];
int suf[1001000];
int dp[55][501][501];
int sum(int i,int j)
{
    return p[j]-p[i]+a[i];
}
int f(int i,int x,int cur)
{
    if(dp[i][x][cur]!=-1)
        return dp[i][x][cur];
    if((cur|sum(i,n-1))==x){
        return 0;
    }
    if(i==n-1)
        return 1e17;
    int mn=1e17;
    for(int j=i;j<n-1;j++)
    {
        mn=min(mn,1+f(j+1,x,(cur|sum(i,j))));
    }
    return dp[i][x][cur]=mn;
}

signed main()
{
    memset(dp,-1,sizeof dp);
    cin>>n>>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];
    }
    for(int i=0;i<=1000;i++)
    {
          if(f(0,i,0)+1<=r){
            cout<<i<<endl;
            return 0;
          }
    }

}


/*
d

0101

1101
*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 108364 KB Output is correct
2 Correct 44 ms 108364 KB Output is correct
3 Correct 40 ms 108304 KB Output is correct
4 Correct 40 ms 108364 KB Output is correct
5 Correct 40 ms 108324 KB Output is correct
6 Correct 40 ms 108364 KB Output is correct
7 Correct 40 ms 108364 KB Output is correct
8 Correct 44 ms 108296 KB Output is correct
9 Correct 41 ms 108264 KB Output is correct
10 Correct 42 ms 108340 KB Output is correct
11 Correct 44 ms 108356 KB Output is correct
12 Correct 40 ms 108292 KB Output is correct
13 Correct 40 ms 108292 KB Output is correct
14 Correct 40 ms 108364 KB Output is correct
15 Incorrect 42 ms 108352 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 108456 KB Output is correct
2 Correct 42 ms 108352 KB Output is correct
3 Correct 40 ms 108268 KB Output is correct
4 Correct 43 ms 108336 KB Output is correct
5 Correct 40 ms 108320 KB Output is correct
6 Correct 41 ms 108344 KB Output is correct
7 Correct 43 ms 108296 KB Output is correct
8 Correct 42 ms 108364 KB Output is correct
9 Correct 42 ms 108344 KB Output is correct
10 Correct 42 ms 108344 KB Output is correct
11 Correct 45 ms 108348 KB Output is correct
12 Correct 40 ms 108292 KB Output is correct
13 Correct 41 ms 108296 KB Output is correct
14 Correct 41 ms 108284 KB Output is correct
15 Incorrect 41 ms 108360 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 108440 KB Output is correct
2 Correct 41 ms 108360 KB Output is correct
3 Correct 39 ms 108360 KB Output is correct
4 Correct 41 ms 108300 KB Output is correct
5 Correct 46 ms 108352 KB Output is correct
6 Correct 40 ms 108364 KB Output is correct
7 Correct 40 ms 108400 KB Output is correct
8 Correct 42 ms 108348 KB Output is correct
9 Correct 42 ms 108356 KB Output is correct
10 Correct 43 ms 108356 KB Output is correct
11 Correct 44 ms 108364 KB Output is correct
12 Correct 42 ms 108296 KB Output is correct
13 Correct 42 ms 108364 KB Output is correct
14 Correct 43 ms 108368 KB Output is correct
15 Correct 43 ms 108256 KB Output is correct
16 Correct 49 ms 108356 KB Output is correct
17 Correct 43 ms 108348 KB Output is correct
18 Correct 53 ms 108348 KB Output is correct
19 Correct 47 ms 108368 KB Output is correct
20 Correct 144 ms 108340 KB Output is correct
21 Correct 46 ms 108364 KB Output is correct
22 Correct 45 ms 108288 KB Output is correct
23 Correct 51 ms 108356 KB Output is correct
24 Correct 53 ms 108368 KB Output is correct
25 Incorrect 42 ms 108308 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 108304 KB Output is correct
2 Correct 42 ms 108364 KB Output is correct
3 Correct 42 ms 108320 KB Output is correct
4 Correct 42 ms 108296 KB Output is correct
5 Correct 42 ms 108320 KB Output is correct
6 Correct 41 ms 108372 KB Output is correct
7 Correct 42 ms 108260 KB Output is correct
8 Correct 40 ms 108364 KB Output is correct
9 Correct 42 ms 108300 KB Output is correct
10 Correct 43 ms 108364 KB Output is correct
11 Correct 43 ms 108364 KB Output is correct
12 Correct 44 ms 108252 KB Output is correct
13 Correct 41 ms 108252 KB Output is correct
14 Correct 42 ms 108272 KB Output is correct
15 Incorrect 49 ms 108360 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 108300 KB Output is correct
2 Correct 44 ms 108328 KB Output is correct
3 Correct 43 ms 108364 KB Output is correct
4 Correct 42 ms 108332 KB Output is correct
5 Correct 41 ms 108340 KB Output is correct
6 Correct 41 ms 108304 KB Output is correct
7 Correct 42 ms 108316 KB Output is correct
8 Correct 46 ms 108376 KB Output is correct
9 Correct 44 ms 108452 KB Output is correct
10 Correct 43 ms 108324 KB Output is correct
11 Correct 49 ms 108280 KB Output is correct
12 Correct 46 ms 108352 KB Output is correct
13 Correct 40 ms 108304 KB Output is correct
14 Runtime error 138 ms 219516 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -