Submission #737212

#	Time	Username	Problem	Language	Result	Execution time	Memory
737212		lobo_prix	Potatoes and fertilizers (LMIO19_bulves)	C++17	24 / 100	1064 ms	96972 KiB

bulves

//[Author]   tuxedcat
//[Date]     2023.05.07 06:51:05 KST
//[File]     src/b.cpp
//[Library]  https://github.com/tuxedcat/ps.cpp
//[Revision] e876fc2f8914923aefbd4b1a0920d88253b54882
/* ORIGINAL_MAIN_SOURCE
#include "core/base.h"
signed main(){
	void solve();
	// for(int ti=1,t=get<0>(input());ti<=t;ti++)
		// print("Case #",ti,": "),
		solve();
	assert(cin.get()=='\n');
	assert(cin.get()==EOF);
}
// #include "dp/slope.h"
void solve(){
	int n; cin>>n;
	Arr<int> a(n);
	for(int i=0;i<n;i++){
		int x,y; cin>>x>>y;
		a[i]=x-y;
	}
	Arr<int> b(n+1);
	partial_sum(a.begin(),a.end(),b.begin());
	auto dp=ARR(n,b[n-1]+1,-1ll);
	func(int,f,int x,int y){
		if(x==-1)
			return 0;
		auto&r=dp[x][y];
		if(~r)return r;
		r=inf<int>();
		for(int i=0;i<=y;i++)
			r=min(r,f(x-1,i))+abs(b[x]-y);
		return r;
	};
	println(f(n-1,b[n-1]));
}
*/
#include <bits/stdc++.h>
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
using namespace std;
#pragma GCC diagnostic ignored "-Wparentheses"
#define SYSCALL_ALLOWED 1
#if SYSCALL_ALLOWED
	#include <bits/extc++.h>
	#include <ext/rope>
#endif

using fp = double;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using pint = pair<i64, i64>;
using tint = tuple<i64, i64, i64>;
template <class T>
using Str = basic_string<T>;
template <class T, class CMP = less<>>
using PQ = std::priority_queue<T, vector<T>, CMP>;
template <class T>
i64 sz(const T& x) {
  return x.size();
}
i64 fdiv(i64 a, i64 b) {
  if (b < 0) a = -a, b = -b;
  return (a > 0) ? a / b : (a - b + 1) / b;
}
i64 cdiv(i64 a, i64 b) {
  if (b < 0) a = -a, b = -b;
  return (a > 0) ? (a + b - 1) / b : a / b;
}
i64 flg2(u64 x) { return 63 - __builtin_clzll(x); }
i64 clg2(u64 x) { return x - 1 == 0 ? 0 : 64 - __builtin_clzll(x - 1); }
i64 fsqrt(i64 n) {
  i64 i = 0;
  while (i * i <= n) i++;
  return i - 1;
}
i64 csqrt(i64 n) {
  i64 i = 0;
  while (i * i < n) i++;
  return i;
}
template <class T>
T sq(T x) {
  return x * x;
}
template <class T>
constexpr T inf() {
  return numeric_limits<T>::max() / 2;
}
template <class... A>
ostream& osprint(ostream& os, A... a) {
  return ((os << a), ...);
}
template <class T, class U>
bool assmin(T& a, U&& b) {
  return a > b ? a = b, true : false;
}
template <class T, class U>
bool assmax(T& a, U&& b) {
  return a < b ? a = b, true : false;
}
auto key2cmp(auto key) {
  return [key](auto x, auto y) {
    return make_pair(key(x), x) < make_pair(key(y), y);
  };
}
template <class T, class P = vector<T>>
struct Arr : public P {
  Arr() { P::shrink_to_fit(); }
  explicit Arr(signed n) : P(n) {}
  explicit Arr(signed n, T init) : P(n, init) {}
  Arr(initializer_list<T> il) : P(il) {}
  Arr(auto its, auto ite) : P(its, ite) {}
  inline T& operator[](signed i) {
    assert(-sz(*this) <= i && i < sz(*this));
    return P::operator[](i < 0 ? i + sz(*this) : i);
  }
  const T& operator[](signed i) const {
    assert(-sz(*this) <= i && i < sz(*this));
    return P::operator[](i < 0 ? i + sz(*this) : i);
  }
  T& at(signed i) { return *this[i]; }
  const T& at(signed i) const { return *this[i]; }
};
template <class... A>
auto ARR(auto n, A&&... a) {
  if constexpr (!sizeof...(a))
    return n;
  else
    return Arr(n, ARR(a...));
}
const fp pi = acos(-1), eps = 1e-11;
const i64 dir4[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
const i64 dir8[8][2] = {{0, 1},  {-1, 1}, {-1, 0}, {-1, -1},
                        {0, -1}, {1, -1}, {1, 0},  {1, 1}};
template <class T>
i64 argmin(const Arr<T>& a) {
  return min_element(a.begin(), a.end()) - a.begin();
}
template <class T>
i64 argmax(const Arr<T>& a) {
  return max_element(a.begin(), a.end()) - a.begin();
}
template <class T>
map<typename T::value_type, Arr<i64>> classify(const T& a) {
  map<typename T::value_type, Arr<i64>> r;
  i64 idx = 0;
  for (auto x : a) r[x].push_back(idx++);
  return r;
}
auto __PR = (cout << fixed << setprecision(10), 0);
auto __PR_NDB = (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0));
signed main() {
  void solve();
  solve();
  assert(cin.get() == '\n');
  assert(cin.get() == EOF);
}
void solve() {
  i64 n;
  cin >> n;
  Arr<i64> a(n);
  for (i64 i = 0; i < n; i++) {
    i64 x, y;
    cin >> x >> y;
    a[i] = x - y;
  }
  Arr<i64> b(n + 1);
  partial_sum(a.begin(), a.end(), b.begin());
  auto dp = ARR(n, b[n - 1] + 1, -1ll);
  function<i64(i64 x, i64 y)> f = [&](i64 x, i64 y) -> i64 {
    if (x == -1) return 0;
    auto& r = dp[x][y];
    if (~r) return r;
    r = inf<i64>();
    for (i64 i = 0; i <= y; i++) r = min(r, f(x - 1, i)) + abs(b[x] - y);
    return r;
  };
  osprint(cout, f(n - 1, b[n - 1]), '\n');
}

Compilation message (stderr)

bulves.cpp:105:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  105 | auto key2cmp(auto key) {
      |              ^~~~
bulves.cpp:116:7: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  116 |   Arr(auto its, auto ite) : P(its, ite) {}
      |       ^~~~
bulves.cpp:116:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  116 |   Arr(auto its, auto ite) : P(its, ite) {}
      |                 ^~~~
bulves.cpp:129:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  129 | auto ARR(auto n, A&&... a) {
      |          ^~~~

• Subtask 1: 24 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36