Submission #142778

#TimeUsernameProblemLanguageResultExecution timeMemory
14277812tqianBali Sculptures (APIO15_sculpture)C++14
100 / 100
88 ms884 KiB
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
  //  freopen(FOUT, "w", stdout);
    fast_io();
}
const int MAX = 2e3 + 5;
const int INF = 1e9;
vector<ll> y;
int a, b, n;
int dp[MAX][MAX];
ll pre[MAX];
ll po[MAX];
ll get(int l, int r){
    return pre[r] - (l == 0? 0: pre[l-1]);
}
inline int on(ll num, ll loc){
    return ((num&po[loc])>0? 1:0);
}

template<class T> struct MaxDeque {
    int lo = 0, hi = -1;
    int sz = 0;
    deque<pair<T,int>> d;
    void ins(T x) { // add to back
        x = -x;
        sz++;
       // cout << sz(d) << endl;
        while ((d).size() && d.back().first >= x) d.pop_back();
        d.push_back({x,++hi});
    }

    void del() { // delete from front
       // cout <<"shoot" << endl;
        sz--;
        if (d.front().second == lo++) d.pop_front();
    }
    T get() {
        return -((d).size() ? d.front().first : INF); // change based on T
    }
};
int possible[MAX];
int solve(ll mx, ll loc, ll o){
   // cout << mx << " " << loc << " " << o << endl;
    /// check if can have a 0 in b given all values are less than or equal to mx
    f0r(i, n+1){
        f0r(j, n+1){
            dp[i][j] = 0; ///used i intervals to cover up to and including j, whether you can do it
        }
    }
    f0r(i, n){
        if((get(0, i)|o)>mx) continue;
        dp[1][i] = 1-(on(get(0, i), loc));
    }
    f1r(i,2, n+1){
        int bef = 0;
        MaxDeque<int> d;
        f0r(j, n){
            f0r(t, j){
                if((get(t+1, j)|o) <= mx && dp[i-1][t]){
                    dp[i][j] = max(dp[i][j], 1-on(get(t+1, j), loc));
                }
            }
        }
    }
    bool isTrue = true;
    f1r(i, 1, n+1){
        if(possible[i] && dp[i][n-1]){
            isTrue = false;
            break;
        }
    }
    if(isTrue){
        return false;
    }
    f1r(i, 1, n+1){
        possible[i] = min(possible[i], dp[i][n-1]);
    }
    return true;
}
int dp1[MAX];
int solve1(ll mx, ll loc, ll o){
  //  cout << mx << " " << loc << " " << o << endl;
    /// minimum number to do in first i
    f0r(i, n){
        dp1[i] = INF;

    }
    f0r(i, n){
        //cout << (get(0, i)|o) << " " << mx << " " << (1-(on(get(0, i), loc)))  << endl;
        if((get(0, i)|o)<= mx && (1-(on(get(0, i), loc))) == 1){
            dp1[i] = 1;
            //cout << "Here" << endl;
            continue;
        }
        f0r(j, i){
            if((get(j+1, i)|o) <= mx && dp1[j] != INF && (1-on(get(j+1, i), loc)) == 1){
                dp1[i] = min(dp1[i], dp1[j] + 1);
            }
        }
    }
  //  cout << dp1[n-1] << " ans" <<endl;
    if(dp1[n-1]<=b) return true;
    return false;
    //return true;
}
int main(){
   // io("test");
    fast_io();
    cin >> n >> a >> b;
    ll sum = 0;
    f0r(i, n){
        ll yi;
        cin >> yi;
        y.eb(yi);
        sum += yi;
        if(i == 0) pre[i] = yi;
        else pre[i] = pre[i-1] + yi;
    }

    f0r(i, 50){
        if(i == 0) po[i] = 1;
        else po[i] = po[i-1]*2;
    }
    f1r(i, a, b+1) possible[i] = 1;
    ll ans = 0;
    ll bits = floor(log2(sum)) + 1;
    for(ll i = bits; i>= 0; i--){
      //  cout << ans << " " << i << endl;
     //   cout << (1<<i) << endl;
        bool val;
        if(a != 1) val = solve(ans + po[i] - 1, i, ans);
        else val = solve1(ans + po[i] -1, i, ans);
        if(val == false){
            ans += po[i];
        }
       // cout << "here" << endl;
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

sculpture.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
sculpture.cpp: In function 'void io(std::__cxx11::string)':
sculpture.cpp:46:17: warning: unused variable 'FOUT' [-Wunused-variable]
     const char* FOUT = fout.c_str();
                 ^~~~
sculpture.cpp: In function 'int solve(long long int, long long int, long long int)':
sculpture.cpp:100:13: warning: unused variable 'bef' [-Wunused-variable]
         int bef = 0;
             ^~~
sculpture.cpp: In function 'void io(std::__cxx11::string)':
sculpture.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...