test/yukicoder/952.monotone_minima.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 13:40:30+09:00
• Problem: https://yukicoder.me/problems/no/952

Depends on

• monotone minima (src/Optimization/monotone_minima.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/952
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <numeric>
#include "src/Optimization/monotone_minima.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 cin >> N;
 int A[N];
 for (int i= 0; i < N; ++i) cin >> A[i];
 long long S[N + 1], dp[N + 2], ans[N];
 S[0]= 0;
 for (int i= 0; i < N; ++i) S[i + 1]= S[i] + A[i];
 static constexpr long long INF= 1e17;
 fill_n(dp, N + 2, INF), dp[0]= 0;
 auto w= [&](int i, int j) { return (S[i] - S[j]) * (S[i] - S[j]); };
 for (int l= N; l--;) {
  auto select= [&](int i, int j, int k) { return dp[j] + w(i - 1, j) > dp[k] + w(i - 1, k); };
  auto id= monotone_minima(N + 2, N + 1, select);
  for (int i= N + 2; --i;) {
   int j= id[i];
   dp[i]= dp[j] + w(i - 1, j);
  }
  dp[0]= INF;
  ans[l]= dp[N + 1];
 }
 for (int i= 0; i < N; ++i) cout << ans[i] << '\n';
 return 0;
}

#line 1 "test/yukicoder/952.monotone_minima.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/952
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <numeric>
#line 2 "src/Optimization/monotone_minima.hpp"
#include <vector>
// select(i,j,k) -> true if (i,k) is better than (i,j)
template <typename F> std::vector<int> monotone_minima(int H, int W, const F &select) {
 std::vector<int> ret(H);
 auto rec= [&](auto &rec, int h1, int h2, int w1, int w2) -> void {
  if (h1 == h2) return;
  int h= (h1 + h2) / 2, best_w= w1;
  for (int w= w1 + 1; w < w2; ++w)
   if (select(h, best_w, w)) best_w= w;
  ret[h]= best_w, rec(rec, h1, h, w1, best_w + 1), rec(rec, h + 1, h2, best_w, w2);
 };
 return rec(rec, 0, H, 0, W), ret;
}
#line 7 "test/yukicoder/952.monotone_minima.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 cin >> N;
 int A[N];
 for (int i= 0; i < N; ++i) cin >> A[i];
 long long S[N + 1], dp[N + 2], ans[N];
 S[0]= 0;
 for (int i= 0; i < N; ++i) S[i + 1]= S[i] + A[i];
 static constexpr long long INF= 1e17;
 fill_n(dp, N + 2, INF), dp[0]= 0;
 auto w= [&](int i, int j) { return (S[i] - S[j]) * (S[i] - S[j]); };
 for (int l= N; l--;) {
  auto select= [&](int i, int j, int k) { return dp[j] + w(i - 1, j) > dp[k] + w(i - 1, k); };
  auto id= monotone_minima(N + 2, N + 1, select);
  for (int i= N + 2; --i;) {
   int j= id[i];
   dp[i]= dp[j] + w(i - 1, j);
  }
  dp[0]= INF;
  ans[l]= dp[N + 1];
 }
 for (int i= 0; i < N; ++i) cout << ans[i] << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	sample_1	AC	6 ms	3 MB
g++-13	sample_2	AC	5 ms	4 MB
g++-13	sample_3	AC	5 ms	4 MB
g++-13	testcase_1.txt	AC	243 ms	4 MB
g++-13	testcase_10.txt	AC	137 ms	4 MB
g++-13	testcase_11.txt	AC	144 ms	4 MB
g++-13	testcase_12.txt	AC	34 ms	4 MB
g++-13	testcase_13.txt	AC	215 ms	4 MB
g++-13	testcase_14.txt	AC	43 ms	4 MB
g++-13	testcase_15.txt	AC	34 ms	4 MB
g++-13	testcase_16.txt	AC	58 ms	4 MB
g++-13	testcase_17.txt	AC	7 ms	4 MB
g++-13	testcase_18.txt	AC	6 ms	4 MB
g++-13	testcase_19.txt	AC	123 ms	4 MB
g++-13	testcase_2.txt	AC	240 ms	4 MB
g++-13	testcase_20.txt	AC	28 ms	4 MB
g++-13	testcase_3.txt	AC	190 ms	4 MB
g++-13	testcase_4.txt	AC	297 ms	4 MB
g++-13	testcase_5.txt	AC	94 ms	4 MB
g++-13	testcase_6.txt	AC	339 ms	4 MB
g++-13	testcase_7.txt	AC	344 ms	4 MB
g++-13	testcase_8.txt	AC	128 ms	4 MB
g++-13	testcase_9.txt	AC	7 ms	4 MB
g++-13	testcase_tester_01.txt	AC	6 ms	3 MB
g++-13	testcase_tester_02.txt	AC	13 ms	3 MB
g++-13	testcase_tester_03.txt	AC	375 ms	4 MB
clang++-18	sample_1	AC	6 ms	4 MB
clang++-18	sample_2	AC	6 ms	4 MB
clang++-18	sample_3	AC	5 ms	4 MB
clang++-18	testcase_1.txt	AC	111 ms	4 MB
clang++-18	testcase_10.txt	AC	66 ms	4 MB
clang++-18	testcase_11.txt	AC	69 ms	4 MB
clang++-18	testcase_12.txt	AC	20 ms	4 MB
clang++-18	testcase_13.txt	AC	100 ms	4 MB
clang++-18	testcase_14.txt	AC	24 ms	4 MB
clang++-18	testcase_15.txt	AC	20 ms	4 MB
clang++-18	testcase_16.txt	AC	31 ms	4 MB
clang++-18	testcase_17.txt	AC	7 ms	4 MB
clang++-18	testcase_18.txt	AC	6 ms	4 MB
clang++-18	testcase_19.txt	AC	59 ms	4 MB
clang++-18	testcase_2.txt	AC	110 ms	4 MB
clang++-18	testcase_20.txt	AC	17 ms	4 MB
clang++-18	testcase_3.txt	AC	88 ms	4 MB
clang++-18	testcase_4.txt	AC	135 ms	4 MB
clang++-18	testcase_5.txt	AC	48 ms	4 MB
clang++-18	testcase_6.txt	AC	154 ms	4 MB
clang++-18	testcase_7.txt	AC	156 ms	4 MB
clang++-18	testcase_8.txt	AC	63 ms	4 MB
clang++-18	testcase_9.txt	AC	7 ms	4 MB
clang++-18	testcase_tester_01.txt	AC	6 ms	4 MB
clang++-18	testcase_tester_02.txt	AC	10 ms	4 MB
clang++-18	testcase_tester_03.txt	AC	159 ms	4 MB

Back to top page