oj.uz

Submission #905123

# Submission time Handle Problem Language Result Execution time Memory
905123 2024-01-12T15:39:57 Z pcc Peru (RMI20_peru) C++17
18 / 100
 600 ms 59404 KB 
#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 = 250001;

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;
}
ll 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 = 200;

int solve(int N,int K,int* S){
	for(int i = N;i>=1;i--)arr[i] = S[i-1];
	arr[0] = 0;
	build(N);
	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));
		}
		int C = 0;
		for(int 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));
		}
		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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 5 ms 16728 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 6 ms 16728 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 4 ms 16732 KB Output is correct
10 Correct 4 ms 16732 KB Output is correct
11 Correct 4 ms 16732 KB Output is correct
12 Correct 7 ms 16728 KB Output is correct
13 Correct 5 ms 16732 KB Output is correct
14 Correct 4 ms 16728 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 5 ms 16728 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 6 ms 16728 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 4 ms 16732 KB Output is correct
10 Correct 4 ms 16732 KB Output is correct
11 Correct 4 ms 16732 KB Output is correct
12 Correct 7 ms 16728 KB Output is correct
13 Correct 5 ms 16732 KB Output is correct
14 Correct 4 ms 16728 KB Output is correct
15 Execution timed out 811 ms 59404 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 811 ms 59404 KB Time limit exceeded
2 Halted 0 ms 0 KB -