oj.uz

Submission #625786

# Submission time Handle Problem Language Result Execution time Memory
625786 2022-08-10T19:13:44 Z d4xn Catfish Farm (IOI22_fish) C++17
29 / 100
 1000 ms 231532 KB 
#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#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];
map<tuple2, ll> dp[N];
//map<tuple<int, int, int>, ll> dp; // dp[i][j][k] = maximos peces que puedo conseguir
              // con las k primeras columnas donde
              // en la columna k+1 he subido i-1
              // en la columna k+2 he subido j-1
 
ll mx(int curr, int h1, int h2) {
  if (curr == -1) return 0;
  
  tuple2 t = make_tuple(h1, h2);
  auto it = dp[curr].find(t);
  if (it != dp[curr].end()) return it->second;
  
  dp[curr][t] = mx(curr-1, 0, h1);
  it = dp[curr].find(t);
 
  if (curr+1 < n) {
    for (int h : c[curr+1]) {
      h++;
      ll cnt = 0;
 
      // ver si pillo los de la derecha
      if (curr+1 < n && h > max(h1, h2)) {
        if (curr+2 == n) {
          cnt += pre[curr+1][h-1] - pre[curr+1][h1-1];
          //assert(pre[curr+1].count(h-1) && pre[curr+1].count(h1-1));
        }
        else {
          cnt += pre[curr+1][h-1] - pre[curr+1][max(h1, h2)-1];
          //assert(pre[curr+1].count(h-1) && pre[curr+1].count(max(h1, h2)-1));
        }
      }
 
      // ver si pillo los de la izquierda      
      if (curr-1 >= 0) {
        cnt += pre[curr-1][h-1];
        //assert(pre[curr-1].count(h-1));
      }
      
 
      // ver si he eliminado alguno de los que he pillado
      cnt -= pre[curr][min(h, h1)-1];
      //assert(pre[curr].count(min(h, h1)-1));
 
      it->second = max(it->second, cnt + mx(curr-1, h, h1));
    }
  }
 
  if (curr-1 >= 0) {
    for (int h : c[curr-1]) {
      h++;
      ll cnt = 0;
 
      // ver si pillo los de la derecha
      if (curr+1 < n && h > max(h1, h2)) {
        if (curr+2 == n) {
          cnt += pre[curr+1][h-1] - pre[curr+1][h1-1];
          //assert(pre[curr+1].count(h-1) && pre[curr+1].count(h1-1));
        }
        else {
          cnt += pre[curr+1][h-1] - pre[curr+1][max(h1, h2)-1];
          //assert(pre[curr+1].count(h-1) && pre[curr+1].count(max(h1, h2)-1));
        }
      }
 
      // ver si pillo los de la izquierda      
      if (curr-1 >= 0) {
        cnt += pre[curr-1][h-1];
        //assert(pre[curr-1].count(h-1));
      }
      
 
      // ver si he eliminado alguno de los que he pillado
      cnt -= pre[curr][min(h, h1)-1];
      //assert(pre[curr].count(min(h, h1)-1));
 
      it->second = max(it->second, cnt + mx(curr-1, h, h1));
    }
  }

  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;
 
  int mxX = 0;
  for (int i = 0; i < m; i++) {
    mxX = max(mxX, X[i]);

    w[X[i]][Y[i]] = W[i];
    c[X[i]].push_back(Y[i]);
  }
 
  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);
      if (w[0].count(i)) pre0[i] += w[0][i];
      if (w[1].count(i)) pre1[i] += w[1][i];
    }

    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 == 2) return max(pre0[n-1], pre1[n-1]);
    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, 0);
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 25044 KB Output is correct
2 Correct 53 ms 27012 KB Output is correct
3 Correct 13 ms 19752 KB Output is correct
4 Correct 15 ms 19796 KB Output is correct
5 Execution timed out 1099 ms 150680 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 18260 KB Output is correct
2 Correct 80 ms 30456 KB Output is correct
3 Correct 97 ms 34228 KB Output is correct
4 Correct 41 ms 25012 KB Output is correct
5 Correct 51 ms 27064 KB Output is correct
6 Correct 11 ms 18300 KB Output is correct
7 Correct 11 ms 18260 KB Output is correct
8 Correct 10 ms 18268 KB Output is correct
9 Correct 10 ms 18308 KB Output is correct
10 Correct 13 ms 19784 KB Output is correct
11 Correct 13 ms 19796 KB Output is correct
12 Correct 43 ms 25168 KB Output is correct
13 Correct 51 ms 27092 KB Output is correct
14 Correct 46 ms 25060 KB Output is correct
15 Correct 52 ms 26436 KB Output is correct
16 Correct 54 ms 25064 KB Output is correct
17 Correct 48 ms 26364 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19796 KB Output is correct
2 Correct 53 ms 52672 KB Output is correct
3 Correct 133 ms 72388 KB Output is correct
4 Correct 113 ms 68452 KB Output is correct
5 Correct 235 ms 94156 KB Output is correct
6 Correct 200 ms 94260 KB Output is correct
7 Correct 202 ms 94120 KB Output is correct
8 Correct 204 ms 94180 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 10 ms 18260 KB Output is correct
3 Correct 11 ms 18252 KB Output is correct
4 Correct 12 ms 18260 KB Output is correct
5 Correct 10 ms 18260 KB Output is correct
6 Correct 10 ms 18260 KB Output is correct
7 Correct 10 ms 18304 KB Output is correct
8 Correct 11 ms 18412 KB Output is correct
9 Correct 13 ms 18644 KB Output is correct
10 Correct 39 ms 20044 KB Output is correct
11 Correct 18 ms 18992 KB Output is correct
12 Correct 20 ms 19376 KB Output is correct
13 Correct 11 ms 18392 KB Output is correct
14 Correct 16 ms 19028 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 10 ms 18260 KB Output is correct
3 Correct 11 ms 18252 KB Output is correct
4 Correct 12 ms 18260 KB Output is correct
5 Correct 10 ms 18260 KB Output is correct
6 Correct 10 ms 18260 KB Output is correct
7 Correct 10 ms 18304 KB Output is correct
8 Correct 11 ms 18412 KB Output is correct
9 Correct 13 ms 18644 KB Output is correct
10 Correct 39 ms 20044 KB Output is correct
11 Correct 18 ms 18992 KB Output is correct
12 Correct 20 ms 19376 KB Output is correct
13 Correct 11 ms 18392 KB Output is correct
14 Correct 16 ms 19028 KB Output is correct
15 Correct 11 ms 18664 KB Output is correct
16 Execution timed out 1087 ms 26304 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 10 ms 18260 KB Output is correct
3 Correct 11 ms 18252 KB Output is correct
4 Correct 12 ms 18260 KB Output is correct
5 Correct 10 ms 18260 KB Output is correct
6 Correct 10 ms 18260 KB Output is correct
7 Correct 10 ms 18304 KB Output is correct
8 Correct 11 ms 18412 KB Output is correct
9 Correct 13 ms 18644 KB Output is correct
10 Correct 39 ms 20044 KB Output is correct
11 Correct 18 ms 18992 KB Output is correct
12 Correct 20 ms 19376 KB Output is correct
13 Correct 11 ms 18392 KB Output is correct
14 Correct 16 ms 19028 KB Output is correct
15 Correct 11 ms 18664 KB Output is correct
16 Execution timed out 1087 ms 26304 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19796 KB Output is correct
2 Correct 53 ms 52672 KB Output is correct
3 Correct 133 ms 72388 KB Output is correct
4 Correct 113 ms 68452 KB Output is correct
5 Correct 235 ms 94156 KB Output is correct
6 Correct 200 ms 94260 KB Output is correct
7 Correct 202 ms 94120 KB Output is correct
8 Correct 204 ms 94180 KB Output is correct
9 Correct 329 ms 138052 KB Output is correct
10 Correct 220 ms 76236 KB Output is correct
11 Correct 515 ms 134184 KB Output is correct
12 Correct 10 ms 18260 KB Output is correct
13 Correct 12 ms 18260 KB Output is correct
14 Correct 10 ms 18288 KB Output is correct
15 Correct 10 ms 18256 KB Output is correct
16 Correct 10 ms 18260 KB Output is correct
17 Correct 10 ms 18260 KB Output is correct
18 Correct 13 ms 19796 KB Output is correct
19 Correct 12 ms 19860 KB Output is correct
20 Correct 56 ms 52632 KB Output is correct
21 Correct 58 ms 52712 KB Output is correct
22 Correct 471 ms 133008 KB Output is correct
23 Correct 916 ms 210204 KB Output is correct
24 Execution timed out 1030 ms 231532 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 25044 KB Output is correct
2 Correct 53 ms 27012 KB Output is correct
3 Correct 13 ms 19752 KB Output is correct
4 Correct 15 ms 19796 KB Output is correct
5 Execution timed out 1099 ms 150680 KB Time limit exceeded
6 Halted 0 ms 0 KB -