oj.uz

Submission #481291

# Submission time Handle Problem Language Result Execution time Memory
481291 2021-10-20T09:21:45 Z BackNoob Cloud Computing (CEOI18_clo) C++14
100 / 100
 822 ms 2116 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define mask(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
using namespace std;
const int mxN = 4e3 + 227;
const ll inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

struct item{
	int cores , f , cost;
	bool operator<(const item &a) const {
		if(f == a.f) return cost < a.cost;
		return f > a.f;
	}
} a[mxN];

ll dp[200007];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("task.inp" , "r" , stdin);
    //freopen("task.out" , "w" , stdout);
    
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i++) {
    	int x , y , z;
    	cin >> x >> y >> z;
    	x = x;
    	z = -z;
    	a[i] = {x , y , z};
    }

    int m;
    cin >> m;
    for(int i = n + 1 ; i <= n + m ; i++) {
    	int x , y , z;
    	cin >> x >> y >> z;
    	x = -x;
    	a[i] = {x , y , z};
    }

    sort(a + 1 , a + 1 + n + m );

    memset(dp , -0x3f , sizeof(dp));
    dp[0] = 0;

    for(int i = 1 ; i <= n + m ; i++) {
    	if(a[i].cores >= 0) {
	    	for(int j = 200000 ; j >= 0 ; j--) {
	    		if(j - a[i].cores >= 0) {
	    			maximize(dp[j] , dp[j - a[i].cores] + a[i].cost);
	    		}
	    	}
	    }
	    else {
	    	for(int j = 0 ; j <= 200000 + a[i].cores ; j++) {
	    		maximize(dp[j] , dp[j - a[i].cores] + a[i].cost);
	    	}
	    }
    }


    ll res = 0;
    for(int i = 0 ; i <= 200000 ; i++) maximize(res , dp[i]);

    cout << res;
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 18 ms 1872 KB Output is correct
4 Correct 35 ms 1872 KB Output is correct
5 Correct 302 ms 1864 KB Output is correct
6 Correct 301 ms 1924 KB Output is correct
7 Correct 312 ms 1868 KB Output is correct
8 Correct 321 ms 1868 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Output is correct
2 Correct 3 ms 1868 KB Output is correct
3 Correct 26 ms 1864 KB Output is correct
4 Correct 19 ms 1888 KB Output is correct
5 Correct 179 ms 1892 KB Output is correct
6 Correct 153 ms 1888 KB Output is correct
7 Correct 345 ms 1868 KB Output is correct
8 Correct 336 ms 1868 KB Output is correct
9 Correct 366 ms 1912 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1868 KB Output is correct
2 Correct 6 ms 1868 KB Output is correct
3 Correct 32 ms 1868 KB Output is correct
4 Correct 34 ms 1868 KB Output is correct
5 Correct 65 ms 1880 KB Output is correct
6 Correct 63 ms 1880 KB Output is correct
7 Correct 93 ms 1868 KB Output is correct
8 Correct 85 ms 1868 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1868 KB Output is correct
2 Correct 4 ms 1868 KB Output is correct
3 Correct 255 ms 1860 KB Output is correct
4 Correct 315 ms 1904 KB Output is correct
5 Correct 620 ms 1984 KB Output is correct
6 Correct 773 ms 1956 KB Output is correct
7 Correct 717 ms 1952 KB Output is correct
8 Correct 740 ms 1952 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 27 ms 1868 KB Output is correct
3 Correct 156 ms 1880 KB Output is correct
4 Correct 369 ms 1916 KB Output is correct
5 Correct 822 ms 1968 KB Output is correct
6 Correct 735 ms 1936 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 18 ms 1872 KB Output is correct
4 Correct 35 ms 1872 KB Output is correct
5 Correct 302 ms 1864 KB Output is correct
6 Correct 301 ms 1924 KB Output is correct
7 Correct 312 ms 1868 KB Output is correct
8 Correct 321 ms 1868 KB Output is correct
9 Correct 2 ms 1880 KB Output is correct
10 Correct 3 ms 1868 KB Output is correct
11 Correct 26 ms 1864 KB Output is correct
12 Correct 19 ms 1888 KB Output is correct
13 Correct 179 ms 1892 KB Output is correct
14 Correct 153 ms 1888 KB Output is correct
15 Correct 345 ms 1868 KB Output is correct
16 Correct 336 ms 1868 KB Output is correct
17 Correct 366 ms 1912 KB Output is correct
18 Correct 6 ms 1868 KB Output is correct
19 Correct 6 ms 1868 KB Output is correct
20 Correct 32 ms 1868 KB Output is correct
21 Correct 34 ms 1868 KB Output is correct
22 Correct 65 ms 1880 KB Output is correct
23 Correct 63 ms 1880 KB Output is correct
24 Correct 93 ms 1868 KB Output is correct
25 Correct 85 ms 1868 KB Output is correct
26 Correct 5 ms 1868 KB Output is correct
27 Correct 4 ms 1868 KB Output is correct
28 Correct 255 ms 1860 KB Output is correct
29 Correct 315 ms 1904 KB Output is correct
30 Correct 620 ms 1984 KB Output is correct
31 Correct 773 ms 1956 KB Output is correct
32 Correct 717 ms 1952 KB Output is correct
33 Correct 740 ms 1952 KB Output is correct
34 Correct 3 ms 1868 KB Output is correct
35 Correct 27 ms 1868 KB Output is correct
36 Correct 156 ms 1880 KB Output is correct
37 Correct 369 ms 1916 KB Output is correct
38 Correct 822 ms 1968 KB Output is correct
39 Correct 735 ms 1936 KB Output is correct
40 Correct 177 ms 1884 KB Output is correct
41 Correct 333 ms 1912 KB Output is correct
42 Correct 510 ms 1936 KB Output is correct
43 Correct 710 ms 1960 KB Output is correct
44 Correct 693 ms 1988 KB Output is correct
45 Correct 769 ms 2116 KB Output is correct
46 Correct 331 ms 1988 KB Output is correct
47 Correct 520 ms 1868 KB Output is correct
48 Correct 539 ms 1992 KB Output is correct