oj.uz

Submission #966235

# Submission time Handle Problem Language Result Execution time Memory
966235 2024-04-19T14:47:32 Z shadow_sami Cloud Computing (CEOI18_clo) C++17
100 / 100
 1823 ms 8784 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;

typedef struct PRO{
	ll c,f,v;
	void init(ll a,ll b,ll d){
		c = a;
		f = b;
		v = d;
	}
	void deb(){
		cerr<<c<<" "<<f<<" "<<v<<nli;
		return;
	}
}pro;

pro p;
vector<pro> a;
ll dp[2][mx];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n;
        res = 0;
        fip(0,n){
        	cin>>tp>>tp2>>tptp;        	
        	res += tp;
        	tptp = (-tptp);
        	p.init(tp,tp2,tptp);
        	a.push_back(p);
        }
        cin>>m;
        ans = 0;
        fip(0,m){
        	cin>>tp>>tp2>>tptp;
        	tp = (-tp);
        	p.init(tp,tp2,tptp);
        	a.push_back(p);
        }
        sort(a.begin(),a.end(),[](const pro aa,const pro bb){
        	if(aa.f == bb.f)
        		return aa.v < bb.v;
        	return aa.f > bb.f;
        });
        fip(1,res+1)
        	dp[0][i] = -1e18;
        ans = -1e18;
        dp[0][0] = 0;
        // fx(a){
        // 	x.deb();
        // }  
        // debug(res)      	;
        fx(a){
        	fjp(0,res+1)
        		dp[1][j] = dp[0][j];
        	fjp(0,res+1){
        		tp = j + x.c;
        		if(tp>=0 && tp<=res)
        			dp[1][tp] = max(dp[1][tp],dp[0][j] + x.v);
        	}
        	swap(dp[0],dp[1]);
        	// fjp(0,res+1)
        	// 	cerr<<dp[0][j]<<" ";
        	// cerr<<nli;
        }
        fjp(0,res+1)
        	ans = max(dp[0][j],ans);
        cout<<ans<<nli;
        
    cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 4 ms 8096 KB Output is correct
3 Correct 39 ms 8028 KB Output is correct
4 Correct 70 ms 8284 KB Output is correct
5 Correct 638 ms 8284 KB Output is correct
6 Correct 651 ms 8364 KB Output is correct
7 Correct 685 ms 8352 KB Output is correct
8 Correct 702 ms 8360 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8280 KB Output is correct
2 Correct 6 ms 8280 KB Output is correct
3 Correct 38 ms 8292 KB Output is correct
4 Correct 38 ms 8280 KB Output is correct
5 Correct 341 ms 8532 KB Output is correct
6 Correct 302 ms 8312 KB Output is correct
7 Correct 792 ms 8364 KB Output is correct
8 Correct 745 ms 8360 KB Output is correct
9 Correct 889 ms 8356 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8280 KB Output is correct
2 Correct 15 ms 8284 KB Output is correct
3 Correct 74 ms 8284 KB Output is correct
4 Correct 74 ms 8096 KB Output is correct
5 Correct 128 ms 8288 KB Output is correct
6 Correct 128 ms 8088 KB Output is correct
7 Correct 181 ms 8284 KB Output is correct
8 Correct 166 ms 8284 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8280 KB Output is correct
2 Correct 8 ms 8028 KB Output is correct
3 Correct 540 ms 8284 KB Output is correct
4 Correct 627 ms 8356 KB Output is correct
5 Correct 1519 ms 8500 KB Output is correct
6 Correct 1743 ms 8532 KB Output is correct
7 Correct 1753 ms 8500 KB Output is correct
8 Correct 1705 ms 8492 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8280 KB Output is correct
2 Correct 56 ms 8284 KB Output is correct
3 Correct 301 ms 8308 KB Output is correct
4 Correct 669 ms 8356 KB Output is correct
5 Correct 1716 ms 8452 KB Output is correct
6 Correct 1789 ms 8284 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 4 ms 8096 KB Output is correct
3 Correct 39 ms 8028 KB Output is correct
4 Correct 70 ms 8284 KB Output is correct
5 Correct 638 ms 8284 KB Output is correct
6 Correct 651 ms 8364 KB Output is correct
7 Correct 685 ms 8352 KB Output is correct
8 Correct 702 ms 8360 KB Output is correct
9 Correct 4 ms 8280 KB Output is correct
10 Correct 6 ms 8280 KB Output is correct
11 Correct 38 ms 8292 KB Output is correct
12 Correct 38 ms 8280 KB Output is correct
13 Correct 341 ms 8532 KB Output is correct
14 Correct 302 ms 8312 KB Output is correct
15 Correct 792 ms 8364 KB Output is correct
16 Correct 745 ms 8360 KB Output is correct
17 Correct 889 ms 8356 KB Output is correct
18 Correct 16 ms 8280 KB Output is correct
19 Correct 15 ms 8284 KB Output is correct
20 Correct 74 ms 8284 KB Output is correct
21 Correct 74 ms 8096 KB Output is correct
22 Correct 128 ms 8288 KB Output is correct
23 Correct 128 ms 8088 KB Output is correct
24 Correct 181 ms 8284 KB Output is correct
25 Correct 166 ms 8284 KB Output is correct
26 Correct 10 ms 8280 KB Output is correct
27 Correct 8 ms 8028 KB Output is correct
28 Correct 540 ms 8284 KB Output is correct
29 Correct 627 ms 8356 KB Output is correct
30 Correct 1519 ms 8500 KB Output is correct
31 Correct 1743 ms 8532 KB Output is correct
32 Correct 1753 ms 8500 KB Output is correct
33 Correct 1705 ms 8492 KB Output is correct
34 Correct 5 ms 8280 KB Output is correct
35 Correct 56 ms 8284 KB Output is correct
36 Correct 301 ms 8308 KB Output is correct
37 Correct 669 ms 8356 KB Output is correct
38 Correct 1716 ms 8452 KB Output is correct
39 Correct 1789 ms 8284 KB Output is correct
40 Correct 381 ms 8320 KB Output is correct
41 Correct 719 ms 8532 KB Output is correct
42 Correct 1006 ms 8528 KB Output is correct
43 Correct 1807 ms 8508 KB Output is correct
44 Correct 1823 ms 8512 KB Output is correct
45 Correct 1820 ms 8784 KB Output is correct
46 Correct 656 ms 8284 KB Output is correct
47 Correct 979 ms 8484 KB Output is correct
48 Correct 970 ms 8528 KB Output is correct