제출 #1309444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309444		zaki98	Cloud Computing (CEOI18_clo)	C++20	100 / 100	230 ms	2152 KiB

clo

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef long long ll;
//#define int long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define dbg cout << "dbg" << endl;
#define all(c) (c).begin(), (c).end()
#define pii pair<int,int>
#define pll pair<long long, long long>
#define sz(a) (int)a.size()
#define smin(x,y) x = min(x,y)
#define smax(x,y) x = max(x,y)
// permutation of the last layer
#define LOO(i,a,b) for (ll i = a; i <= b; i++)
#define OOL(i,a,b) for (ll i = b; i >= a; i--)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
#define ld long double
#define YE cout << "YES\n"
#define NI cout << "NO\n"
#pragma GCC target("popcnt")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("avx2")
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

template <typename SS>
ostream& operator<<(ostream& os,
                    const vector<SS>& vector) {
    os << "{";
    for (auto i : vector)
        os << i << ", ";
    cout << "}";
    return os;
}


typedef tree<int,null_type, less_equal<>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
typedef tree<int,null_type, less<>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
ll constexpr MAX = 998244353;
void iO() {
    freopen("haircut.out", "w",stdout);
    freopen("haircut.in", "r",stdin);
}
vector<int> make_sorted_index(vector<ll> const &values) {
    vector<int> index(values.size());
    iota(index.begin(), index.end(), 0);
    stable_sort(index.begin(), index.end(), [&values](auto a, auto b) {
        return values[a] < values[b];
    });
    return index;
} // this function is so skibidi
vector<int> make_sorted_index(vector<int> const &values) {
    vector<int> index(values.size());
    iota(index.begin(), index.end(), 0);
    stable_sort(index.begin(), index.end(), [&values](auto a, auto b) {
        return values[a] < values[b];
    });
    return index;
} // this function is so skibidi
uint64_t splitmix(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

const uint64_t c1 = chrono::steady_clock::now().time_since_epoch().count();
const uint64_t c2 = splitmix(c1);
uint64_t mishmash(uint64_t a, uint64_t b) {
    return splitmix(c1*a+b + c2);
}
struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }

    int operator()(pii x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(FIXED_RANDOM * x.first + x.second + FIXED_RANDOM);
    }
}; // gp_hash_table custom hash so skibidi
std::random_device dev;
std::mt19937 rng(dev());
struct BIT {
    vector<ll> bit;  // binary indexed tree
    int n;
    BIT(int n) {
        this->n = n;
        bit.assign(n, 0);
    }
    BIT(int n, vector<int> vec) {
        this->n = n;
        bit.assign(n, 0);
        LOO(i,0,n-1) add(i, vec[i]);
    }

    ll s(int r) {
        ll ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }
    void add(int idx, ll delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] = (bit[idx]+delta)%MAX;
    }
    ll sum(int l, int r) {
        if (l>r) return 0;
        return (s(r)-(l==0 ? 0 : s(l-1)))%MAX;
    }
};
ll arith(ll n, ll step, ll a0) {
    ll prog = ((n)*(n-1)/2)%MAX;
    prog= step*prog%MAX;
    ll answ = (a0*n)%MAX + prog;
    return answ%MAX;
}
ll iSqrt(ll n) {
    if (n==0) return 0;
    ll lo = 1, hi = min((ll)1414213562, n); // long long
    ll res = 1;
    while(lo <= hi) {
        ll mid = lo + (hi - lo)/2;
        if(mid*mid <= n) {
            res = mid;
            lo = mid + 1;
        }
        else {
            hi = mid - 1;
        }
    }
    return res;
}
ll invmod(ll b) {
    b%=MAX;
    ll curr = 1; ll mt = b;
    ll exp = MAX-2;
    while (exp) {
        if (exp&1) curr=(curr*mt)%MAX;
        mt=mt*mt%MAX;
        exp>>=1;
    }
    return curr;
}
ll invmod(ll k, ll p)
{
    k %= p;
    if (k < 0) k += p;
    int neg = 1;
    ll p1 = 1, p2 = 0, k1 = k, m1 = p, q, r, temp;
    while(k1 > 0) {
        q = m1 / k1;
        r = m1 % k1;
        temp = q*p1 + p2;
        p2 = p1;
        p1 = temp;
        m1 = k1;
        k1 = r;
        neg = !neg;
    }
    return neg ? p - p2 : p2;
}
ll binpow(ll b, ll exp) {
    ll curr = 1; ll mt = b;
    while (exp) {
        if (exp&1) curr=(curr*mt)%MAX;
        mt=mt*mt%MAX;
        exp>>=1;
    }
    return curr;
}
ll binpow(ll b, ll exp, ll p) {
    ll curr = 1; ll mt = b;
    while (exp) {
        if (exp&1) curr=(curr*mt)%p;
        mt=mt*mt%p;
        exp>>=1;
    }
    return curr;
}
vector<int> LIS(vector<ll> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    vector<int> parent(n+1), ind(n+1);
    d[0] = -INF;
    ind[0]=-1;
    parent[0]=-1;
    for (int i = 0; i < n; i++) {
        int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[l-1] < a[i] && a[i] < d[l]) {
            d[l] = a[i];
            ind[l]=i;
            parent[i]=ind[l-1];
        }
    }
    int lastind = -1;
    for (int l = 0; l <= n; l++) {
        if (d[l] < INF) {
            lastind=l;
        }
    }
    lastind=ind[lastind];
    vector<int> ans={lastind};
    while (lastind!=-1) {
        if (parent[lastind]!=-1) ans.PB(parent[lastind]);
        lastind=parent[lastind];
    }
    reverse(all(ans));
    return ans;
}
ll dp[1'000'01];
ll dp2[1'000'01];
void solve(){
   int n;
    cin>>n;
    // freq, cores, price
    vector<pair<ll, pll>> cool(n);
    LOO(i,0,n-1) {
        cin>>cool[i].S.F;
        cin>>cool[i].F;
        cin>>cool[i].S.S;
        cool[i].S.F=-cool[i].S.F;
        cool[i].S.S=-cool[i].S.S;
        cool[i].F=-cool[i].F;
    }
    int m;
    cin>>m;
    cool.resize(n+m);
    LOO(i,n,n+m-1) {
        cin>>cool[i].S.F;
        cin>>cool[i].F;
        cin>>cool[i].S.S;
        cool[i].F=-cool[i].F;
    }

    n+=m;
    sort(all(cool));
    vector<pii> actual(n);
    LOO(i,0,n-1) {
        actual[i]=cool[i].S;
        actual[i].F=-actual[i].F;
    }
    LOO(i,0,1e5) {
        dp[i]=-1e18;
        dp2[i]=0;
    }
    dp[0]=dp2[0]=0;
    LOO(ind,0,n/2) {
        if (actual[ind].F>=0) {
            OOL(i,max(-actual[ind].F,0), min(1'000'00-actual[ind].F,1'000'00)) {
                smax(dp[i+actual[ind].F], dp[i]+actual[ind].S);
            }
        }
        else {
            LOO(i,max(-actual[ind].F,0), min(1'000'00-actual[ind].F,1'000'00)) {
                smax(dp[i+actual[ind].F], dp[i]+actual[ind].S);
            }
        }
    }
    OOL(ind,n/2+1, n-1) {
        actual[ind].F=-actual[ind].F;
        if (actual[ind].F>=0) {
            OOL(i,max(-actual[ind].F,0), min(1'000'00-actual[ind].F,1'000'00)) {
                smax(dp2[i+actual[ind].F], dp2[i]+actual[ind].S);
            }
        }
        else {
            LOO(i,max(-actual[ind].F,0), min(1'000'00-actual[ind].F,1'000'00)) {
                smax(dp2[i+actual[ind].F], dp2[i]+actual[ind].S);
            }
        }
    }
    OOL(i,0,1'000'00-1) smax(dp[i],dp[i+1]);
    ll best=0;
    LOO(i,0,1'000'00) {
        smax(best,dp[i]+dp2[i]);
    }
    cout << best << '\n';
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
   // iO();
   int t = 1;
  //  cin >> t;
    while (t--) {
        solve();
        //cout << flush;
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

clo.cpp: In function 'void iO()':
clo.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen("haircut.out", "w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen("haircut.in", "r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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