이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
const int MAX = 2010;
int n, m;
vi cpu[MAX]; /// computers: {cores, rate, price}
vi work[MAX]; /// works: {cores, rate, price}
int dp[MAX][MAX];
int res;
bool cmp_by_rate(vi a, vi b){
return (a[1] > b[1]);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
FOR(i, 0, n-1, 1){
int c, r, p;
cin>>c>>r>>p;
cpu[i] = {c, r, p};
}
sort(cpu, cpu+n, cmp_by_rate);
cin>>m;
FOR(i, 0, m-1, 1){
int c, r, p;
cin>>c>>r>>p;
work[i] = {c, r, p};
}
sort(work, work+m, cmp_by_rate);
dp[0][0] = (cpu[0][1] >= work[0][1]) ? max((int)0, work[0][2] - cpu[0][2]) : 0;
FOR(i, 1, n-1, 1){
dp[i][0] = max( dp[i-1][0], ((cpu[i][1] >= work[0][1]) ? max((int)0, work[0][2] - cpu[i][2]) : 0) );
}
FOR(j, 1, m-1, 1){
dp[0][j] = max( dp[0][j-1], ((cpu[0][1] >= work[j][1]) ? max((int)0, work[j][2] - cpu[0][2]) : 0) );
}
FOR(i, 1, n-1, 1){
FOR(j, 1, m-1, 1){
dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
if(cpu[i][1] >= work[j][1]){
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + work[j][2] - cpu[i][2]);
}
}
}
cout<<dp[n-1][m-1]<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |