Submission #897838

#	Time	Username	Problem	Language	Result	Execution time	Memory
897838		alexdd	Cloud Computing (CEOI18_clo)	C++17	100 / 100	375 ms	2644 KiB

clo

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
struct event
{
    int tip;///1 - calculator
            ///2 - oferta
    int c;
    int f;
    int v;
};
bool cmp(event x, event y)
{
    if(x.f > y.f)
        return 1;
    if(x.f < y.f)
        return 0;
    if(x.tip==1 && y.tip==2)
        return 1;
    if(x.tip==2 && y.tip==1)
        return 0;
    return 0;
}
int n,m;
int dp[100005];
int newdp[100005];
vector<event> events;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    event aux;
    for(int i=0;i<n;i++)
    {
        cin>>aux.c>>aux.f>>aux.v;
        aux.tip = 1;
        events.push_back(aux);
    }
    cin>>m;
    for(int i=0;i<m;i++)
    {
        cin>>aux.c>>aux.f>>aux.v;
        aux.tip = 2;
        events.push_back(aux);
    }
    sort(events.begin(),events.end(),cmp);
    int maxc=0;
    for(auto e:events)
    {
        if(e.tip==2)
        {
            for(int j=0;j<=maxc;j++)
            {
                newdp[j] = dp[j];
                if(j+e.c <= maxc) newdp[j] = max(newdp[j], dp[j+e.c] + e.v);
            }
        }
        else
        {
            for(int j=maxc+1;j<=maxc+e.c;j++)
                dp[j] = -INF;
            maxc += e.c;
            for(int j=0;j<=maxc;j++)
            {
                newdp[j] = dp[j];
                if(j>=e.c) newdp[j] = max(newdp[j], dp[j-e.c] - e.v);
            }
        }
        for(int j=0;j<=maxc;j++)
            dp[j] = newdp[j];
    }
    int mxm=0;
    for(int i=0;i<=maxc;i++)
        mxm = max(mxm, dp[i]);
    cout<<mxm;
    return 0;
}
/**
sortam ofertele si calculatoarele descrescator dupa f (daca un calculator si o oferta au acelasi f, calculatorul o sa fie primu in ordine)
dp[i][j] = profitul maxim daca din calculatoarele & ofertele cu pozitia in ordine <= i am ales unele a.i. sa avem j core-uri cumparate dar nefolosite

newdp[j] max= dp[j]

daca pe pozitia i avem o oferta:
newdp[j] max= dp[j+c] + v


daca pe pozitia i avem un calculator:
newdp[j] max= dp[j-c] - v


*/

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