| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1176843 | _unknown_2010 | Ski 2 (JOI24_ski2) | C++20 | 0 ms | 0 KiB |
//#ifndef LOCAL
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int int64_t
#define vi vector
#define ss second
#define ff first
#define TESTCASES
#define all(x) (x).begin(), (x).end()
const int mod = 1E9+7;
const int MAXN=200000;
const int inf=1e18;
#ifndef khos
#define debug(...) 42
#endif
#define debug(args...) \
{ \
cout << "[" << #args << "]: "; \
my::debug::debug_out(args); \
cout << endl; \
}
namespace my::debug {
using std::cout;
template <typename T, typename = void>
struct is_container : std::false_type {};
template <typename T>
struct is_container<T, std::void_t<decltype(std::begin(std::declval<T>()))>>
: std::true_type {};
template <typename T>
constexpr bool is_container_v = is_container<T>::value;
template <typename Test, template <typename...> class Ref>
struct is_specialization : std::false_type {};
template <template <typename...> class Ref, typename... Args>
struct is_specialization<Ref<Args...>, Ref> : std::true_type {};
template <typename Test, template <typename...> class Ref>
constexpr bool is_specialization_v = is_specialization<Test, Ref>::value;
// https://stackoverflow.com/a/47563100
template <std::size_t N>
struct num {
static const constexpr auto value = N;
};
template <class F, std::size_t... Is>
void for_(F func, std::index_sequence<Is...>) {
(func(num<Is>{}), ...);
}
template <std::size_t N, typename F>
void for_(F func) {
for_(func, std::make_index_sequence<N>());
}
template <typename T>
constexpr auto is_coutable(int)
-> decltype(std::cout << std::declval<T>(), std::true_type{}) {
return std::true_type{};
}
template <typename T>
constexpr std::false_type is_coutable(...) {
return std::false_type{};
}
template <typename T>
constexpr bool is_coutable_v = decltype(is_coutable<T>(0))::value;
template <typename T>
void single_out(T x) {
if constexpr (std::is_same_v<T, std::string> | std::is_same_v<T, char*> ||
std::is_same_v<T, const char*>) {
cout << '"' << x << '"';
} else if constexpr (std::is_same_v<T, char>) {
cout << x;
} else if constexpr (std::is_integral_v<T> || std::is_floating_point_v<T> ||
std::is_enum_v<T> || std::is_pointer_v<T>) {
cout << x;
} else if constexpr (is_specialization_v<T, std::pair>) {
cout << "(";
single_out(x.first);
cout << ", ";
single_out(x.second);
cout << ")";
} else if constexpr (is_specialization_v<T, std::tuple>) {
cout << "(";
std::string sep = "";
for_<std::tuple_size_v<T>>([&](auto i) {
cout << exchange(sep, ", ");
single_out(std::get<i.value>(x));
});
cout << ")";
} else if constexpr (is_specialization_v<T, std::map> ||
is_specialization_v<T, std::unordered_map>) {
cout << "{";
std::string sep = "";
for (auto [k, v] : x) {
cout << exchange(sep, ", ");
single_out(k);
cout << ": ";
single_out(v);
}
cout << "}";
} else if constexpr (is_container_v<T>) {
if constexpr (is_specialization_v<T, std::vector>) {
cout << "[";
} else cout << "{";
std::string sep = "";
for (auto i : x) {
cout << exchange(sep, ", ");
single_out(i);
}
if constexpr (is_specialization_v<T, std::vector>) {
cout << "]";
} else cout << "}";
}
// types without iterator, f*** you, c++ comittee
else if constexpr (is_specialization_v<T, std::queue>) {
cout << "{";
std::string sep = "";
while (x.size()) {
cout << exchange(sep, ", ");
single_out(x.front());
x.pop();
}
cout << "}";
} else if constexpr (is_specialization_v<T, std::stack> ||
is_specialization_v<T, std::priority_queue>) {
std::vector<
std::remove_cv_t<std::remove_reference_t<decltype(x.top())>>>
v;
while (x.size()) {
v.push_back(x.top());
x.pop();
}
if constexpr (is_specialization_v<T, std::stack>)
std::reverse(v.begin(), v.end());
cout << "{";
std::string sep = "";
for (auto i : v) {
cout << exchange(sep, ", ");
single_out(i);
}
cout << "}";
}
// lastly, if the expression (cout << x) compiles, use it
else {
static_assert(is_coutable_v<T>, "The type given to debug() is not supported.");
cout << x;
}
}
template <typename T, typename... Rest>
void debug_out(T, Rest...);
void debug_out();
template <typename T, typename... Rest>
void debug_out(T x, Rest... rest) {
// single_out<std::remove_cv_t<std::decay_t<T>>>(x);
single_out<std::remove_cv_t<T>>(x);
if (sizeof...(rest) > 0) cout << ", ";
debug_out(rest...);
}
void debug_out() {
}
}; // namespace my::debug
struct hotel{
int h,c;
};
void solution(){
int n,k;
cin >> n >> k;
vi<hotel> a(n);
for(int i=0; i<n; i++){
cin >> a[i].h >> a[i].c;
}
int mn=inf;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int ans=0;
for(int z=0; z<n; z++){
if(z==j)continue;
if(i==z){
ans+=k*max(a[j].h+1-a[z].h,0LL);
}
else {
ans+=k*max(max(a[j].h+1,a[i].h)+1-a[z].h,0LL);
}
}
if(i==j){
ans+=(n-2)*(a[j].c);
}
else {
ans+=(n-3)*(a[i].c);
}
mn=min(mn,ans);
}
}
cout << mn;
}
int32_t main(){
clock_t tStart = clock();
#ifdef khos
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q = 1;
#ifdef TESTCASES
// cin >> q;
#endif
while(q--) {
solution();
cout << '\n';
}
cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}