Submission #1033263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033263		nmts	Cloud Computing (CEOI18_clo)	C++17	90 / 100	1265 ms	9296 KiB

clo

#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout);
#define faster    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define fi first
#define se second
#define mii map< int , int>
#define reset(a,val) memset(a ,val , sizeof(a) )
#define count_bit(i) __builtin_popcountll(i) 
#define mask(i) ((1LL << (i)))  
#define status(x, i) (((x) >> (i)) & 1)  
#define set_on(x, i) ((x) | mask(i)) 
#define set_off(x, i) ((x) & ~mask(i))
#define endl '\n'    
#define ll long long
#define int ll
const int maxn1 = 4e3 + 6;
const int maxn2 = 1e6 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;


template <class T> inline T sqr(T x) { return x * x; };

template <class T> inline int Power(T x, int y) 

{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }

template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

inline int gcd(int x, int y) 
{ return y ? gcd(y , x % y) : x;}

inline int lcm(int x, int y) { return x * y / gcd(x, y); }

using namespace std;

struct dl{
    bool type ; int c , f , v;
} a[maxn1];

int n , q;

ll dp[maxn2];
ll new_dp[maxn2];

void solve()
{

    cin >> n;

    for (int i = 1 ; i <= n ; ++i)
        {
            cin >> a[i].c >> a[i].f >> a[i].v;
            a[i].type = 0;
        }
    
    cin >> q;

    for (int i = 1 ; i <= q ; ++i)  
        {
            cin >> a[i + n].c >> a[i + n].f >> a[i + n].v;
            a[i + n].type = 1;
        }

    sort(a + 1 , a + n + q + 1 , [&](dl x , dl y)
        {
            if  (x.f != y.f) return x.f < y.f;
            return x.type > y.type;
        }
    );


    for (int i = 1 ; i <= n + q ; ++i)
        {

            memset(new_dp , -0x3f , sizeof new_dp);

            for (int j = 0 ; j <= 50 * q - a[i].c  ; ++j)
                    {   
                        maximize(new_dp[j], dp[j]);

                        if (a[i].type == 1)
                            {
                                new_dp[j + a[i].c] = max(new_dp[j + a[i].c] , dp[j] + a[i].v);
                            }
                        else 
                        if (j != 0)
                            {
                                new_dp[max(0ll , j - a[i].c)] = max(new_dp[max(0ll , j - a[i].c)] , dp[j] - a[i].v);
                            }
                    }

            for (int j = 0 ; j <= 50 * q ; ++j)
                dp[j] = new_dp[j];
        }
    
    cout << dp[0] << endl;
}


int32_t main()
{
    faster;
    // file("txt");
    // int t ; cin >> t ; while (t--)
    solve();
    return 0;
} 

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