oj.uz

Submission #626608

# Submission time Handle Problem Language Result Execution time Memory
626608 2022-08-11T15:02:49 Z d4xn Catfish Farm (IOI22_fish) C++17
32 / 100
 1000 ms 175604 KB 
#pragma GCC optimize ("Ofast")
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define tuple2 tuple<int, int>
#define tuple3 tuple<int, int, int>
 
const int N = 1e5;
 
int n, m;
vi c[N];
unordered_map<int, int> w[N];
unordered_map<int, ll> pre[N];
unordered_map<int, ll> dp[4][N];
 
ll mx(int curr, int h1, int state) {
  if (curr == -1) return 0;
  
  auto it = dp[state][curr].find(h1);
  if (it != dp[state][curr].end()) return it->second;
  
  if (state != 3) dp[state][curr][h1] = mx(curr-1, h1, 3);
  else dp[state][curr][h1] = mx(curr-1, 0, 2);
  it = dp[state][curr].find(h1);
 
  if (!state) {
    if (curr+1 < n) {
      for (int h : c[curr+1]) {
        h++;
        if (h >= h1) break;
 
        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += pre[curr-1][h-1];
        }
  
        // ver si he eliminado alguno de los que he pillado
        cnt -= pre[curr][min(h, h1)-1];
  
        it->second = max(it->second, cnt + mx(curr-1, h, 0));
      }
    }
  
    if (curr-1 >= 0) {
      for (int h : c[curr-1]) {
        h++;
        if (h >= h1) break;
        
        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += pre[curr-1][h-1];
        }
  
        // ver si he eliminado alguno de los que he pillado
        cnt -= pre[curr][min(h, h1)-1];
  
        it->second = max(it->second, cnt + mx(curr-1, h, 0));
      }
    }
  }
  else if (state == 1 || state == 2) {
    if (curr+1 < n) {
      for (int h : c[curr+1]) {
        h++;
        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += pre[curr-1][h-1];
        }
 
        // ver si pillo los de la derecha      
        if (h > h1 && curr+1 < n) {
          cnt += pre[curr+1][h-1] - pre[curr+1][h1-1];
        }
        
        // ver si he eliminado alguno de los que he pillado
        cnt -= pre[curr][min(h, h1)-1];
  
        if (h <= h1) it->second = max(it->second, cnt + mx(curr-1, h, 0));
        else it->second = max(it->second, cnt + mx(curr-1, h, 1));
      }
    }
  
    if (curr-1 >= 0) {
      for (int h : c[curr-1]) {
        h++;
        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += pre[curr-1][h-1];
        }
 
        // ver si pillo los de la derecha      
        if (h > h1 && curr+1 < n) {
          cnt += pre[curr+1][h-1] - pre[curr+1][h1-1];
        }
        
        // ver si he eliminado alguno de los que he pillado
        cnt -= pre[curr][min(h, h1)-1];
  
        if (h <= h1) it->second = max(it->second, cnt + mx(curr-1, h, 0));
        else it->second = max(it->second, cnt + mx(curr-1, h, 1));
      }
    }
  }
  else {
    if (curr+1 < n) {
      for (int h : c[curr+1]) {
        h++;
        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += pre[curr-1][h-1];
        }
 
        // ver si pillo los de la derecha      
        if (h > h1 && curr+1 < n) {
          cnt += pre[curr+1][h-1] - pre[curr+1][h1-1];
        }
  
        it->second = max(it->second, cnt + mx(curr-1, h, 2));
      }
    }
  
    if (curr-1 >= 0) {
      for (int h : c[curr-1]) {
        h++;
        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += pre[curr-1][h-1];
        }
 
        // ver si pillo los de la derecha      
        if (h > h1 && curr+1 < n) {
          cnt += pre[curr+1][h-1] - pre[curr+1][h1-1];
        }
  
        it->second = max(it->second, cnt + mx(curr-1, h, 2));
      }
    }
  }
 
  return it->second;
}
 
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  n = N;
  m = M;
 
  ll sum = 0;
  bool odd = 0;
  int mxX = 0;
  for (int i = 0; i < m; i++) {
    sum += W[i];
    if (X[i]%2) odd = 1;
    mxX = max(mxX, X[i]);
 
    w[X[i]][Y[i]] = W[i];
    c[X[i]].push_back(Y[i]);
  }
 
  if (!odd) return sum;
  if (mxX <= 1) {
    ll pre0[n], pre1[n];
    for (int i = 0; i < n; i++) {
      pre0[i] = (i ? pre0[i-1] : 0);
      pre1[i] = (i ? pre1[i-1] : 0);
 
      auto it = w[0].find(i);
      if (it != w[0].end()) pre0[i] += it->second;
 
 
      it = w[1].find(i);
      if (it != w[1].end()) pre1[i] += it->second;
    }
 
    if (n == 2) return max(pre0[n-1], pre1[n-1]);
 
    ll ans = max(pre0[n-1], pre1[n-1]);
    for (int i = 0; i < n; i++) {
      ans = max(ans, pre0[i] + pre1[n-1] - pre1[i]);
    }
 
    if (n >= 3) return ans;
  }
 
  map<int, int> heights;
  for (int i = 0; i < n; i++) {
    pre[i][-1] = 0;
 
    for (int &h : c[i]) heights[h]++;
 
    if (i >= 3) {
      for (int &h : c[i-3]) {
        heights[h]--;
        if (!heights[h]) heights.erase(h);
      }
    }
 
    ll sum1 = 0;
    ll sum2 = 0;
    ll sum3 = 0;
    for (auto &[h, cnt] : heights) {
      auto it = w[i].find(h);
      if (it != w[i].end()) sum3 += it->second;
      pre[i][h] = sum3;
 
      if (i-1 >= 0) {
        it = w[i-1].find(h);
        if (it != w[i-1].end()) sum2 += it->second;
        pre[i-1][h] = sum2;
      }
      if (i-2 >= 0) {
        it = w[i-2].find(h);
        if (it != w[i-2].end()) sum1 += it->second;
        pre[i-2][h] = sum1;
      }
    }
  }
 
  return mx(n-1, 0, 2);
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 40916 KB Output is correct
2 Correct 60 ms 42844 KB Output is correct
3 Correct 19 ms 35412 KB Output is correct
4 Correct 19 ms 35412 KB Output is correct
5 Correct 173 ms 57572 KB Output is correct
6 Correct 293 ms 59764 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35460 KB Output is correct
2 Correct 85 ms 47704 KB Output is correct
3 Correct 104 ms 51532 KB Output is correct
4 Correct 51 ms 40832 KB Output is correct
5 Correct 67 ms 42844 KB Output is correct
6 Correct 24 ms 35512 KB Output is correct
7 Correct 20 ms 35412 KB Output is correct
8 Correct 20 ms 35412 KB Output is correct
9 Correct 20 ms 35412 KB Output is correct
10 Correct 20 ms 35524 KB Output is correct
11 Correct 22 ms 35452 KB Output is correct
12 Correct 53 ms 42372 KB Output is correct
13 Correct 59 ms 44244 KB Output is correct
14 Correct 55 ms 42336 KB Output is correct
15 Correct 64 ms 43652 KB Output is correct
16 Correct 54 ms 42296 KB Output is correct
17 Correct 57 ms 43648 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35412 KB Output is correct
2 Correct 78 ms 79220 KB Output is correct
3 Correct 244 ms 119672 KB Output is correct
4 Correct 185 ms 113656 KB Output is correct
5 Correct 356 ms 150524 KB Output is correct
6 Correct 354 ms 150496 KB Output is correct
7 Correct 347 ms 150520 KB Output is correct
8 Correct 376 ms 150508 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35412 KB Output is correct
2 Correct 20 ms 35540 KB Output is correct
3 Correct 20 ms 35412 KB Output is correct
4 Correct 21 ms 35432 KB Output is correct
5 Correct 26 ms 35468 KB Output is correct
6 Correct 20 ms 35524 KB Output is correct
7 Correct 21 ms 35492 KB Output is correct
8 Correct 21 ms 35412 KB Output is correct
9 Correct 21 ms 35716 KB Output is correct
10 Correct 26 ms 36288 KB Output is correct
11 Correct 23 ms 35796 KB Output is correct
12 Correct 26 ms 36056 KB Output is correct
13 Correct 20 ms 35540 KB Output is correct
14 Correct 21 ms 36052 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35412 KB Output is correct
2 Correct 20 ms 35540 KB Output is correct
3 Correct 20 ms 35412 KB Output is correct
4 Correct 21 ms 35432 KB Output is correct
5 Correct 26 ms 35468 KB Output is correct
6 Correct 20 ms 35524 KB Output is correct
7 Correct 21 ms 35492 KB Output is correct
8 Correct 21 ms 35412 KB Output is correct
9 Correct 21 ms 35716 KB Output is correct
10 Correct 26 ms 36288 KB Output is correct
11 Correct 23 ms 35796 KB Output is correct
12 Correct 26 ms 36056 KB Output is correct
13 Correct 20 ms 35540 KB Output is correct
14 Correct 21 ms 36052 KB Output is correct
15 Correct 27 ms 35876 KB Output is correct
16 Correct 43 ms 36344 KB Output is correct
17 Execution timed out 1092 ms 48000 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35412 KB Output is correct
2 Correct 20 ms 35540 KB Output is correct
3 Correct 20 ms 35412 KB Output is correct
4 Correct 21 ms 35432 KB Output is correct
5 Correct 26 ms 35468 KB Output is correct
6 Correct 20 ms 35524 KB Output is correct
7 Correct 21 ms 35492 KB Output is correct
8 Correct 21 ms 35412 KB Output is correct
9 Correct 21 ms 35716 KB Output is correct
10 Correct 26 ms 36288 KB Output is correct
11 Correct 23 ms 35796 KB Output is correct
12 Correct 26 ms 36056 KB Output is correct
13 Correct 20 ms 35540 KB Output is correct
14 Correct 21 ms 36052 KB Output is correct
15 Correct 27 ms 35876 KB Output is correct
16 Correct 43 ms 36344 KB Output is correct
17 Execution timed out 1092 ms 48000 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35412 KB Output is correct
2 Correct 78 ms 79220 KB Output is correct
3 Correct 244 ms 119672 KB Output is correct
4 Correct 185 ms 113656 KB Output is correct
5 Correct 356 ms 150524 KB Output is correct
6 Correct 354 ms 150496 KB Output is correct
7 Correct 347 ms 150520 KB Output is correct
8 Correct 376 ms 150508 KB Output is correct
9 Correct 462 ms 175604 KB Output is correct
10 Incorrect 270 ms 103608 KB 1st lines differ - on the 1st token, expected: '36454348383152', found: '36454254938101'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 40916 KB Output is correct
2 Correct 60 ms 42844 KB Output is correct
3 Correct 19 ms 35412 KB Output is correct
4 Correct 19 ms 35412 KB Output is correct
5 Correct 173 ms 57572 KB Output is correct
6 Correct 293 ms 59764 KB Output is correct
7 Correct 20 ms 35460 KB Output is correct
8 Correct 85 ms 47704 KB Output is correct
9 Correct 104 ms 51532 KB Output is correct
10 Correct 51 ms 40832 KB Output is correct
11 Correct 67 ms 42844 KB Output is correct
12 Correct 24 ms 35512 KB Output is correct
13 Correct 20 ms 35412 KB Output is correct
14 Correct 20 ms 35412 KB Output is correct
15 Correct 20 ms 35412 KB Output is correct
16 Correct 20 ms 35524 KB Output is correct
17 Correct 22 ms 35452 KB Output is correct
18 Correct 53 ms 42372 KB Output is correct
19 Correct 59 ms 44244 KB Output is correct
20 Correct 55 ms 42336 KB Output is correct
21 Correct 64 ms 43652 KB Output is correct
22 Correct 54 ms 42296 KB Output is correct
23 Correct 57 ms 43648 KB Output is correct
24 Correct 20 ms 35412 KB Output is correct
25 Correct 78 ms 79220 KB Output is correct
26 Correct 244 ms 119672 KB Output is correct
27 Correct 185 ms 113656 KB Output is correct
28 Correct 356 ms 150524 KB Output is correct
29 Correct 354 ms 150496 KB Output is correct
30 Correct 347 ms 150520 KB Output is correct
31 Correct 376 ms 150508 KB Output is correct
32 Correct 20 ms 35412 KB Output is correct
33 Correct 20 ms 35540 KB Output is correct
34 Correct 20 ms 35412 KB Output is correct
35 Correct 21 ms 35432 KB Output is correct
36 Correct 26 ms 35468 KB Output is correct
37 Correct 20 ms 35524 KB Output is correct
38 Correct 21 ms 35492 KB Output is correct
39 Correct 21 ms 35412 KB Output is correct
40 Correct 21 ms 35716 KB Output is correct
41 Correct 26 ms 36288 KB Output is correct
42 Correct 23 ms 35796 KB Output is correct
43 Correct 26 ms 36056 KB Output is correct
44 Correct 20 ms 35540 KB Output is correct
45 Correct 21 ms 36052 KB Output is correct
46 Correct 27 ms 35876 KB Output is correct
47 Correct 43 ms 36344 KB Output is correct
48 Execution timed out 1092 ms 48000 KB Time limit exceeded
49 Halted 0 ms 0 KB -