oj.uz

Submission #838855

# Submission time Handle Problem Language Result Execution time Memory
838855 2023-08-27T23:36:11 Z taher Catfish Farm (IOI22_fish) C++17
84 / 100
 1000 ms 293204 KB 
#include <bits/stdc++.h>
#include "fish.h"

using namespace std;

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
  vector<vector<int>> at(n);
  vector<vector<int>> ids(n);
  for (int i = 0; i < m; i++) {
    at[x[i]].push_back(y[i]); 
    ids[x[i]].push_back(i);
  }
  
  
  for (int i = 0; i < n; i++) {
    if (at[i].empty()) {
      continue;
    }
    sort(ids[i].begin(), ids[i].end(), [&](int a, int b) {
      return y[a] < y[b];    
    });
    sort(at[i].begin(), at[i].end()); 
  }
  
  vector<vector<long long>> pref(n);
  for (int i = 0; i < n; i++) {
    if (at[i].empty()) {
      continue; 
    }
    pref[i].resize((int) at[i].size());
    pref[i][0] = 1LL * w[ids[i][0]];
    for (int j = 1; j < (int) at[i].size(); j++) {
      pref[i][j] = pref[i][j - 1] + w[ids[i][j]];
    }
  }
  
  vector<vector<int>> endpoints(n);
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      for (auto v : at[i - 1]) {
        endpoints[i].push_back(v); 
      } 
    }
    if (i < n - 1) {
      for (auto v : at[i + 1]) {
        endpoints[i].push_back(v); 
      }            
    }
    endpoints[i].push_back(-1);
    
    sort(endpoints[i].begin(), endpoints[i].end());
    endpoints[i].erase(unique(endpoints[i].begin(), endpoints[i].end()), endpoints[i].end());
  }
  
  int current = 0;
  vector<vector<int>> coords(n);
  for (int i = 0; i < n; i++) {
    coords[i].resize((int) endpoints[i].size());
    for (int j = 0; j < (int) endpoints[i].size(); j++) {
      coords[i][j] = current++; 
    }
  }  
  
  auto Count = [&](int col, int from, int to) {
    int xx = upper_bound(at[col].begin(), at[col].end(), from) - at[col].begin();
    int yy = upper_bound(at[col].begin(), at[col].end(), to) - at[col].begin();
    yy--;
    
    if (xx <= yy) {
      assert(yy < (int) at[col].size());
      long long s = pref[col][yy];
      if (xx > 0) {
        s -= pref[col][xx - 1]; 
      }
      return s;        
    }
    return 0LL;
  };
  
  /*
    0: undef
    1: increasing
    2: decreasing
  */
  
  vector<vector<vector<long long>>> dp(current, vector<vector<long long>> (3, vector<long long> (2, -1)));
  
  function<long long(int, int, int, int)> DP = [&](int col, int id, int state, int used_dec) {
    
    if (dp[coords[col][id]][state][used_dec] != -1) {
      return dp[coords[col][id]][state][used_dec]; 
    }
    
    long long ans = 0;
    int current_height = endpoints[col][id];
    if (state == 1) {
      if (id + 1 < (int) endpoints[col].size()) {
        long long cnt = Count(col - 1, current_height, endpoints[col][id + 1]);
        ans = max(ans, DP(col, id + 1, 1, used_dec) + cnt); 
      }      
    } else if (state == 2) {
      if (id - 1 > 0) {
        long long cnt = Count(col, endpoints[col][id - 1], current_height);
        ans = max(ans, DP(col, id - 1, 2, used_dec) + cnt);
      } 
    } else {
      if (id + 1 < (int) endpoints[col].size()) {
        ans = max(ans, DP(col, id + 1, 0, used_dec)); 
      }
    }
    
    if (col + 1 < n) {
      if (!used_dec) {
        int nid = lower_bound(endpoints[col + 1].begin(), endpoints[col + 1].end(), current_height) - endpoints[col + 1].begin();
        if (nid < (int) endpoints[col + 1].size()) {
          ans = max(ans, DP(col + 1, nid, 1, used_dec) + Count(col, current_height, endpoints[col + 1][nid])); 
        }
      }
      int nid = upper_bound(endpoints[col + 1].begin(), endpoints[col + 1].end(), current_height) - endpoints[col + 1].begin();
      --nid;
      if (nid > 0) {
        ans = max(ans, DP(col + 1, nid, 2, 1) + Count(col + 1, endpoints[col + 1][nid], current_height));
      }
      
      ans = max(ans, Count(col + 1, -1, current_height));
    }
    if (col + 2 < n) {
      int nid = lower_bound(endpoints[col + 2].begin(), endpoints[col + 2].end(), current_height) - endpoints[col + 2].begin();
      if (nid < (int) endpoints[col + 2].size()) {
        ans = max(ans, DP(col + 2, nid, 1, 0) + Count(col + 1, -1, endpoints[col + 2][nid]));
      }
      nid = 0;
      ans = max(ans, DP(col + 2, nid, 0, 0) + Count(col + 1, -1, current_height));
    }
    return dp[coords[col][id]][state][used_dec] = ans;
  };
  
  long long res = DP(0, 0, 0, 0);
  return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 96468 KB Output is correct
2 Correct 145 ms 112192 KB Output is correct
3 Correct 60 ms 62820 KB Output is correct
4 Correct 59 ms 62860 KB Output is correct
5 Correct 622 ms 293204 KB Output is correct
6 Correct 528 ms 245668 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 301 ms 132728 KB Output is correct
3 Correct 368 ms 160292 KB Output is correct
4 Correct 131 ms 97764 KB Output is correct
5 Correct 145 ms 113956 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 59 ms 62912 KB Output is correct
11 Correct 57 ms 62888 KB Output is correct
12 Correct 181 ms 114552 KB Output is correct
13 Correct 203 ms 134336 KB Output is correct
14 Correct 163 ms 116396 KB Output is correct
15 Correct 200 ms 118136 KB Output is correct
16 Correct 157 ms 106444 KB Output is correct
17 Correct 179 ms 118000 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62920 KB Output is correct
2 Correct 58 ms 62796 KB Output is correct
3 Correct 124 ms 74060 KB Output is correct
4 Correct 120 ms 73948 KB Output is correct
5 Correct 184 ms 94152 KB Output is correct
6 Correct 189 ms 94192 KB Output is correct
7 Correct 187 ms 94144 KB Output is correct
8 Correct 183 ms 94128 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 724 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 4 ms 1108 KB Output is correct
17 Correct 91 ms 15568 KB Output is correct
18 Correct 89 ms 13876 KB Output is correct
19 Correct 73 ms 15060 KB Output is correct
20 Correct 80 ms 12512 KB Output is correct
21 Correct 68 ms 12184 KB Output is correct
22 Correct 161 ms 23908 KB Output is correct
23 Correct 22 ms 6100 KB Output is correct
24 Correct 75 ms 15440 KB Output is correct
25 Correct 3 ms 1084 KB Output is correct
26 Correct 21 ms 5332 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 4 ms 1108 KB Output is correct
17 Correct 91 ms 15568 KB Output is correct
18 Correct 89 ms 13876 KB Output is correct
19 Correct 73 ms 15060 KB Output is correct
20 Correct 80 ms 12512 KB Output is correct
21 Correct 68 ms 12184 KB Output is correct
22 Correct 161 ms 23908 KB Output is correct
23 Correct 22 ms 6100 KB Output is correct
24 Correct 75 ms 15440 KB Output is correct
25 Correct 3 ms 1084 KB Output is correct
26 Correct 21 ms 5332 KB Output is correct
27 Correct 5 ms 3668 KB Output is correct
28 Correct 470 ms 68756 KB Output is correct
29 Correct 730 ms 132732 KB Output is correct
30 Correct 801 ms 197084 KB Output is correct
31 Correct 849 ms 194864 KB Output is correct
32 Correct 539 ms 79200 KB Output is correct
33 Correct 867 ms 201556 KB Output is correct
34 Correct 880 ms 200556 KB Output is correct
35 Correct 307 ms 63668 KB Output is correct
36 Correct 868 ms 175848 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62920 KB Output is correct
2 Correct 58 ms 62796 KB Output is correct
3 Correct 124 ms 74060 KB Output is correct
4 Correct 120 ms 73948 KB Output is correct
5 Correct 184 ms 94152 KB Output is correct
6 Correct 189 ms 94192 KB Output is correct
7 Correct 187 ms 94144 KB Output is correct
8 Correct 183 ms 94128 KB Output is correct
9 Correct 231 ms 113736 KB Output is correct
10 Correct 133 ms 58940 KB Output is correct
11 Correct 294 ms 121224 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 64 ms 62800 KB Output is correct
19 Correct 56 ms 62936 KB Output is correct
20 Correct 57 ms 62800 KB Output is correct
21 Correct 59 ms 62896 KB Output is correct
22 Correct 261 ms 121228 KB Output is correct
23 Correct 383 ms 168892 KB Output is correct
24 Correct 390 ms 177856 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 96468 KB Output is correct
2 Correct 145 ms 112192 KB Output is correct
3 Correct 60 ms 62820 KB Output is correct
4 Correct 59 ms 62860 KB Output is correct
5 Correct 622 ms 293204 KB Output is correct
6 Correct 528 ms 245668 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 301 ms 132728 KB Output is correct
9 Correct 368 ms 160292 KB Output is correct
10 Correct 131 ms 97764 KB Output is correct
11 Correct 145 ms 113956 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 0 ms 296 KB Output is correct
16 Correct 59 ms 62912 KB Output is correct
17 Correct 57 ms 62888 KB Output is correct
18 Correct 181 ms 114552 KB Output is correct
19 Correct 203 ms 134336 KB Output is correct
20 Correct 163 ms 116396 KB Output is correct
21 Correct 200 ms 118136 KB Output is correct
22 Correct 157 ms 106444 KB Output is correct
23 Correct 179 ms 118000 KB Output is correct
24 Correct 57 ms 62920 KB Output is correct
25 Correct 58 ms 62796 KB Output is correct
26 Correct 124 ms 74060 KB Output is correct
27 Correct 120 ms 73948 KB Output is correct
28 Correct 184 ms 94152 KB Output is correct
29 Correct 189 ms 94192 KB Output is correct
30 Correct 187 ms 94144 KB Output is correct
31 Correct 183 ms 94128 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 2 ms 980 KB Output is correct
42 Correct 2 ms 596 KB Output is correct
43 Correct 3 ms 852 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 2 ms 724 KB Output is correct
46 Correct 1 ms 596 KB Output is correct
47 Correct 4 ms 1108 KB Output is correct
48 Correct 91 ms 15568 KB Output is correct
49 Correct 89 ms 13876 KB Output is correct
50 Correct 73 ms 15060 KB Output is correct
51 Correct 80 ms 12512 KB Output is correct
52 Correct 68 ms 12184 KB Output is correct
53 Correct 161 ms 23908 KB Output is correct
54 Correct 22 ms 6100 KB Output is correct
55 Correct 75 ms 15440 KB Output is correct
56 Correct 3 ms 1084 KB Output is correct
57 Correct 21 ms 5332 KB Output is correct
58 Correct 5 ms 3668 KB Output is correct
59 Correct 470 ms 68756 KB Output is correct
60 Correct 730 ms 132732 KB Output is correct
61 Correct 801 ms 197084 KB Output is correct
62 Correct 849 ms 194864 KB Output is correct
63 Correct 539 ms 79200 KB Output is correct
64 Correct 867 ms 201556 KB Output is correct
65 Correct 880 ms 200556 KB Output is correct
66 Correct 307 ms 63668 KB Output is correct
67 Correct 868 ms 175848 KB Output is correct
68 Correct 231 ms 113736 KB Output is correct
69 Correct 133 ms 58940 KB Output is correct
70 Correct 294 ms 121224 KB Output is correct
71 Correct 1 ms 212 KB Output is correct
72 Correct 0 ms 212 KB Output is correct
73 Correct 1 ms 212 KB Output is correct
74 Correct 1 ms 304 KB Output is correct
75 Correct 0 ms 212 KB Output is correct
76 Correct 1 ms 212 KB Output is correct
77 Correct 64 ms 62800 KB Output is correct
78 Correct 56 ms 62936 KB Output is correct
79 Correct 57 ms 62800 KB Output is correct
80 Correct 59 ms 62896 KB Output is correct
81 Correct 261 ms 121228 KB Output is correct
82 Correct 383 ms 168892 KB Output is correct
83 Correct 390 ms 177856 KB Output is correct
84 Execution timed out 1064 ms 254516 KB Time limit exceeded
85 Halted 0 ms 0 KB -