oj.uz

Submission #142768

# Submission time Handle Problem Language Result Execution time Memory
142768 2019-08-10T19:56:53 Z 12tqian Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 4 ms 504 KB 
#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){
    /// 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){
            while(bef+1 <= j && (get(bef, j)|o) >mx){
                bef++;
                //d.del();
            }
            while(d.sz> j-bef+1) {
                d.del();
              //  cout << "deletion" << endl;
            }
            if((get(bef, j)|o)>mx) {
                d.ins(dp[i-1][j]);
              //  cout <<"insertion" << endl;
                continue;
            }
            dp[i][j] = min(max(d.get(), 0), 1-on(get(bef, j), loc));
            //cout << dp[i][j] << " " << i << " " << j << " " << d.get() endl;
            d.ins(dp[i-1][j]);
         //   cout << "insertion" << endl;
        }
    }
    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(){
    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--){
        bool val = solve(ans + (1<<i) - 1, i, ans);
        if(val == false){
            ans += (1<<i);
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message

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: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);
     ~~~~~~~^~~~~~~~~~~~~~~~~
sculpture.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 3 ms 376 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 3 ms 376 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Halted 0 ms 0 KB -