제출 #1108270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108270		koukirocks	Cloud Computing (CEOI18_clo)	C++17	100 / 100	595 ms	2960 KiB

clo

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

int main() {
    speed;
    ll n,m;
    cin>>n;
    vector<pair<pll,ll>> a;
    for (int i=1;i<=n;i++) {
        ll c,f,v;
        cin>>c>>f>>v;
        a.emplace_back(pair(c,f),-v);
    }
    cin>>m;
    for (int i=1;i<=m;i++) {
        ll c,f,v;
        cin>>c>>f>>v;
        a.emplace_back(pair(-c,f),v);
    }
    sort(all(a),[&](pair<pll,ll> a,pair<pll,ll> b) {
        if (a.F.S==b.F.S) return (a.S<0)>(b.S<0);
        return a.F.S>b.F.S;
    });
    // for (int i=0;i<n+m;i++) {
    //     cout<<a[i].F.F<<" "<<a[i].F.S<<" "<<a[i].S<<"\n";
    // }
    // cout<<"a\n";
    vvector<ll> dp(2,vector<ll>(n*50+1,-oo));
    dp[1][0]=0;
    for (int i=0;i<n+m;i++) {
        ll id=i&1,ni=id^1;
        for (int j=0;j<=n*50;j++) {
            dp[id][j]=dp[ni][j];
            ll nj = j-a[i].F.F;
            if (nj>=0 and nj<=n*50) dp[id][j]=max(dp[id][j],dp[ni][nj]+a[i].S);
            // if (nj==0) cout<<j<<" "<<nj<<" "<<a[i].S<<" j nj a.S\n";
        }
        // for (int j=0;j<=n*50;j++) {
        //     if (dp[id][j]<-100000000) cout<<"-oo ";
        //     else cout<<dp[id][j]<<" ";
        // }
        // cout<<"\n";
    }
    cout<<*max_element(all(dp[(n+m-1)&1]))<<"\n";
    return 0;
}

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