Submission #675567

#	Time	Username	Problem	Language	Result	Execution time	Memory
675567		m23022002	Bali Sculptures (APIO15_sculpture)	C++14	21 / 100	40 ms	536 KiB

sculpture

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pi (3.141592653589)
#define ordered_set tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update>
#define mod 1000000007
#define N 100000
#define float double
#define pb push_back
#define all(c) c.begin(), c.end()
#define rloop(i, n) for(int i=n-1;i>=0;i--)
#define loop(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);


//--------------------------I never forgive--------------------------------//

vector<int>arr;//(n);
vector<vector<int>>dp;//(arr.size() + 5, vector<int>(curr + 5, -1));
int rec(int i, int n)
{
    //base condition
    if(i >= arr.size()){
        // if(n == 0) return 0;
        return LLONG_MAX;
    }
    if(n > arr.size() - i) return LLONG_MAX;
    if(n == 1) return accumulate(arr.begin() + i, arr.end(), 0ll);
    if(dp[i][n] != -1) return dp[i][n];

    //recv condition
    int ans = LLONG_MAX;
    int curr_ans = 0;
    for(int idx = i;idx < arr.size();++idx)
    {
        curr_ans += 1ll * arr[idx];
        ans = min(ans, curr_ans | rec(idx + 1, n - 1));
    }
    return dp[i][n] = ans;
}
int sol(int curr){
    dp.clear();
    dp.resize(arr.size() + 5);
    loop(i, dp.size()){
        dp[i].resize(curr + 5);
        loop(j, dp[i].size()) dp[i][j] = -1;
    }
    return rec(0, curr);
}
void solve()
{
    arr.clear();
    int n, a, b;
    cin >> n >> a >> b;
    arr.resize(n);
    loop(i, n) cin >> arr[i];
    int ans = LLONG_MAX;
    for(int i=a;i<=b;++i)
    {
        // cout << sol(i) << endl;
        ans = min(ans, sol(i));
    }
    cout << ans << endl;
}

int32_t main(){
fast
int t=1;
// cin>>t;
while(t--){
    solve();
}
return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'long long int rec(long long int, long long int)':
sculpture.cpp:26:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if(i >= arr.size()){
      |        ~~^~~~~~~~~~~~~
sculpture.cpp:30:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   30 |     if(n > arr.size() - i) return LLONG_MAX;
      |        ~~^~~~~~~~~~~~~~~~
sculpture.cpp:37:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int idx = i;idx < arr.size();++idx)
      |                     ~~~~^~~~~~~~~~~~
sculpture.cpp: In function 'long long int sol(long long int)':
sculpture.cpp:15:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define loop(i,n) for(int i=0;i<n;i++)
......
   47 |     loop(i, dp.size()){
      |          ~~~~~~~~~~~~           
sculpture.cpp:47:5: note: in expansion of macro 'loop'
   47 |     loop(i, dp.size()){
      |     ^~~~
sculpture.cpp:15:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define loop(i,n) for(int i=0;i<n;i++)
......
   49 |         loop(j, dp[i].size()) dp[i][j] = -1;
      |              ~~~~~~~~~~~~~~~    
sculpture.cpp:49:9: note: in expansion of macro 'loop'
   49 |         loop(j, dp[i].size()) dp[i][j] = -1;
      |         ^~~~

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