oj.uz

Submission #518515

# Submission time Handle Problem Language Result Execution time Memory
518515 2022-01-24T02:38:54 Z LptN21 Cloud Computing (CEOI18_clo) C++14
100 / 100
 415 ms 1304 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define PI acos(-1.0)
#define eps 1e-9
#define FF first
#define SS second
// VECTOR (6)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define uniq(v) sort(all( (v) )), (v).resize( unique(all( (v) )) - (v).begin() );
// BIT (6)
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, int> ii;
/* CODE BELOW */
const int N = 2e3 + 7, M = 50 + 7;
const ll oo = 1e16 + 7;
const int MOD = 1e9 + 7;

int n, m, k, t;

struct Product{
    int c, f, v; Product() {}
    Product(int _c, int _f, int _v):
        c(_c), f(_f), v(_v) {}
    bool operator<(const Product &o) const {
        if(f != o.f) return f < o.f;
        if(c != o.c) return c < o.c;
        return o.v < o.v;
    }
} a[N], b[N];

ll _dp[N * M];

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d", &n);
    int c, f, v;
    for(int i=1;i<=n;i++) {
        scanf("%d%d%d", &c, &f, &v);
        a[i] = Product(c, f, v);
    }
    scanf("%d", &m);
    for(int i=1;i<=m;i++) {
        scanf("%d%d%d", &c, &f, &v);
        b[i] = Product(c, f, v);
    }
    sort(a+1, a+n+1), sort(b+1, b+m+1);
    for(int i=1;i<N*M;i++) _dp[i] = -oo;

    for(int j=n, i=m;i>0;i--) {
        for(;j>0&&a[j].f>=b[i].f;j--) {
            for(int k=N*M-1;k>=a[j].c;k--) {
                _dp[k] = max(_dp[k], _dp[k - a[j].c] - a[j].v);
            }
        }
        for(int k=0;k+b[i].c<N*M;k++) {
            _dp[k] = max(_dp[k], _dp[k + b[i].c] + b[i].v);
        }
    }

    ll ans = 0;
    for(int i=0;i<N*M;i++) ans = max(ans, _dp[i]);
    printf("%lld", ans);

    return 0;
}

Compilation message

clo.cpp: In member function 'bool Product::operator<(const Product&) const':
clo.cpp:41:20: warning: self-comparison always evaluates to false [-Wtautological-compare]
   41 |         return o.v < o.v;
      |                ~~~ ^ ~~~
clo.cpp: In function 'int main()':
clo.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
clo.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d%d%d", &c, &f, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
clo.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d", &m);
      |     ~~~~~^~~~~~~~~~
clo.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d%d%d", &c, &f, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 11 ms 1100 KB Output is correct
4 Correct 20 ms 1100 KB Output is correct
5 Correct 185 ms 1240 KB Output is correct
6 Correct 175 ms 1232 KB Output is correct
7 Correct 188 ms 1256 KB Output is correct
8 Correct 196 ms 1232 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1196 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct
3 Correct 11 ms 1100 KB Output is correct
4 Correct 11 ms 1192 KB Output is correct
5 Correct 84 ms 1200 KB Output is correct
6 Correct 96 ms 1204 KB Output is correct
7 Correct 163 ms 1228 KB Output is correct
8 Correct 216 ms 1228 KB Output is correct
9 Correct 185 ms 1208 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1192 KB Output is correct
2 Correct 4 ms 1100 KB Output is correct
3 Correct 13 ms 1196 KB Output is correct
4 Correct 13 ms 1228 KB Output is correct
5 Correct 35 ms 1180 KB Output is correct
6 Correct 35 ms 1192 KB Output is correct
7 Correct 49 ms 1204 KB Output is correct
8 Correct 47 ms 1100 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1100 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct
3 Correct 139 ms 1212 KB Output is correct
4 Correct 170 ms 1100 KB Output is correct
5 Correct 358 ms 1264 KB Output is correct
6 Correct 378 ms 1256 KB Output is correct
7 Correct 379 ms 1260 KB Output is correct
8 Correct 362 ms 1260 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 12 ms 1204 KB Output is correct
3 Correct 83 ms 1192 KB Output is correct
4 Correct 195 ms 1220 KB Output is correct
5 Correct 402 ms 1268 KB Output is correct
6 Correct 367 ms 1228 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 11 ms 1100 KB Output is correct
4 Correct 20 ms 1100 KB Output is correct
5 Correct 185 ms 1240 KB Output is correct
6 Correct 175 ms 1232 KB Output is correct
7 Correct 188 ms 1256 KB Output is correct
8 Correct 196 ms 1232 KB Output is correct
9 Correct 2 ms 1196 KB Output is correct
10 Correct 2 ms 1100 KB Output is correct
11 Correct 11 ms 1100 KB Output is correct
12 Correct 11 ms 1192 KB Output is correct
13 Correct 84 ms 1200 KB Output is correct
14 Correct 96 ms 1204 KB Output is correct
15 Correct 163 ms 1228 KB Output is correct
16 Correct 216 ms 1228 KB Output is correct
17 Correct 185 ms 1208 KB Output is correct
18 Correct 4 ms 1192 KB Output is correct
19 Correct 4 ms 1100 KB Output is correct
20 Correct 13 ms 1196 KB Output is correct
21 Correct 13 ms 1228 KB Output is correct
22 Correct 35 ms 1180 KB Output is correct
23 Correct 35 ms 1192 KB Output is correct
24 Correct 49 ms 1204 KB Output is correct
25 Correct 47 ms 1100 KB Output is correct
26 Correct 3 ms 1100 KB Output is correct
27 Correct 2 ms 1100 KB Output is correct
28 Correct 139 ms 1212 KB Output is correct
29 Correct 170 ms 1100 KB Output is correct
30 Correct 358 ms 1264 KB Output is correct
31 Correct 378 ms 1256 KB Output is correct
32 Correct 379 ms 1260 KB Output is correct
33 Correct 362 ms 1260 KB Output is correct
34 Correct 1 ms 1100 KB Output is correct
35 Correct 12 ms 1204 KB Output is correct
36 Correct 83 ms 1192 KB Output is correct
37 Correct 195 ms 1220 KB Output is correct
38 Correct 402 ms 1268 KB Output is correct
39 Correct 367 ms 1228 KB Output is correct
40 Correct 100 ms 1204 KB Output is correct
41 Correct 190 ms 1228 KB Output is correct
42 Correct 278 ms 1252 KB Output is correct
43 Correct 404 ms 1260 KB Output is correct
44 Correct 369 ms 1276 KB Output is correct
45 Correct 415 ms 1304 KB Output is correct
46 Correct 186 ms 1228 KB Output is correct
47 Correct 276 ms 1268 KB Output is correct
48 Correct 297 ms 1252 KB Output is correct