oj.uz

Submission #625752

# Submission time Handle Problem Language Result Execution time Memory
625752 2022-08-10T18:33:57 Z d4xn Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 169668 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 tuple3 tuple<int, int, int>
 
const int N = 1e5+1;
 
int n, m;
vi c[N];
map<int, int> w[N];
map<int, ll> pre[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;
  
  tuple3 t = make_tuple(curr, h1, h2);
  auto it = dp.find(t);
  if (it != dp.end()) return it->second;
  
  dp[t] = mx(curr-1, 0, h1);
  it = dp.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;
 
  for (int i = 0; i < m; i++) {
    w[X[i]][Y[i]] = W[i];
    c[X[i]].push_back(Y[i]);
  }
 
  map<int, int> heights;
  for (int i = 0; i < n; i++) {
    pre[i][-1] = 0;

    sort(c[i].begin(), c[i].end());
    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) {
      if (w[i].count(h)) sum3 += w[i][h];
      pre[i][h] = sum3;
 
      if (i-1 >= 0) {
        if (w[i-1].count(h)) sum2 += w[i-1][h];
        pre[i-1][h] = sum2;
      }
      if (i-2 >= 0) {
        if (w[i-2].count(h)) sum1 += w[i-2][h];
        pre[i-2][h] = sum1;
      }
    }
  }

  return mx(n-1, 0, 0);
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 69240 KB Output is correct
2 Correct 397 ms 79008 KB Output is correct
3 Correct 56 ms 46412 KB Output is correct
4 Correct 58 ms 46432 KB Output is correct
5 Execution timed out 1102 ms 169668 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Execution timed out 1099 ms 71276 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 46424 KB Output is correct
2 Correct 69 ms 46412 KB Output is correct
3 Correct 180 ms 62992 KB Output is correct
4 Correct 166 ms 60392 KB Output is correct
5 Correct 479 ms 81596 KB Output is correct
6 Correct 463 ms 81672 KB Output is correct
7 Correct 450 ms 81688 KB Output is correct
8 Correct 499 ms 81604 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12048 KB Output is correct
2 Correct 7 ms 11944 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 11 ms 12372 KB Output is correct
10 Correct 63 ms 13900 KB Output is correct
11 Correct 23 ms 12744 KB Output is correct
12 Correct 28 ms 13132 KB Output is correct
13 Correct 7 ms 12164 KB Output is correct
14 Correct 16 ms 12756 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12048 KB Output is correct
2 Correct 7 ms 11944 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 11 ms 12372 KB Output is correct
10 Correct 63 ms 13900 KB Output is correct
11 Correct 23 ms 12744 KB Output is correct
12 Correct 28 ms 13132 KB Output is correct
13 Correct 7 ms 12164 KB Output is correct
14 Correct 16 ms 12756 KB Output is correct
15 Correct 8 ms 12420 KB Output is correct
16 Execution timed out 1099 ms 15648 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12048 KB Output is correct
2 Correct 7 ms 11944 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 11 ms 12372 KB Output is correct
10 Correct 63 ms 13900 KB Output is correct
11 Correct 23 ms 12744 KB Output is correct
12 Correct 28 ms 13132 KB Output is correct
13 Correct 7 ms 12164 KB Output is correct
14 Correct 16 ms 12756 KB Output is correct
15 Correct 8 ms 12420 KB Output is correct
16 Execution timed out 1099 ms 15648 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 46424 KB Output is correct
2 Correct 69 ms 46412 KB Output is correct
3 Correct 180 ms 62992 KB Output is correct
4 Correct 166 ms 60392 KB Output is correct
5 Correct 479 ms 81596 KB Output is correct
6 Correct 463 ms 81672 KB Output is correct
7 Correct 450 ms 81688 KB Output is correct
8 Correct 499 ms 81604 KB Output is correct
9 Correct 969 ms 138056 KB Output is correct
10 Correct 522 ms 69116 KB Output is correct
11 Execution timed out 1050 ms 126264 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 69240 KB Output is correct
2 Correct 397 ms 79008 KB Output is correct
3 Correct 56 ms 46412 KB Output is correct
4 Correct 58 ms 46432 KB Output is correct
5 Execution timed out 1102 ms 169668 KB Time limit exceeded
6 Halted 0 ms 0 KB -