oj.uz

Submission #470268

# Submission time Handle Problem Language Result Execution time Memory
470268 2021-09-03T11:05:09 Z nia_azm Cloud Computing (CEOI18_clo) C++14
100 / 100
 848 ms 2060 KB 
#include<bits/stdc++.h>
using namespace std;
 
typedef pair<long long, long long> pll;
typedef pair<int, long long> pil;
typedef pair<long long, int> pli;
typedef pair<int, int> pii;
typedef long double ld;
typedef long long ll;
 
#define mp make_pair
#define pb push_back
#define in insert
#define ers erase
#define S second
#define F first
 
const ll inF = 1e18 + 5;
const int N = 1e5 + 5;
int n, m;
ll ans, dp[5][N];
 
struct strct {
        int c, f, v;
};
vector<strct> vec;
 
int cmp(strct i, strct j){
        if (i.f == j.f){
                if (i.c > j.c) return 1;
                return 0;
        }
        if (i.f > j.f) return 1;
        return 0;
}
 
void read_input() {
        cin >> n;
        for (int i = 0; i < n; i++) {
                int cc, ff, v;
                cin >> cc >> ff >> v;
                v *= -1;
                strct x;
                x.c = cc, x.f = ff, x.v = v;
                vec.pb(x);
        }
        cin >> m;
        for (int i = 0; i < m; i++) {
                int cc, ff, v;
                cin >> cc >> ff >> v;
                cc *= (-1);
                strct x;
                x.c = cc; x.f = ff; x.v = v;
                vec.pb(x);
        }
        sort(vec.begin(), vec.end(), cmp);
}
 
void solve() {
        for (int i = 1; i < N; i++) dp[0][i]= -inF;
        for (int i = 0; i < vec.size(); i++) {
                for (int j = 0; j < N; j++) {
                        if (j < vec[i].c) dp[1][j] = dp[0][j];
                        else if (j - vec[i].c >= N) dp[1][j] = dp[0][j];
                        else dp[1][j] = max(dp[0][j - vec[i].c] + vec[i].v, dp[0][j]);
                }
                for (int j = 0; j < N; j++) dp[0][j] = dp[1][j];
        }
        for (int j = 0; j < N; j++) ans = max(ans, dp[0][j]);
        cout << ans << '\n';
}
 
int main() {
        ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
        read_input(), solve();
        return 0;
}

Compilation message

clo.cpp: In function 'void solve()':
clo.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<strct>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int i = 0; i < vec.size(); i++) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 22 ms 1888 KB Output is correct
4 Correct 42 ms 1892 KB Output is correct
5 Correct 383 ms 1932 KB Output is correct
6 Correct 375 ms 1924 KB Output is correct
7 Correct 436 ms 1868 KB Output is correct
8 Correct 411 ms 1920 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 3 ms 1868 KB Output is correct
3 Correct 22 ms 1892 KB Output is correct
4 Correct 23 ms 1892 KB Output is correct
5 Correct 182 ms 1868 KB Output is correct
6 Correct 211 ms 1892 KB Output is correct
7 Correct 393 ms 1920 KB Output is correct
8 Correct 421 ms 1924 KB Output is correct
9 Correct 390 ms 1920 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1868 KB Output is correct
2 Correct 8 ms 1868 KB Output is correct
3 Correct 38 ms 1876 KB Output is correct
4 Correct 36 ms 1868 KB Output is correct
5 Correct 81 ms 1868 KB Output is correct
6 Correct 73 ms 1884 KB Output is correct
7 Correct 100 ms 1888 KB Output is correct
8 Correct 117 ms 1868 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1868 KB Output is correct
2 Correct 4 ms 1868 KB Output is correct
3 Correct 301 ms 1868 KB Output is correct
4 Correct 361 ms 1924 KB Output is correct
5 Correct 749 ms 1980 KB Output is correct
6 Correct 785 ms 2012 KB Output is correct
7 Correct 768 ms 2016 KB Output is correct
8 Correct 848 ms 2016 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 32 ms 1868 KB Output is correct
3 Correct 161 ms 1896 KB Output is correct
4 Correct 453 ms 1928 KB Output is correct
5 Correct 789 ms 1972 KB Output is correct
6 Correct 827 ms 1964 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 22 ms 1888 KB Output is correct
4 Correct 42 ms 1892 KB Output is correct
5 Correct 383 ms 1932 KB Output is correct
6 Correct 375 ms 1924 KB Output is correct
7 Correct 436 ms 1868 KB Output is correct
8 Correct 411 ms 1920 KB Output is correct
9 Correct 3 ms 1868 KB Output is correct
10 Correct 3 ms 1868 KB Output is correct
11 Correct 22 ms 1892 KB Output is correct
12 Correct 23 ms 1892 KB Output is correct
13 Correct 182 ms 1868 KB Output is correct
14 Correct 211 ms 1892 KB Output is correct
15 Correct 393 ms 1920 KB Output is correct
16 Correct 421 ms 1924 KB Output is correct
17 Correct 390 ms 1920 KB Output is correct
18 Correct 10 ms 1868 KB Output is correct
19 Correct 8 ms 1868 KB Output is correct
20 Correct 38 ms 1876 KB Output is correct
21 Correct 36 ms 1868 KB Output is correct
22 Correct 81 ms 1868 KB Output is correct
23 Correct 73 ms 1884 KB Output is correct
24 Correct 100 ms 1888 KB Output is correct
25 Correct 117 ms 1868 KB Output is correct
26 Correct 4 ms 1868 KB Output is correct
27 Correct 4 ms 1868 KB Output is correct
28 Correct 301 ms 1868 KB Output is correct
29 Correct 361 ms 1924 KB Output is correct
30 Correct 749 ms 1980 KB Output is correct
31 Correct 785 ms 2012 KB Output is correct
32 Correct 768 ms 2016 KB Output is correct
33 Correct 848 ms 2016 KB Output is correct
34 Correct 3 ms 1868 KB Output is correct
35 Correct 32 ms 1868 KB Output is correct
36 Correct 161 ms 1896 KB Output is correct
37 Correct 453 ms 1928 KB Output is correct
38 Correct 789 ms 1972 KB Output is correct
39 Correct 827 ms 1964 KB Output is correct
40 Correct 210 ms 1908 KB Output is correct
41 Correct 387 ms 1988 KB Output is correct
42 Correct 593 ms 2000 KB Output is correct
43 Correct 834 ms 2020 KB Output is correct
44 Correct 771 ms 2028 KB Output is correct
45 Correct 809 ms 2060 KB Output is correct
46 Correct 392 ms 1952 KB Output is correct
47 Correct 600 ms 2000 KB Output is correct
48 Correct 568 ms 2004 KB Output is correct