Submission #1299306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299306		nmhung	Hacker (BOI15_hac)	C++20	0 / 100	1 ms	724 KiB

hac

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define file "file"
#define rf if(fopen(file".inp", "r")) {freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);}

const int N=5e5+7;
int n,a[N];
ll pre[N],mm[20][N],res;

int sub(int x, int y)
{
    x-=y;
    if(x<=0) x+=n;
    if(x>n) x-=n;
    return x;
}

int len(int x, int y)
{
    x-=y;
    if(x<0) x+=n;
    return x;
}

int ad(int x, int y)
{
    x+=y;
    if(x<=0) x+=n;
    if(x>n) x-=n;
    return x;
}

ll get(int l, int r)
{
    if(l>r) return 0;
    int len=31-__builtin_clz(r-l+1);
//    cout<<' '<<l<<' '<<r<<' '<<len<<' '<<mm[len][l]<<' '<<mm[len][r-(1<<len)+1]<<endl;
    return max(mm[len][l],mm[len][r-(1<<len)+1]);
}

void prep()
{
    for(int i=1; i<20; i++)
    for(int j=1; j<=n; j++)
    {
        if(j+(1<<i)-1>n) break;
        mm[i][j]=max(mm[i-1][j],mm[i-1][j+(1<<(i-1))]);
//        cout<<' '<<i<<' '<<j<<' '<<mm[i][j]<<' '<<mm[i-1][j]<<' '<<mm[i-1][j+(1<<(i-1))-1]<<endl;
    }
}

void init()
{
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
}

void proc()
{
    for(int i=1; i<=n; i++) pre[i]=pre[i-1]+a[i];
    for(int i=1; i<=n; i++)
    {
        int j=sub(ad(i,n/2),1); ll w;
        if(j<i) w=pre[j]+pre[n]-pre[i-1];
        else w=pre[j]-pre[i-1];

        mm[0][i]=w;

//        cout<<i<<' '<<j<<' '<<w<<endl;
    }
    prep();
//    cout<<get(1,3)<<' '<<get(3,5);
//    cout<<pre[n]<<endl;

    for(int i=1; i<=n; i++)
    {
        int j=sub(i,n/2); ll w;
        if(j<=n) w=get(i+1,n);
        else w=max(get(i+1,n),get(1,j));
//        cout<<i<<' '<<i-n/2<<' '<<sub(i,n/2)<<' '<<get(1,i-n/2)<<' '<<w<<endl;
        res=max(res,pre[n]-max(get(1,i-n/2),w));
    }

    cout<<res;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    rf;
    init();
    proc();
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:10:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define rf if(fopen(file".inp", "r")) {freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:98:5: note: in expansion of macro 'rf'
   98 |     rf;
      |     ^~
hac.cpp:10:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define rf if(fopen(file".inp", "r")) {freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);}
      |                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:98:5: note: in expansion of macro 'rf'
   98 |     rf;
      |     ^~

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