oj.uz

Submission #775853

# Submission time Handle Problem Language Result Execution time Memory
775853 2023-07-07T05:17:34 Z Dzadzo Cloud Computing (CEOI18_clo) C++14
0 / 100
 91 ms 262144 KB 
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vector<int>>
#define INF LLONG_MAX
#define MOD 1000000009
#define MAXN 2000
#define MAXM 2000
using namespace std;
int c[MAXN+MAXM+1],f[MAXN+MAXM+1],v[MAXN+MAXM+1];
bool comp(int a,int b){
	if (f[a]>f[b])return true;
	if (f[a]<f[b])return false;
	return v[a]<v[b];
}
main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
//	freopen("problemname.in", "r", stdin);
//	freopen("problemname.out", "w", stdout);
	int n;
	cin>>n;
	
	for (int i=1;i<=n;i++){
		int q1,q2,q3;
		cin>>q1>>q2>>q3;
		c[i]=q1;
		f[i]=q2;
		v[i]=-q3;
	}
	int m;
	cin>>m;
	for (int i=n+1;i<=n+m;i++){
		int q1,q2,q3;
		cin>>q1>>q2>>q3;
		c[i]=-q1;
		f[i]=q2;
		v[i]=q3;		
	}
	int ind[n+m+1];
	for (int i=1;i<=n+m;i++)ind[i]=i;
	sort(ind+1,ind+n+m+1,comp);
	vvi dp(n+m+1,vi (MAXN*50+1,-INF));
	dp[0][0]=0;
	
	for (int i=1;i<=n+m;i++){
		for (int k=0;k<=MAXN*50;k++){
			dp[i][k]=max(dp[i][k],dp[i-1][k]);
			if (k-c[ind[i]]>=0 && k-c[ind[i]]<=MAXN*50){
				if (dp[i-1][k-c[ind[i]]]!=-INF){
					dp[i][k]=max(dp[i][k],dp[i-1][k-c[ind[i]]]+v[ind[i]]);
				}
			}	
		}
	}
//	for (int i=1;i<=n+m;i++)cout<<c[ind[i]]<<" "<<f[ind[i]]<<" "<<v[ind[i]]<<"\n";
	int ans=0;
	for (int i=0;i<=MAXN*50;i++)ans=max(ans,dp[n+m][i]);
/*	for (int i=1;i<=n+m;i++){
		cout<<"---"<<i<<"---\n";
		for (int k=0;k<=MAXN*50;k++){
			if (dp[i][k]!=-INF)
			cout<<k<<" "<<dp[i][k]<<"\n";
		}
		cout<<"\n";
	}
	*/
	cout<<ans;
}

Compilation message

clo.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 50 ms 86732 KB Output is correct
4 Correct 90 ms 164432 KB Output is correct
5 Runtime error 90 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 42 ms 85076 KB Output is correct
4 Correct 55 ms 85152 KB Output is correct
5 Runtime error 87 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25360 KB Output is correct
2 Correct 13 ms 25420 KB Output is correct
3 Correct 68 ms 142428 KB Output is correct
4 Correct 78 ms 142432 KB Output is correct
5 Runtime error 91 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 11 ms 14420 KB Output is correct
3 Runtime error 89 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6596 KB Output is correct
2 Correct 63 ms 126684 KB Output is correct
3 Runtime error 81 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 50 ms 86732 KB Output is correct
4 Correct 90 ms 164432 KB Output is correct
5 Runtime error 90 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -