oj.uz

답안 #864851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
864851 2023-10-23T17:00:22 Z dead0ne Cloud Computing (CEOI18_clo) C++17
36 / 100
 206 ms 262144 KB 
#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define int long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1000000009
#define MOD 1000000007
#define lim 200005
using namespace std;



int n,m;
vector<tuple<int, int, int>> vec;   // frequence, core, value
int dp[4001][10001];

int calc(int cur, int cor){
    if(cur>=n+m) return 0;
    if(dp[cur][cor]!=-1) return dp[cur][cor];

    if(cor >= (n+m-cur)*50){
        if(get<1>(vec[cur]) > 0){
            return dp[cur][cor] = calc(cur+1, cor);
        }
        else{
            return dp[cur][cor] = calc(cur+1, cor + get<1>(vec[cur])) + get<2>(vec[cur]);
        }
    }

    dp[cur][cor] = calc(cur+1, cor);
    if(cor + get<1>(vec[cur]) >= 0) dp[cur][cor] = max(dp[cur][cor], calc(cur+1, cor + get<1>(vec[cur])) + get<2>(vec[cur]));

    return dp[cur][cor];    
}




void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        int c,f,v; cin >> c >> f >> v;
        vec.pb({f, c, -v});
    }
    cin >> m;
    for(int i=1; i<=m; i++){
        int c,f,v; cin >> c >> f >> v;
        vec.pb({f, -c, v});
    }

    for(int i=0; i<=n+m; i++) for(int j=0; j<=min(10000ll, (n+m)*50); j++) dp[i][j]=-1;
    
    sort(all(vec), greater<tuple<int, int, int>>());
    //for(auto i:vec) cerr << get<0>(i) spc get<1>(i) spc get<2>(i) << endl;

    cout << max(calc(0, 0), 0ll) << endl;
}


signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    #ifdef Local
    freopen("in","r",stdin);
    freopen("out","w",stdout);
    #endif

    int t=1;
    //cin >> t;
    while(t--) solve();
}

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 20 ms 152660 KB Output is correct
6 Correct 18 ms 152612 KB Output is correct
7 Correct 30 ms 158856 KB Output is correct
8 Correct 24 ms 158800 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 8660 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 71 ms 72536 KB Output is correct
6 Correct 12 ms 72540 KB Output is correct
7 Correct 159 ms 158852 KB Output is correct
8 Correct 88 ms 158848 KB Output is correct
9 Incorrect 206 ms 154964 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14804 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 7 ms 41564 KB Output is correct
8 Correct 7 ms 41560 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 63 ms 119640 KB Output is correct
4 Correct 23 ms 144216 KB Output is correct
5 Runtime error 32 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 83 ms 66356 KB Output is correct
4 Correct 77 ms 158828 KB Output is correct
5 Runtime error 35 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 20 ms 152660 KB Output is correct
6 Correct 18 ms 152612 KB Output is correct
7 Correct 30 ms 158856 KB Output is correct
8 Correct 24 ms 158800 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 8660 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 71 ms 72536 KB Output is correct
14 Correct 12 ms 72540 KB Output is correct
15 Correct 159 ms 158852 KB Output is correct
16 Correct 88 ms 158848 KB Output is correct
17 Incorrect 206 ms 154964 KB Output isn't correct
18 Halted 0 ms 0 KB -