oj.uz

Submission #950972

# Submission time Handle Problem Language Result Execution time Memory
950972 2024-03-21T03:21:47 Z pcc Peru (RMI20_peru) C++17
18 / 100
 16 ms 74332 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 = 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 = 1000;
 
int solve(int N,int K,int* S){
	int s = clock();
	int lim = 0.010*CLOCKS_PER_SEC;
	for(int i = N;i>=1;i--)arr[i] = S[i-1];
	arr[0] = 0;
	build(N);
	if(clock()-s>=lim)return 0;
	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.0 / 18.0

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

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26972 KB Output is correct
2 Correct 4 ms 26968 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 4 ms 27148 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 4 ms 26972 KB Output is correct
11 Correct 4 ms 27224 KB Output is correct
12 Correct 5 ms 26972 KB Output is correct
13 Correct 4 ms 26972 KB Output is correct
14 Correct 4 ms 26968 KB Output is correct
15 Incorrect 16 ms 74332 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 74332 KB Output isn't correct
2 Halted 0 ms 0 KB -