Submission #905139

#	Time	Username	Problem	Language	Result	Execution time	Memory
905139		pcc	Peru (RMI20_peru)	C++17	18 / 100	654 ms	80748 KiB

peru

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const ll inf = 4e18;
const ll mod = 1e9+7;
const ll p = 23;
const int mxn = 2500001;

int sparse[21][mxn];
int arr[mxn];
deque<int> dq;
pll dp[mxn];

void build(int N){
	for(int i = 0;i<=N;i++){
		sparse[0][i] = arr[i];
	}
	for(int i = 1;i<21;i++){
		for(int j = 0;j+(1<<i)-1<=N;j++){
			sparse[i][j] = max(sparse[i-1][j],sparse[i-1][j+(1<<(i-1))]);
		}
	}
	return;
}
int getval(int l,int r){
	int h = __lg(r-l+1);
	return max(sparse[h][l],sparse[h][r-(1<<h)+1]);
}

const int magic = 220;

int solve(int N,int K,int* S){
	int s = clock();
	int lim = 0.36*CLOCKS_PER_SEC;
	for(int i = N;i>=1;i--)arr[i] = S[i-1];
	arr[0] = 0;
	build(N);
	assert(clock()-s<=lim);
	dp[0] = make_pair(0,0);
	ll re = 0;
	for(int i = 1;i<=N;i++){
		dp[i] = make_pair(inf,i);
		for(int j = i-1;i-j<=K&&j>=0&&i-j<=magic;j--){
			dp[i] = min(dp[i],make_pair(dp[j].fs+getval(j+1,i),1ll*j));
		}
		for(int C = 0, j = max(dp[i-1].sc,1ll*i-K);C<=magic&&j<i;C++,j++){
			dp[i] = min(dp[i],make_pair(dp[j].fs+getval(j+1,i),1ll*j));
		}
		dp[i].sc = max(dp[i].sc,dp[i-1].sc);
		re = (re*p+dp[i].fs)%mod;
	}
	//for(int i = 1;i<=N;i++)cout<<dp[i].fs<<' ';cout<<endl;
	return re;
}

/*

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,k;
	cin>>n>>k;
	for(int i = 0;i<n;i++)cin>>arr[i];
	cout<<solve(n,k,(int*)arr);
}

*/

• Subtask 1: 18 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51