Submission #1190676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190676		pcheloveks	Peru (RMI20_peru)	C++20	0 / 100	1097 ms	29832 KiB

peru

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")

//Andrusha Holod did not qualify to IOI 2025 )))
//Hope Andrusha Holod will win IOI 2026

#include "peru.h"

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset

#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef pair < ll, ull > piu;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;

const ll DIM = 100007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;

const ll dx[5] = { -1, -1, 0, 1, 0 };
const ll dy[5] = { -1, 0, -1, 0, 1 };

FILE* stream;

int maxQuery(int L, int R, int* S) {
	ll res = -INF;
	for (int i = L; i <= R; i++) {
		res = max(res, (ll)S[i]);
	}
	return res;
}

int n, k;

int solve(int N, int K, int* S) {
	n = N;
	k = K;

	vector < ll > F(n);

	for (int i = 0; i < k; i++) {
		F[i] = maxQuery(0, i, S);
	}

	for (int i = k; i < n; i++) {
		ll mx = S[i];
		F[i] = INF;
		for (int j = i - 1; j >= i - k; j--) {
			F[i] = min(F[i], mx + F[j]);
			mx = max(mx, (ll)S[j]);
		}
	}

	vector < ll > powers(n);
	powers[0] = 1;
	for (int i = 1; i < n; i++) powers[i] = (powers[i - 1] * 23) % mod;

	ll res = 0;
	for (int i = 0; i < n; i++) {
		res += F[i] * powers[n - 1 - i];
		res %= mod;
	}
	return res;
}

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