oj.uz

Submission #657567

# Submission time Handle Problem Language Result Execution time Memory
657567 2022-11-10T09:06:34 Z lovrot Peru (RMI20_peru) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h> 
#include "peru.h"
using namespace std; 

typedef long long ll;

const int N = 25 * 1e2 + 10;
const ll MOD = 1e9 + 7;

int dp[N];

int add(int a, int b){
	if(a + b < 0) return a + b + N;
	if(a + b >= N) return a + b - N;
	return a + b;
}

ll MODadd(ll a, ll b){
	return (a + b) % MOD;
}

ll MODmult(ll a, ll b){
	return a * b % MOD;
}

struct elem{
	int val, maxi, ind;
	elem(){
		val = 0;
		maxi = 0;
		ind = 0;
	};
};

struct monostack{
	elem arr[N];
	int ind = 0;
	void push(elem x){
		if(ind) x.val = min(x.val, arr[ind - 1].val);
		arr[ind] = x;
		ind++;
	};
	elem pop(){
		if(ind){
			ind--;
			return arr[ind];
		}
		assert(false);
		return arr[ind];
	};
	elem front(){
		if(ind) return arr[ind - 1];
		assert(false);
		return arr[ind];
	};
	int size(){
		return ind;
	};
	void clear(){
		ind = 0;
	};
};

struct monodeck{
	monostack l, r;
	elem arr[N];
	int L = 0, R = 1;
	void build(){
		if(l.size() > 0 && r.size() > 0) return;
		int mi = (L + R) >> 1;
		if(L > R) mi = (L - N + R) >> 1;
		l.clear();
		r.clear();
		for(int i = mi; i != L; i = add(i, -1)){
			assert(i >= 0);
			l.push(arr[i]);
		} 
		for(int i = mi + 1; i != R; i = add(i, 1)){
			assert(i < N);
			r.push(arr[i]);
		} 
	}
	void push_front(elem x){
		arr[L] = x;
		l.push(x);
		L = add(L, -1);
		build();
	};
	void push_back(elem x){
		arr[R] = x;
		r.push(x);
		R = add(R, 1);
		build();
	};
	elem pop_front(){
		if(l.size() == 0) swap(l, r);
		L = add(L, 1);
		elem ret = l.pop();
		build();
		return ret;
	};
	elem pop_back(){
		if(r.size() == 0) swap(l, r);
		R = add(R, -1);
		elem ret = r.pop();
		build();
		return ret;
	};
	elem front(){
		return arr[add(L, 1)];
	};
	elem back(){
		return arr[add(R, -1)];
	};
	int size(){
		return l.size() + r.size();
	};
};

ll DP(int x){
	if(x < 0) return 0;
	return dp[x];
}

int solve(int n, int k, int* arr){
	elem res, p; 
	monodeck s;
	dp[0] = arr[0];
	p.val = arr[0];
	p.maxi = arr[0];
	p.ind = 0;
	s.push_back(p);
	for(int i = 1; i < n; i++){
		if(i >= k){
			res = s.front();
			if(res.ind == i - k) res = s.pop_front();
			p.val = dp[i - k] + res.maxi;
			p.maxi = res.maxi;
			p.ind = i - k + 1;
			if(res.ind != i - k + 1) s.push_front(p);
		}
		bool del = false;
		while(s.size() > 0 && s.back().maxi < arr[i]){
			res = s.pop_back();
			del = true;
		}
		if(del){
			p.val = DP(res.ind - 1) + arr[i];
			p.maxi = arr[i];
			p.ind = res.ind;
			s.push_back(p);
		}
		p.val = arr[i] + dp[i - 1];
		p.maxi = arr[i];
		p.ind = i;
		s.push_back(p);
		dp[i] = min(s.front().val, s.back().val);
		//printf("%d, ", dp[i]);
	}
	ll ans = 0;
	ll c = 1;
	for(int i = n - 1; i >= 0; i--){
		ans = MODadd(ans, MODmult(dp[i], c));
		c = MODmult(c, 23);
	}
	return ans;
}

Subtask #1
0 / 18.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 51.0

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