제출 #1050547

#제출 시각아이디문제언어결과실행 시간메모리
1050547nghiaaaCloud Computing (CEOI18_clo)C++17
0 / 100
1 ms8540 KiB
#include <bits/stdc++.h> using namespace std; #define ld long double #define ll long long #define db double #define ii pair<int,int> #define f first #define s second #define mp make_pair #define mt make_tuple #define pb push_back #define all(v) v.begin(),v.end() #define BIT(i) ((ll)1<<(i)) #define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl #define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++) #define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--) #define sz(a) (int)a.size() #define len(a) (int)a.length() const int mod = 998244353; inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;} //auto seed = chrono::high_resolution_clock::now().time_since_epoch().count(); //mt19937 RAND(seed); inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;} inline int mul(int u,int v){return (ll)u*v%mod;} const int N = 2000; const int UP = 10; struct item{ int cores, cl_rate, price; item(){} bool operator < (item &u) const { return cl_rate < u.cl_rate; } }; item shop[N + 1], order[N + 1]; int n, m; bool ready[N + 1][N + 1][21][2]; ll dp[N + 1][N + 1][21][2]; const ll inf = 1e15; ll f(int i, int j, int cores, bool done) { if (i == n + 1) { if (cores <= 0) return 0; else return -inf; } if (j == m + 1) return 0; if (ready[i][j][cores + UP][done]) return dp[i][j][cores + UP][done]; ready[i][j][cores + UP][done] = 1; if (shop[i].cl_rate < order[j].cl_rate) return dp[i][j][cores + UP][done] = f(i + 1, j, 0, done); if (cores > 0) { ll pre1 = -shop[i].price + f(i + 1, j, cores - shop[i].cores, done); ll pre2 = f(i + 1, j, cores, done); return dp[i][j][cores + UP][done] = max({inf, pre1, pre2}); } else{ int nxtcores = cores; if (shop[i - 1].cl_rate < order[j + 1].cl_rate) nxtcores = 0; if (!done){ ll pre1 = f(i, j, order[j].cores + cores, 1) + order[j].price; ll pre2 = f(i, j + 1, nxtcores, 0); return dp[i][j][cores + UP][done] = max({inf, pre1, pre2}); } else{ return dp[i][j][cores + UP][done] = f(i, j + 1, nxtcores, 0); } } } void solve() { cin >> n; forw(i, 1, n) cin >> shop[i].cores >> shop[i].cl_rate >> shop[i].price; sort(shop + 1, shop + n + 1); cin >> m; forw(i, 1, m) cin >> order[i].cores >> order[i].cl_rate >> order[i].price; sort(order + 1, order + m + 1); cout << f(1, 1, 0, 0); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); // freopen("test.inp","r",stdin); // freopen("test.out","w",stdout); //time_t TIME_TU=clock(); int t=1; // cin>>t; while(t--) solve(); //time_t TIME_TV=clock(); //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...