oj.uz

Submission #533947

# Submission time Handle Problem Language Result Execution time Memory
533947 2022-03-07T17:34:37 Z amunduzbaev Peru (RMI20_peru) C++17
0 / 100
 1 ms 468 KB 
#include "bits/stdc++.h"
using namespace std;
#include "peru.h"
#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
const int N = 4e5 + 5;
const int mod = 1e9 + 7;
const int P = 23;
long long dp[N];

int solve(int n, int k, int* a){
	deque<int> ss;
	multiset<long long> mm;
	int res = 0;
	for(int i=0;i<n;i++){
		while(!ss.empty() && ss.front() <= i - k){
			int j = ss.front(); ss.pop_front();
			if(!ss.empty()){
				assert(mm.count(dp[ss.back()] + a[j]));
				mm.erase(mm.find(dp[j] + a[ss.front()]));
			}
		}
		while(!ss.empty() && a[ss.back()] <= a[i]){
			int j = ss.back(); ss.pop_back();
			if(!ss.empty()){
				//~ assert(mm.count(dp[ss.back()] + a[j]));
				mm.erase(mm.find(dp[ss.back()] + a[j]));
			}
		}
		
		dp[i] = 1e18;
		if(!ss.empty()) mm.insert(dp[ss.back()] + a[i]);
		ss.push_back(i);
		if(!mm.empty()) dp[i] = *mm.begin();
		assert(!ss.empty());
		dp[i] = min(dp[i], (i < k ? 0 : dp[i-k]) + a[ss.front()]);
		res = (res * 1ll * P + dp[i]) % mod;
	} 
	
	//~ cout<<"\n";
	return res;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -