test/aoj/2603.monotone_minima.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 10:56:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2603

Depends on

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

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2603
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <algorithm>
#include "src/Optimization/monotone_minima.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int s, n, m;
 cin >> s >> n >> m;
 int x[s];
 for (int i= 0; i < s; ++i) cin >> x[i];
 int a[n];
 for (int i= 0; i < n; ++i) {
  int t, p;
  cin >> t >> p;
  a[i]= t - x[p - 1];
 }
 if (n <= m) return cout << 0 << '\n', 0;
 sort(a, a + n);
 int sum[n + 1];
 sum[0]= 0;
 for (int i= 0; i < n; ++i) sum[i + 1]= sum[i] + a[i];
 auto w= [&](int i, int j) { return (i - j) * a[i - 1] - (sum[i] - sum[j]); };

 int dp[n + 1];
 fill_n(dp, n + 1, 1e9);
 dp[0]= 0;
 for (int _= m; _--;) {
  auto select= [&](int i, int j, int k) { return dp[j] + w(i, j) > dp[k] + w(i, k); };
  auto id= monotone_minima(n + 1, n + 1, select);
  for (int i= n; i > 0; --i) {
   int j= id[i];
   dp[i]= dp[j] + w(i, j);
  }
 }
 cout << dp[n] << '\n';
 return 0;
}

#line 1 "test/aoj/2603.monotone_minima.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2603
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <algorithm>
#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/aoj/2603.monotone_minima.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int s, n, m;
 cin >> s >> n >> m;
 int x[s];
 for (int i= 0; i < s; ++i) cin >> x[i];
 int a[n];
 for (int i= 0; i < n; ++i) {
  int t, p;
  cin >> t >> p;
  a[i]= t - x[p - 1];
 }
 if (n <= m) return cout << 0 << '\n', 0;
 sort(a, a + n);
 int sum[n + 1];
 sum[0]= 0;
 for (int i= 0; i < n; ++i) sum[i + 1]= sum[i] + a[i];
 auto w= [&](int i, int j) { return (i - j) * a[i - 1] - (sum[i] - sum[j]); };

 int dp[n + 1];
 fill_n(dp, n + 1, 1e9);
 dp[0]= 0;
 for (int _= m; _--;) {
  auto select= [&](int i, int j, int k) { return dp[j] + w(i, j) > dp[k] + w(i, k); };
  auto id= monotone_minima(n + 1, n + 1, select);
  for (int i= n; i > 0; --i) {
   int j= id[i];
   dp[i]= dp[j] + w(i, j);
  }
 }
 cout << dp[n] << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.txt	AC	5 ms	4 MB
g++-13	00_sample_01.txt	AC	5 ms	4 MB
g++-13	00_sample_02.txt	AC	5 ms	4 MB
g++-13	01_teuchi_00.txt	AC	5 ms	4 MB
g++-13	99_large_random_0.txt	AC	5 ms	4 MB
g++-13	99_large_random_1.txt	AC	5 ms	4 MB
g++-13	99_large_random_2.txt	AC	8 ms	4 MB
g++-13	99_large_random_3.txt	AC	5 ms	4 MB
g++-13	99_large_random_4.txt	AC	5 ms	4 MB
g++-13	99_large_random_5.txt	AC	5 ms	4 MB
g++-13	99_large_random_6.txt	AC	12 ms	4 MB
g++-13	99_large_random_7.txt	AC	5 ms	4 MB
g++-13	99_large_random_8.txt	AC	5 ms	4 MB
g++-13	99_large_random_9.txt	AC	5 ms	4 MB
g++-13	99_max_random_0.txt	AC	35 ms	4 MB
g++-13	99_max_random_1.txt	AC	25 ms	4 MB
g++-13	99_max_random_2.txt	AC	48 ms	4 MB
g++-13	99_max_random_3.txt	AC	61 ms	4 MB
g++-13	99_max_random_4.txt	AC	50 ms	4 MB
g++-13	99_max_random_5.txt	AC	53 ms	4 MB
g++-13	99_max_random_6.txt	AC	72 ms	4 MB
g++-13	99_max_random_7.txt	AC	90 ms	4 MB
g++-13	99_max_random_8.txt	AC	8 ms	4 MB
g++-13	99_max_random_9.txt	AC	10 ms	4 MB
g++-13	99_middle_random_0.txt	AC	5 ms	4 MB
g++-13	99_middle_random_1.txt	AC	5 ms	4 MB
g++-13	99_middle_random_2.txt	AC	5 ms	4 MB
g++-13	99_middle_random_3.txt	AC	5 ms	4 MB
g++-13	99_middle_random_4.txt	AC	5 ms	4 MB
g++-13	99_middle_random_5.txt	AC	5 ms	4 MB
g++-13	99_middle_random_6.txt	AC	6 ms	4 MB
g++-13	99_middle_random_7.txt	AC	5 ms	4 MB
g++-13	99_middle_random_8.txt	AC	5 ms	3 MB
g++-13	99_middle_random_9.txt	AC	5 ms	4 MB
g++-13	99_small_random_0.txt	AC	5 ms	4 MB
g++-13	99_small_random_1.txt	AC	4 ms	4 MB
g++-13	99_small_random_2.txt	AC	5 ms	3 MB
g++-13	99_small_random_3.txt	AC	4 ms	4 MB
g++-13	99_small_random_4.txt	AC	5 ms	4 MB
g++-13	99_small_random_5.txt	AC	5 ms	4 MB
g++-13	99_small_random_6.txt	AC	5 ms	4 MB
g++-13	99_small_random_7.txt	AC	5 ms	4 MB
g++-13	99_small_random_8.txt	AC	5 ms	3 MB
g++-13	99_small_random_9.txt	AC	4 ms	4 MB
g++-13	99_tiny_random_0.txt	AC	5 ms	3 MB
g++-13	99_tiny_random_1.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_2.txt	AC	4 ms	4 MB
g++-13	99_tiny_random_3.txt	AC	4 ms	4 MB
g++-13	99_tiny_random_4.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_5.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_6.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_7.txt	AC	4 ms	4 MB
g++-13	99_tiny_random_8.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_9.txt	AC	5 ms	4 MB
clang++-18	00_sample_00.txt	AC	5 ms	4 MB
clang++-18	00_sample_01.txt	AC	5 ms	4 MB
clang++-18	00_sample_02.txt	AC	5 ms	4 MB
clang++-18	01_teuchi_00.txt	AC	4 ms	4 MB
clang++-18	99_large_random_0.txt	AC	5 ms	4 MB
clang++-18	99_large_random_1.txt	AC	5 ms	4 MB
clang++-18	99_large_random_2.txt	AC	7 ms	4 MB
clang++-18	99_large_random_3.txt	AC	5 ms	4 MB
clang++-18	99_large_random_4.txt	AC	5 ms	4 MB
clang++-18	99_large_random_5.txt	AC	4 ms	4 MB
clang++-18	99_large_random_6.txt	AC	8 ms	4 MB
clang++-18	99_large_random_7.txt	AC	5 ms	4 MB
clang++-18	99_large_random_8.txt	AC	4 ms	4 MB
clang++-18	99_large_random_9.txt	AC	5 ms	4 MB
clang++-18	99_max_random_0.txt	AC	20 ms	4 MB
clang++-18	99_max_random_1.txt	AC	15 ms	4 MB
clang++-18	99_max_random_2.txt	AC	25 ms	4 MB
clang++-18	99_max_random_3.txt	AC	30 ms	4 MB
clang++-18	99_max_random_4.txt	AC	26 ms	4 MB
clang++-18	99_max_random_5.txt	AC	27 ms	4 MB
clang++-18	99_max_random_6.txt	AC	35 ms	4 MB
clang++-18	99_max_random_7.txt	AC	44 ms	4 MB
clang++-18	99_max_random_8.txt	AC	7 ms	4 MB
clang++-18	99_max_random_9.txt	AC	8 ms	4 MB
clang++-18	99_middle_random_0.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_1.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_2.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_3.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_4.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_5.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_6.txt	AC	6 ms	4 MB
clang++-18	99_middle_random_7.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_8.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_9.txt	AC	5 ms	4 MB
clang++-18	99_small_random_0.txt	AC	5 ms	4 MB
clang++-18	99_small_random_1.txt	AC	5 ms	4 MB
clang++-18	99_small_random_2.txt	AC	5 ms	4 MB
clang++-18	99_small_random_3.txt	AC	5 ms	4 MB
clang++-18	99_small_random_4.txt	AC	5 ms	4 MB
clang++-18	99_small_random_5.txt	AC	5 ms	4 MB
clang++-18	99_small_random_6.txt	AC	5 ms	4 MB
clang++-18	99_small_random_7.txt	AC	5 ms	4 MB
clang++-18	99_small_random_8.txt	AC	5 ms	4 MB
clang++-18	99_small_random_9.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_0.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_1.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_2.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_3.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_4.txt	AC	4 ms	4 MB
clang++-18	99_tiny_random_5.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_6.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_7.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_8.txt	AC	4 ms	4 MB
clang++-18	99_tiny_random_9.txt	AC	5 ms	4 MB

Back to top page