oj.uz

Submission #217593

# Submission time Handle Problem Language Result Execution time Memory
217593 2020-03-30T10:26:11 Z DystoriaX Cloud Computing (CEOI18_clo) C++14
18 / 100
 405 ms 2048 KB 
#include <bits/stdc++.h>

using namespace std;

struct node{
    int c, f, v;
};

int n, m;
const int MAX = 100001;
vector<node> comp, dem;
priority_queue<int, vector<int>, greater<int> > pq;
long long ans = 0, dp[MAX], dps[MAX];

bool cp(node a, node b){
    return a.f > b.f;
}

int main(){
    scanf("%d", &n);

    comp.resize(n + 1);
    for(int i = 1; i <= n; i++) scanf("%d%d%d", &comp[i].c, &comp[i].f, &comp[i].v);

    scanf("%d", &m);

    dem.resize(m + 1);
    for(int i = 1; i <= m; i++) scanf("%d%d%d", &dem[i].c, &dem[i].f, &dem[i].v);

    sort(comp.begin() + 1, comp.end(), cp);
    sort(dem.begin() + 1, dem.end(), cp);

    //dp = minCost, maxProfit
    for(int i = 0; i < MAX; i++) dp[i] = 1e18;

    dp[0] = 0;
    for(int i = 1; i <= n; i++)
        for(int k = MAX - 1; k >= comp[i].c; k--)
            dp[k] = min(dp[k], dp[k - comp[i].c] + comp[i].v);

    for(int i = 1; i <= m; i++)
        for(int k = MAX - 1; k >= dem[i].c; k--)
            dps[k] = max(dps[k], dps[k - dem[i].c] + dem[i].v);

    long long tp = 0;
    for(int i = 0; i < MAX; i++){
        tp = max(tp, dps[i]);
        ans = max(ans, tp - dp[i]);
    }

    printf("%lld\n", ans);

    return 0;
}

Compilation message

clo.cpp: In function 'int main()':
clo.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
clo.cpp:23:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d%d%d", &comp[i].c, &comp[i].f, &comp[i].v);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
clo.cpp:28:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= m; i++) scanf("%d%d%d", &dem[i].c, &dem[i].f, &dem[i].v);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1920 KB Output is correct
2 Correct 6 ms 1920 KB Output is correct
3 Correct 16 ms 1920 KB Output is correct
4 Correct 26 ms 1920 KB Output is correct
5 Incorrect 189 ms 1920 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1920 KB Output is correct
2 Incorrect 6 ms 1920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1920 KB Output is correct
2 Correct 7 ms 1920 KB Output is correct
3 Correct 161 ms 1924 KB Output is correct
4 Correct 184 ms 1920 KB Output is correct
5 Correct 376 ms 1916 KB Output is correct
6 Correct 385 ms 1912 KB Output is correct
7 Correct 405 ms 2040 KB Output is correct
8 Correct 380 ms 1912 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1920 KB Output is correct
2 Incorrect 21 ms 1920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1920 KB Output is correct
2 Correct 6 ms 1920 KB Output is correct
3 Correct 16 ms 1920 KB Output is correct
4 Correct 26 ms 1920 KB Output is correct
5 Incorrect 189 ms 1920 KB Output isn't correct
6 Halted 0 ms 0 KB -