# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
431008 | 2021-06-17T08:52:12 Z | Runtime_error_ | Cloud Computing (CEOI18_clo) | C++14 | 818 ms | 2060 KB |
#include <bits/stdc++.h> #define ll long long using namespace std; const ll N = 2009,C = 55,MX = 1e18+9; ll n,m,SumCores,ans; ll dp[2][N*C]; struct item{ ll type;//1 costumer 2 computer ll clock;//sort decreasingly and forget about it ll cores;//the knapsack size, + for computers, - for costumers, keep this >=0 ll price;// - for computers, + for costumers: maximize this bool operator<(const item &other)const { if(clock == other.clock) return type > other.type; return clock > other.clock; } }a[N<<1]; signed main(){ scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i].cores,&a[i].clock,&a[i].price), a[i].type = 2, a[i].price*=-1, SumCores += a[i].cores; scanf("%d",&m); for(ll i=n+1;i<=n+m;i++) scanf("%d%d%d",&a[i].cores,&a[i].clock,&a[i].price), a[i].type = 1, a[i].cores *= -1; sort(a+1,a+1+n+m); bool is = 0; for(ll j=1;j<=SumCores;j++) dp[is][j] = -MX; for(ll i=1;i<=n+m;i++){ is = !is; for(ll j=0;j<=SumCores;j++){ dp[is][j] = dp[!is][j]; if(j - a[i].cores >= 0 && j-a[i].cores <= SumCores) dp[is][j] = max(dp[is][j],dp[!is][j-a[i].cores] + a[i].price); //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; ans = max(ans,dp[is][j]); } } printf("%lld\n",ans); } /* 2 4 2200 700 4 2000 750 2 1 1500 300 6 1900 1500 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 2 ms | 332 KB | Output is correct |
6 | Correct | 2 ms | 332 KB | Output is correct |
7 | Correct | 4 ms | 332 KB | Output is correct |
8 | Correct | 4 ms | 332 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 260 KB | Output is correct |
3 | Correct | 1 ms | 256 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 59 ms | 676 KB | Output is correct |
6 | Correct | 4 ms | 332 KB | Output is correct |
7 | Correct | 199 ms | 1152 KB | Output is correct |
8 | Correct | 62 ms | 500 KB | Output is correct |
9 | Correct | 351 ms | 1716 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 14 ms | 428 KB | Output is correct |
4 | Correct | 3 ms | 384 KB | Output is correct |
5 | Correct | 419 ms | 1196 KB | Output is correct |
6 | Correct | 762 ms | 1868 KB | Output is correct |
7 | Correct | 789 ms | 1868 KB | Output is correct |
8 | Correct | 696 ms | 1812 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 2 ms | 460 KB | Output is correct |
3 | Correct | 47 ms | 768 KB | Output is correct |
4 | Correct | 12 ms | 400 KB | Output is correct |
5 | Correct | 741 ms | 1788 KB | Output is correct |
6 | Correct | 790 ms | 1808 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 2 ms | 332 KB | Output is correct |
6 | Correct | 2 ms | 332 KB | Output is correct |
7 | Correct | 4 ms | 332 KB | Output is correct |
8 | Correct | 4 ms | 332 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 260 KB | Output is correct |
11 | Correct | 1 ms | 256 KB | Output is correct |
12 | Correct | 1 ms | 256 KB | Output is correct |
13 | Correct | 59 ms | 676 KB | Output is correct |
14 | Correct | 4 ms | 332 KB | Output is correct |
15 | Correct | 199 ms | 1152 KB | Output is correct |
16 | Correct | 62 ms | 500 KB | Output is correct |
17 | Correct | 351 ms | 1716 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
20 | Correct | 1 ms | 204 KB | Output is correct |
21 | Correct | 1 ms | 204 KB | Output is correct |
22 | Correct | 1 ms | 204 KB | Output is correct |
23 | Correct | 1 ms | 332 KB | Output is correct |
24 | Correct | 1 ms | 332 KB | Output is correct |
25 | Correct | 1 ms | 332 KB | Output is correct |
26 | Correct | 1 ms | 256 KB | Output is correct |
27 | Correct | 1 ms | 204 KB | Output is correct |
28 | Correct | 14 ms | 428 KB | Output is correct |
29 | Correct | 3 ms | 384 KB | Output is correct |
30 | Correct | 419 ms | 1196 KB | Output is correct |
31 | Correct | 762 ms | 1868 KB | Output is correct |
32 | Correct | 789 ms | 1868 KB | Output is correct |
33 | Correct | 696 ms | 1812 KB | Output is correct |
34 | Correct | 1 ms | 204 KB | Output is correct |
35 | Correct | 2 ms | 460 KB | Output is correct |
36 | Correct | 47 ms | 768 KB | Output is correct |
37 | Correct | 12 ms | 400 KB | Output is correct |
38 | Correct | 741 ms | 1788 KB | Output is correct |
39 | Correct | 790 ms | 1808 KB | Output is correct |
40 | Correct | 57 ms | 692 KB | Output is correct |
41 | Correct | 134 ms | 844 KB | Output is correct |
42 | Correct | 24 ms | 460 KB | Output is correct |
43 | Correct | 797 ms | 2016 KB | Output is correct |
44 | Correct | 818 ms | 2024 KB | Output is correct |
45 | Correct | 816 ms | 2060 KB | Output is correct |
46 | Correct | 6 ms | 384 KB | Output is correct |
47 | Correct | 13 ms | 440 KB | Output is correct |
48 | Correct | 19 ms | 512 KB | Output is correct |