Submission #633118

#	Time	Username	Problem	Language	Result	Execution time	Memory
633118		Iwanttobreakfree	Hacker (BOI15_hac)	C++17	100 / 100	488 ms	45796 KiB

hac

#include <iostream>
#include <vector>
using namespace std;
#define int long long int
int f(int a,int b){
	return min(a,b);
}
int ls(int x){
	return x<<1;
}
int rs(int x){
	return (x<<1)+1;
}
void build(int n,int l,int r,vector<int>& li,vector<int>& t){
	if(l==r)t[n]=li[l];
	else{
		int mid=(r+l)/2;
		build(ls(n),l,mid,li,t);
		build(rs(n),mid+1,r,li,t);
		t[n]=f(t[ls(n)],t[rs(n)]);
	}
}
void lazy(int n,int l,int r,int x,vector<int>& la,vector<int>& t){
	la[n]=max(la[n],x);
	t[n]=max(t[n],x);
}
void rupd(int n,int l,int r,int a,int b,int x,vector<int>& t,vector<int>& la){
	if(l>b||r<a)return;
	if(l>=a&&r<=b){
		lazy(n,l,r,x,la,t);
	}
	else{
		int mid=(r+l)/2;
		if(l!=r&&la[n]!=0){
			int y=la[n];
			lazy(ls(n),l,mid,y,la,t);
			lazy(rs(n),mid+1,r,y,la,t);
			la[n]=0;
		}
		rupd(ls(n),l,mid,a,b,x,t,la);
		rupd(rs(n),mid+1,r,a,b,x,t,la);
		t[n]=f(t[ls(n)],t[rs(n)]);
	}
}
signed main(){
    int n,ans=0,tot=0;
    cin>>n;
    vector<int> v(n),v2(2*n+1);
    for(int& i:v){
        cin>>i;
        tot+=i;
    }
    for(int i=1;i<=2*n;i++){
        v2[i]=v[(i-1)%n]+v2[i-1];
        //cout<<v2[i]-v2[i-1]<<' ';
    }
    //cout<<endl;
    vector<int> t(4*n),la(4*n);
    int dif=n/2;
    for(int i=0;i<n;i++){
        int val=v2[i+dif]-v2[i];
        if((i+dif)%n<i)rupd(1,0,n-1,(i+dif)%n,i-1,val,t,la);
        else{
            rupd(1,0,n-1,0,i-1,val,t,la);
            rupd(1,0,n-1,i+dif,n-1,val,t,la);
        }
    }
    int x=t[1];
    cout<<tot-x;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:46:11: warning: unused variable 'ans' [-Wunused-variable]
   46 |     int n,ans=0,tot=0;
      |           ^~~

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