Submission #127580

#	Time	Username	Problem	Language	Result	Execution time	Memory
127580		MohamedAhmed04	Bali Sculptures (APIO15_sculpture)	C++14	21 / 100	14 ms	9468 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2005 ;
const int MAX2 = 105 ;

long long arr[MAX] , pref[MAX];

long long dp[MAX2][MAX2][MAX2] ;

int n , a , b ;

long long now = 0 ;

long long calc1(int idx , int st , int groups)
{
    if(idx == n && groups >= a && groups <= b)
    {
        long long val ;
        if(st == 0)
            val = pref[idx-1] ;
        else
            val = pref[idx-1] - pref[st-1] ;
        return val ;
    }
    if(idx == n && groups < a || groups > b)
        return (1ll << 58) ;
    long long &ret = dp[idx][st][groups] ;
    if(ret != -1)
        return ret ;
    long long val ;
    if(st == 0)
        val = pref[idx-1] ;
    else
        val = pref[idx-1] - pref[st-1] ;
    long long choice1 = calc1(idx+1 , st , groups) ;
    long long choice2 = calc1(idx+1 , idx , groups+1) | val ;
    ret = min(choice1 , choice2) ;
    return ret ;
}

void solve1()
{
    memset(dp , -1 , sizeof(dp)) ;
    cout<<calc1(1 , 0 , 1)<<"\n" ;
    return ;
}

//void solve2()
//{
//
//}

int main()
{
    scanf("%d %d %d" , &n , &a , &b) ;
    for(int i = 0 ; i < n ; ++i)
        scanf("%lld" , &arr[i]) ;
    pref[0] = arr[0] ;
    for(int i = 1 ; i < n ; ++i)
        pref[i] = pref[i-1] + arr[i] ;
    if(n <= 100)
    {
        solve1() ;
        return 0 ;
    }
    //solve2() ;
    return 0 ;
}

Compilation message (stderr)

sculpture.cpp: In function 'long long int calc1(int, int, int)':
sculpture.cpp:27:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if(idx == n && groups < a || groups > b)
        ~~~~~~~~~^~~~~~~~~~~~~
sculpture.cpp: In function 'int main()':
sculpture.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d" , &n , &a , &b) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld" , &arr[i]) ;
         ~~~~~^~~~~~~~~~~~~~~~~~

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