Submission #1206027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206027		squatrian	Hacker (BOI15_hac)	C++20	100 / 100	84 ms	16736 KiB

hac

#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;
using std::mt19937_64;
using std::random_device;
using std::uniform_int_distribution;
#include <numeric>
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             (int) 1e17+1
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
void cpc()
{
#ifndef ONLINE_JUDGE
    freopen("paintbarn.in", "r", stdin);
    freopen("paintbarn.out", "w", stdout);
#endif
}
// int dx[] = {-1, 0, 1, 0};
// int dy[] = {0, 1, 0, -1};
int exp(int x, int n, int m) {
    if(x == 0 and n == 0) return 1;
    x %= m; 
    int res = 1;
    while (n > 0) {
        if (n % 2 == 1) { res = res * x % m; }
        x = x * x % m;
        n /= 2;
    }
    return res;
}
int gcd(int a,int b){
    if(a == 0) return b;
    return gcd(b%a,a);
}
stack<pair<int,int>> s1,s2;

signed main()
{  
   // cpc();
   int t=1;
   // cin >> t; 
   while(t--){
    int n;
    cin >> n;
    vector<int> v(n);
    for(auto &x:v) cin >> x;
    vector<int> a;
    int ct = (n+1)/2-1;
    int i = n-ct;
    while(ct--){
        a.pb(v[i++]);
    }
    for(int j = 0 ; j < n; j++) a.pb(v[j]);
    ct = (n+1)/2-1;
    i = 0;
    while(ct--){
        a.pb(v[i++]);
    }
    // for(auto &x:a) cout<<x<<" ";
    //     cout<<endl;
    int cur_sum = 0;
    ct = (n+1)/2-1;
    for(int i = 0 ; i <= ct; i++){
        cur_sum += a[i];
    }

    s1.push({cur_sum,cur_sum});
    // cout<<cur_sum<<endl;
    for(int i = ct+1; i <=2*ct; i++){
      cur_sum -= a[i-ct-1];
      cur_sum += a[i];
     s1.push({cur_sum,min(s1.top().ss,cur_sum)});
    }
    // while(!s1.empty()){
    //     cout<<s1.top().ff<<" "<<s1.top().ss<<endl;
    //     s1.pop();
    // }
    // cout<<cur_sum<<endl;
    int ans = s1.top().ss;
    for(int i = 2*ct+1; i < a.size(); i++){
     cur_sum -= a[i-ct-1];
     cur_sum += a[i];
     // cout<<cur_sum<<endl;
     if(s2.empty()){
        while(!s1.empty()){
           if(s2.empty()) s2.push({s1.top().ff,s1.top().ff});
           else s2.push({s1.top().ff,min(s1.top().ff,s2.top().ss)});
            s1.pop();
        }
     }
     s2.pop();
     if(s1.empty()) s1.push({cur_sum,cur_sum});
    else s1.push({cur_sum,min(s1.top().ss,cur_sum)}); 
    int mi = s1.top().ss;
    if(!s2.empty()) mi = min(s2.top().ss,s1.top().ss);
    ans = max(ans,mi);
    }
    cout<<ans<<endl;
    }
return 0;
}

Compilation message (stderr)

hac.cpp: In function 'void cpc()':
hac.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen("paintbarn.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen("paintbarn.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40