Submission #446610

#	Time	Username	Problem	Language	Result	Execution time	Memory
446610		O_o	Hacker (BOI15_hac)	C++14	100 / 100	79 ms	21504 KiB

hac

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)

#define pb push_back
#define mp make_pair
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define precise(i) fixed << setprecision(i)
#define fi first
#define se second
#define sz(x) ((int)(x).size())

#define err() cout<<"\n==================================\n";
#define errA(A) for(auto i:A) cout<<i<<" "; cout<<"\n";
#define err1(a) cout<<#a<<" "<<a<<"\n";
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<"\n";
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<"\n";
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<"\n";

const int logN = 20;
const int M = 1000000007;
const int INF = 1e17;
#define PI 3.14159265;
const int N = 200005;

#define Pii pair<int,int>
#define Vi vector<int>
#define Vpii vector<Pii>
#define PQ priority_queue<int>

void setIO(string d_name = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(sz(d_name)){
		freopen((d_name+".in").c_str(), "r", stdin);
		freopen((d_name+".out").c_str(), "w", stdout);
	}
}

int32_t main()
{
    setIO();
    int n;
    cin>>n;
    Vi v(n);
    rep(i,0,n)
    {
    	cin>>v[i];
    }
    rep(i,0,n)
    {
    	v.pb(v[i]);
    }
    rep(i,1,2*n)
    {
    	v[i]+= v[i-1];
    }
    int m= (n+1)/2;
    deque<int> vals;
    Vi mSum(n+m);
    rep(i,0,n+m)
    {
    	int curSum;
    	if(!i)
    	{
    		curSum= (v[i+m-1]);
    	}
    	else
    	{
    		curSum= (v[i+m-1]-v[i-1]);
    	}
    	mSum[i]= curSum;
    }
    rep(i,0,m)
    {
    	while((!vals.empty()) && (mSum[vals.back()] >= mSum[i]))
    	{
    		vals.pop_back();
    	}
    	vals.push_back(i);
    }
    Vi ans(n);
    rep(i,m,n+m)
    {
    	int ind= (i-1)%n;
    	ans[ind]= mSum[vals.front()];
    	while((!vals.empty()) && (mSum[vals.back()] >= mSum[i]))
    	{
    		vals.pop_back();
    	}
    	vals.push_back(i);
    	if((!vals.empty()) && (vals.front() == i-m))
    	{
    		vals.pop_front();
    	}
    }
    int maxSum= 0;
    rep(i,0,n)
    {
    	maxSum= max(maxSum, ans[i]);
    }
    cout<<maxSum;

    return 0;
}

Compilation message (stderr)

hac.cpp: In function 'void setIO(std::string)':
hac.cpp:40:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   freopen((d_name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   freopen((d_name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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