제출 #142776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
142776		12tqian	Bali Sculptures (APIO15_sculpture)	C++14	37 / 100	16 ms	764 KiB

sculpture

#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 get(int l, int r){
    return pre[r] - (l == 0? 0: pre[l-1]);
}
inline int on(ll num, int loc){
    return ((num&(1<<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, int 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 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;
    }
    f1r(i, a, b+1) possible[i] = 1;
    ll ans = 0;
    int bits = floor(log2(sum)) + 1;
    for(int i = bits; i>= 0; i--){
      //  cout << ans << " " << i << endl;
        bool val = solve(ans + (1<<i) - 1, i, ans);
        if(val == false){
            ans += (1<<i);
        }
    }
    cout << ans << endl;
    return 0;
}

컴파일 시 표준 에러 (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, int, long long int)':
sculpture.cpp:99: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);
     ~~~~~~~^~~~~~~~~~~~~~~~~

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