제출 #988996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
988996		parlimoos	Cloud Computing (CEOI18_clo)	C++14	0 / 100	84 ms	157012 KiB

clo

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define arr(x) array<ll , x>
#define endl '\n'
#define cl clear
#define bg begin

int n , m , sum;
vector<arr(3)> a , b , ord;
ll dp[2000][10000] , o , ps[10000];

ll getPs(int l , int r){
    ll res = ps[r];
    if(l > 0) res -= ps[l - 1];
    return res;
}
ll f(int i , int j){
    ll res = 0;
    if(dp[i][j] != -1) return dp[i][j];
    if(i >= m or j >= sum) return 0;
    res = max(f(i + 1 , j) , f(i , ord[j][2]));
    if(j + a[i][0] <= sum and ord[j][0] >= a[i][1]){
        res = max(res , a[i][2] - getPs(j , j + a[i][0] - 1) + f(i + 1 , j + a[i][0]));
    }
    return (dp[i][j] = res);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0 ; i < n ; i++){
        int c , f , v;
        cin >> c >> f >> v;
        a.pb({c , f , v}) , b.pb({c , f , v}) , sum += c;
    }
    cin >> m;
    for(int i = 0 ; i < m ; i++){
        int c , f , v;
        cin >> c >> f >> v;
        a.pb({c , f , v});
    }
    fill(&dp[0][0] , &dp[1999][10000] , -1);
    sort(a.bg() , a.end() , [](arr(3) a , arr(3) b){
        return (a[1] < b[1]);
    });
    sort(b.bg() , b.end() , [](arr(3) a , arr(3) b){
        return (a[1] < b[1]);
    });
    for(auto el : b){
        int inx = (int)ord.size() + el[0];
        ord.pb({el[1] , el[2] , inx});
        for(int i = 0 ; i < el[0] - 1 ; i++) ord.pb({el[1] , 0 , inx});
    }
    for(int i = 0 ; i < sum ; i++){
        ps[i] = ord[i][1];
        if(i > 0) ps[i] += ps[i - 1];
    }
    cout << f(0 , 0) + o;
}

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