oj.uz

답안 #563194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563194 2022-05-16T13:21:05 Z zaneyu Cloud Computing (CEOI18_clo) C++14
100 / 100
 301 ms 1356 KB 
/*input
4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
#define ll long long 
#define ld long double
#define pii pair<int,int>
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define MP make_pair
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
// big mod 3006703054056749LL;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
ll mult(ll a,ll b){
    return (a*b)%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    a%=MOD;
    ll res=1LL;
    while(b){
        if(b&1){
            res=(res*a)%MOD;
        }
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
const int maxn=1e5+5;
const int maxlg=__lg(maxn)+2;
ll dp[maxn];
int main(){
    int n;
    cin>>n;
    vector<pair<int,pii>> v;
    REP(i,n){
        int a,b,c;
        cin>>a>>b>>c;
        v.pb({b,{a,-c}});
    }
    int m;
    cin>>m;
    REP(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        v.pb({b,{-a,c}});
    }
    sort(ALL(v)),reverse(ALL(v));
    REP1(j,maxn-1) dp[j]=-INF64;
    for(auto x:v){
        if(x.s.f>0){
            for(int i=maxn-x.s.f-1;i>=0;i--){
                MXTO(dp[i+x.s.f],dp[i]+x.s.s);
            }
        }   
        else{
            for(int i=-x.s.f;i<maxn;i++){
                MXTO(dp[i+x.s.f],dp[i]+x.s.s);
            }
        }
    }
    cout<<*max_element(dp,dp+maxn);
}

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1084 KB Output is correct
3 Correct 9 ms 1096 KB Output is correct
4 Correct 17 ms 980 KB Output is correct
5 Correct 145 ms 1152 KB Output is correct
6 Correct 136 ms 1168 KB Output is correct
7 Correct 150 ms 1164 KB Output is correct
8 Correct 151 ms 1096 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 8 ms 1084 KB Output is correct
4 Correct 9 ms 1100 KB Output is correct
5 Correct 65 ms 1108 KB Output is correct
6 Correct 64 ms 1120 KB Output is correct
7 Correct 150 ms 1168 KB Output is correct
8 Correct 152 ms 1156 KB Output is correct
9 Correct 138 ms 1228 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 14 ms 1084 KB Output is correct
4 Correct 14 ms 980 KB Output is correct
5 Correct 27 ms 1092 KB Output is correct
6 Correct 26 ms 980 KB Output is correct
7 Correct 36 ms 1084 KB Output is correct
8 Correct 36 ms 1108 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1080 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 109 ms 1124 KB Output is correct
4 Correct 136 ms 1100 KB Output is correct
5 Correct 277 ms 1236 KB Output is correct
6 Correct 275 ms 1108 KB Output is correct
7 Correct 275 ms 1216 KB Output is correct
8 Correct 284 ms 1228 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 13 ms 1096 KB Output is correct
3 Correct 60 ms 1108 KB Output is correct
4 Correct 140 ms 1108 KB Output is correct
5 Correct 301 ms 1236 KB Output is correct
6 Correct 286 ms 1108 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1084 KB Output is correct
3 Correct 9 ms 1096 KB Output is correct
4 Correct 17 ms 980 KB Output is correct
5 Correct 145 ms 1152 KB Output is correct
6 Correct 136 ms 1168 KB Output is correct
7 Correct 150 ms 1164 KB Output is correct
8 Correct 151 ms 1096 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 8 ms 1084 KB Output is correct
12 Correct 9 ms 1100 KB Output is correct
13 Correct 65 ms 1108 KB Output is correct
14 Correct 64 ms 1120 KB Output is correct
15 Correct 150 ms 1168 KB Output is correct
16 Correct 152 ms 1156 KB Output is correct
17 Correct 138 ms 1228 KB Output is correct
18 Correct 3 ms 980 KB Output is correct
19 Correct 3 ms 980 KB Output is correct
20 Correct 14 ms 1084 KB Output is correct
21 Correct 14 ms 980 KB Output is correct
22 Correct 27 ms 1092 KB Output is correct
23 Correct 26 ms 980 KB Output is correct
24 Correct 36 ms 1084 KB Output is correct
25 Correct 36 ms 1108 KB Output is correct
26 Correct 3 ms 1080 KB Output is correct
27 Correct 2 ms 980 KB Output is correct
28 Correct 109 ms 1124 KB Output is correct
29 Correct 136 ms 1100 KB Output is correct
30 Correct 277 ms 1236 KB Output is correct
31 Correct 275 ms 1108 KB Output is correct
32 Correct 275 ms 1216 KB Output is correct
33 Correct 284 ms 1228 KB Output is correct
34 Correct 1 ms 980 KB Output is correct
35 Correct 13 ms 1096 KB Output is correct
36 Correct 60 ms 1108 KB Output is correct
37 Correct 140 ms 1108 KB Output is correct
38 Correct 301 ms 1236 KB Output is correct
39 Correct 286 ms 1108 KB Output is correct
40 Correct 78 ms 1108 KB Output is correct
41 Correct 147 ms 1140 KB Output is correct
42 Correct 207 ms 1196 KB Output is correct
43 Correct 278 ms 1108 KB Output is correct
44 Correct 286 ms 1236 KB Output is correct
45 Correct 281 ms 1356 KB Output is correct
46 Correct 141 ms 1092 KB Output is correct
47 Correct 220 ms 1204 KB Output is correct
48 Correct 209 ms 1232 KB Output is correct