oj.uz

Submission #824795

# Submission time Handle Problem Language Result Execution time Memory
824795 2023-08-14T10:17:04 Z Sam_a17 Cloud Computing (CEOI18_clo) C++17
100 / 100
 829 ms 2900 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const long long inf = -1e15;
int n, m;
#define point pair<long long, pair<long long, long long>>

vector<point> a;

void solve_() {
  cin >> n;

  int max_cores;
  for(int i = 1; i <= n; i++) {
    point p; cin >> p.second.first >> p.first >> p.second.second;
    max_cores += p.second.first;
    p.second.second *= -1;
    a.push_back(p);
  }

  cin >> m;
  for(int i = 1; i <= m; i++) {
    point p; cin >> p.second.first >> p.first >> p.second.second;
    p.second.first *= -1;
    a.push_back(p);
  }

  sort(rall(a));

  vector<vector<long long>> dp(2, vector<long long> (max_cores + 1, inf));
  dp[0][0] = 0;

  // dbg(max_cores)

  long long pat = 0;
  for(int i = 0; i < sz(a); i++) {
    int cur = (i + 1) & 1, prev = 1 - cur;

    if(a[i].second.first > 0) {
      for(int j = max_cores - a[i].second.first; j >= 0; j--) {
        dp[cur][j + a[i].second.first] = max(dp[cur][j + a[i].second.first], dp[prev][j] + a[i].second.second);
      }
    } else {
      int val = -a[i].second.first;
      for(int j = val; j <= max_cores; j++) {
        if(dp[prev][j] == inf) continue;
        dp[cur][j - val] = max(dp[cur][j - val], dp[prev][j] + a[i].second.second);
      }
    }

    for(int j = 0; j <= max_cores; j++) {
      dp[cur][j] = max(dp[prev][j], dp[cur][j]);
      pat = max(pat, dp[cur][j]);
      dp[prev][j] = inf;
    }

  }

  cout << pat << '\n';
}
 
int main() {
  fastIO();
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

clo.cpp: In function 'void setIO(std::string)':
clo.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
clo.cpp: In function 'void solve_()':
clo.cpp:97:64: warning: 'max_cores' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |   vector<vector<long long>> dp(2, vector<long long> (max_cores + 1, inf));
      |                                                      ~~~~~~~~~~^~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 3 ms 460 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 58 ms 848 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 238 ms 1620 KB Output is correct
8 Correct 41 ms 668 KB Output is correct
9 Correct 371 ms 2388 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 356 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 20 ms 468 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 409 ms 1748 KB Output is correct
6 Correct 774 ms 2644 KB Output is correct
7 Correct 829 ms 2644 KB Output is correct
8 Correct 766 ms 2516 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 50 ms 980 KB Output is correct
4 Correct 9 ms 340 KB Output is correct
5 Correct 734 ms 2632 KB Output is correct
6 Correct 759 ms 2644 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 58 ms 848 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 238 ms 1620 KB Output is correct
16 Correct 41 ms 668 KB Output is correct
17 Correct 371 ms 2388 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 356 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 320 KB Output is correct
27 Correct 0 ms 320 KB Output is correct
28 Correct 20 ms 468 KB Output is correct
29 Correct 3 ms 340 KB Output is correct
30 Correct 409 ms 1748 KB Output is correct
31 Correct 774 ms 2644 KB Output is correct
32 Correct 829 ms 2644 KB Output is correct
33 Correct 766 ms 2516 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 50 ms 980 KB Output is correct
37 Correct 9 ms 340 KB Output is correct
38 Correct 734 ms 2632 KB Output is correct
39 Correct 759 ms 2644 KB Output is correct
40 Correct 46 ms 852 KB Output is correct
41 Correct 126 ms 1236 KB Output is correct
42 Correct 10 ms 532 KB Output is correct
43 Correct 780 ms 2900 KB Output is correct
44 Correct 775 ms 2900 KB Output is correct
45 Correct 739 ms 2900 KB Output is correct
46 Correct 5 ms 332 KB Output is correct
47 Correct 10 ms 468 KB Output is correct
48 Correct 9 ms 468 KB Output is correct