test/atcoder/agc018_c.test.cpp

View this file on GitHub
Last update: 2025-08-08 18:52:16+09:00
Problem: https://atcoder.jp/contests/agc018/tasks/agc018_c

Depends on

L凸関数最小化(スケーリング法) (src/Optimization/min_Lconvex.hpp)

Code

// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/agc018/tasks/agc018_c
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <algorithm>
#include "src/Optimization/min_Lconvex.hpp"
using namespace std;
// O(MAX_A log log MAX_A)
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int x[3], n= 0;
 for (int j= 0; j < 3; j++) cin >> x[j], n+= x[j];
 int c[n][3];
 for (int i= 0; i < n; i++)
  for (int j= 0; j < 3; j++) cin >> c[i][j];
 auto f= [&](const std::vector<int> &q) {
  long long ret= 0;
  for (int i= 0; i < n; i++) ret+= max({c[i][0] - q[0], c[i][1] - q[1], c[i][2] - q[2]});
  for (int j= 0; j < 3; j++) ret+= 1LL * x[j] * q[j];
  return ret;
 };
 cout << min_Lconvex<int, long long>(f, {0, 0, 0}, 1 << 29).first << '\n';
 return 0;
}

#line 1 "test/atcoder/agc018_c.test.cpp"
// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/agc018/tasks/agc018_c
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <algorithm>
#line 2 "src/Optimization/min_Lconvex.hpp"
#include <vector>
template <typename TD, typename TR, class F> std::pair<TR, std::vector<TD>> min_Lconvex(const F &f, std::vector<TD> x, TD alpha) {
 TR f0= f(x), f1= f0, fS;
 for (int n= x.size(); alpha; f0 == f1 ? alpha>>= 1 : f0= f1) {
  std::vector<TD> x0{x};
  for (int S= 1; S < (1 << n) - 1; S++) {
   std::vector<TD> xS{x0};
   for (int i= 0; i < n; i++)
    if ((S >> i) & 1) xS[i]+= alpha;
   if ((fS= f(xS)) < f1) f1= fS, x= std::move(xS);
  }
 }
 return {f1, std::move(x)};
}
#line 8 "test/atcoder/agc018_c.test.cpp"
using namespace std;
// O(MAX_A log log MAX_A)
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int x[3], n= 0;
 for (int j= 0; j < 3; j++) cin >> x[j], n+= x[j];
 int c[n][3];
 for (int i= 0; i < n; i++)
  for (int j= 0; j < 3; j++) cin >> c[i][j];
 auto f= [&](const std::vector<int> &q) {
  long long ret= 0;
  for (int i= 0; i < n; i++) ret+= max({c[i][0] - q[0], c[i][1] - q[1], c[i][2] - q[2]});
  for (int j= 0; j < 3; j++) ret+= 1LL * x[j] * q[j];
  return ret;
 };
 cout << min_Lconvex<int, long long>(f, {0, 0, 0}, 1 << 29).first << '\n';
 return 0;
}