Submission #1305425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305425		cheat_when_I_was_young	Cloud Computing (CEOI18_clo)	C++20	100 / 100	235 ms	1096 KiB

clo

#include "bits/stdc++.h"
#ifdef LOCAL
#include <windows.h>
#include <psapi.h>
#endif
using namespace std;
template<typename T>
struct is_pair: false_type{};
template<typename F, typename S>
struct is_pair<pair<F, S>>: true_type{};
template<typename T>
concept Pair = is_pair<remove_cvref_t<T>>::value;
template<typename T>
struct is_tuple: false_type{};
template<typename... Ts>
struct is_tuple<tuple<Ts...>>: true_type{};
template<typename T>
concept Tuple = is_tuple<remove_cvref_t<T>>::value;
template<typename T>
concept Range = ranges::range<T> && !is_convertible_v<T, string_view>;
template<typename T>
concept Composite = Range<T> || Pair<T> || Tuple<T>;
unsigned __int128 read_uint128(string_view sv) {
    unsigned __int128 x = 0;
    for (char c: sv) x = x * 10 + (c - '0');
    return x;
}
istream& operator >> (istream &is, __int128 &x) {
    string s;
    is >> s;
    if (s[0] == '-') x = -read_uint128(string_view(s).substr(1));
    else if (s[0] == '+') x = read_uint128(string_view(s).substr(1));
    else x = read_uint128(string_view(s));
    return is;
}
istream& operator >> (istream &is, unsigned __int128 &x) {
    string s;
    is >> s;
    x = read_uint128(string_view(s));
    return is;
}
template<Range R> istream& operator >> (istream &is, R &r);
template<typename F, typename S> istream& operator >> (istream &is, pair<F, S> &p);
template<typename... Ts> istream& operator >> (istream &is, tuple<Ts...> &t);
template<Range R>
istream& operator >> (istream &is, R &r) {
    for (auto &i: r) is >> i;
    return is;
}
template<typename F, typename S>
istream& operator >> (istream &is, pair<F, S> &p) {
    return is >> p.first >> p.second;
}
template<typename... Ts>
istream& operator >> (istream &is, tuple<Ts...> &t) {
    apply([&](auto&... elems) {((is >> elems), ...);}, t);
    return is;
}
ostream& print_uint128(ostream &os, const unsigned __int128 &x) {
    if (x >= 10) print_uint128(os, x / 10);
    return os << (char)(x % 10 + '0');
}
ostream& operator << (ostream &os, const __int128 &x) {
    if (x < 0) {
        os << '-';
        return print_uint128(os, -(unsigned __int128)x);
    }
    return print_uint128(os, x);
}
ostream& operator << (ostream &os, const unsigned __int128 &x) {
    return print_uint128(os, x);
}
template<Range R> ostream& operator << (ostream &os, R &&r);
template<typename F, typename S> ostream& operator << (ostream &os, const pair<F, S> &p);
template<typename... Ts> ostream& operator << (ostream &os, const tuple<Ts...> &t);
template<Range R>
ostream& operator << (ostream &os, R &&r) {
    string s;
    for (auto &&i: r) {
        os << s << i;
        if constexpr (Composite<decltype(i)>) s = "\n";
        else s = " ";
    }
    return os;
}
template<typename F, typename S>
ostream& operator << (ostream &os, const pair<F, S> &p) {
    return os << p.first << ' ' << p.second;
}
template<typename... Ts>
ostream& operator << (ostream &os, const tuple<Ts...> &t) {
    string s;
    apply([&](const auto&... elems) {((os << s << elems, s = " "), ...);}, t);
    return os;
}
template<typename T>
auto make_vector(size_t n) {
    return vector<T>(n);
}
template<typename T, typename... Args>
auto make_vector(size_t n, const Args&... args) {
    return vector<decltype(make_vector<T>(args...))>(n, make_vector<T>(args...));
}
template<typename T>
auto make_filled_vector(size_t n, const T &val) {
    return vector<T>(n, val);
}
template<typename T, typename... Args>
auto make_filled_vector(size_t n, const Args&... args) {
    return vector<decltype(make_filled_vector<T>(args...))>(n, make_filled_vector<T>(args...));
}
template<typename T, size_t N>
struct vec { using type = vector<typename vec<T, N - 1>::type>; };
template<typename T>
struct vec<T, 1> { using type = vector<T>; };
template<typename T, size_t N>
using vector_type = typename vec<T, N>::type;
void khac();
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(ios::badbit | ios::failbit);
    #ifdef LOCAL
        PROCESS_MEMORY_COUNTERS pmc;
        GetProcessMemoryInfo(GetCurrentProcess(), &pmc, sizeof(pmc));
        auto start_memory = pmc.PeakWorkingSetSize;
        auto start_time = chrono::high_resolution_clock::now();
    #endif
    khac();
    #ifdef LOCAL
        auto end_time = chrono::high_resolution_clock::now();
        GetProcessMemoryInfo(GetCurrentProcess(), &pmc, sizeof(pmc));
        auto end_memory = pmc.PeakWorkingSetSize;
        auto used_time = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
        auto used_memory = (end_memory - start_memory) / 1048576.0;
        cout << "\n=====\nUsed: " << used_time << " ms, ";
        cout << fixed << setprecision(3) << used_memory << " MB";
    #endif
}

void khac() {
    int n;
    cin >> n;
    vector<array<int, 3>> a(n);
    cin >> a;
    int m;
    cin >> m;
    vector<array<int, 3>> b(m);
    cin >> b;

    sort(b.begin(), b.end(), [] (const array<int, 3> &x, const array<int, 3> &y) {
        return x[1] < y[1];        
    });

    vector<long long> dp(n * 50 + 1, -1e18);
    dp[0] = 0;
    for (int i = m - 1; i >= 0; --i) {
        int l = b[i][1], r = i != m - 1 ? b[i + 1][1] - 1 : 1e9;
        auto &[C, F, V] = b[i];
        for (auto &[c, f, v]: a) {
            if (f < l || f > r) continue;
            for (int j = n * 50 - c; j >= 0; --j) dp[j + c] = max(dp[j + c], dp[j] - v);
        }
        for (int j = C; j <= n * 50; ++j) dp[j - C] = max(dp[j - C], dp[j] + V);
    }
    cout << *max_element(dp.begin(), dp.end());
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10