제출 #1061763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1061763		MilosMilutinovic	Peru (RMI20_peru)	C++14	18 / 100	785 ms	9848 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>

using namespace std;

const int md = 1e9 + 7;

int add(int x, int y) {
  return x + y < md ? x + y : x + y - md;
}

int mul(int x, int y) {
  return x * 1LL * y % md;
}

int solve(int n, int k, int* v) {
  const long long inf = (long long) 1e18;
  vector<long long> dp(n, inf);
  for (int i = 0; i < n; i++) {
    int mx = 0;
    for (int j = i; j >= 0; j--) {
      if (i - j + 1 > k) {
        break;
      }
      mx = max(mx, v[j]);
      dp[i] = min(dp[i], (j == 0 ? 0LL : dp[j - 1]) + mx);
    }
  }
  int res = 0;
  int pw = 1;
  for (int i = n - 1; i >= 0; i--) {
    dp[i] %= md;
    res = add(res, mul(pw, dp[i]));
    pw = mul(pw, 23);
  }
  return res;
}

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