oj.uz

Submission #625754

# Submission time Handle Problem Language Result Execution time Memory
625754 2022-08-10T18:35:32 Z d4xn Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 158776 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;
 
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 452 ms 67828 KB Output is correct
2 Correct 575 ms 77312 KB Output is correct
3 Correct 63 ms 44852 KB Output is correct
4 Correct 60 ms 44800 KB Output is correct
5 Execution timed out 1090 ms 158776 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 1098 ms 69868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 44880 KB Output is correct
2 Correct 62 ms 44828 KB Output is correct
3 Correct 189 ms 61608 KB Output is correct
4 Correct 169 ms 58888 KB Output is correct
5 Correct 450 ms 80120 KB Output is correct
6 Correct 441 ms 80016 KB Output is correct
7 Correct 457 ms 80120 KB Output is correct
8 Correct 441 ms 80068 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11976 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Correct 11 ms 12372 KB Output is correct
10 Correct 64 ms 13864 KB Output is correct
11 Correct 24 ms 12792 KB Output is correct
12 Correct 34 ms 13368 KB Output is correct
13 Correct 7 ms 12068 KB Output is correct
14 Correct 18 ms 12756 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11976 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Correct 11 ms 12372 KB Output is correct
10 Correct 64 ms 13864 KB Output is correct
11 Correct 24 ms 12792 KB Output is correct
12 Correct 34 ms 13368 KB Output is correct
13 Correct 7 ms 12068 KB Output is correct
14 Correct 18 ms 12756 KB Output is correct
15 Correct 8 ms 12372 KB Output is correct
16 Execution timed out 1075 ms 16136 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 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 11976 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Correct 11 ms 12372 KB Output is correct
10 Correct 64 ms 13864 KB Output is correct
11 Correct 24 ms 12792 KB Output is correct
12 Correct 34 ms 13368 KB Output is correct
13 Correct 7 ms 12068 KB Output is correct
14 Correct 18 ms 12756 KB Output is correct
15 Correct 8 ms 12372 KB Output is correct
16 Execution timed out 1075 ms 16136 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 44880 KB Output is correct
2 Correct 62 ms 44828 KB Output is correct
3 Correct 189 ms 61608 KB Output is correct
4 Correct 169 ms 58888 KB Output is correct
5 Correct 450 ms 80120 KB Output is correct
6 Correct 441 ms 80016 KB Output is correct
7 Correct 457 ms 80120 KB Output is correct
8 Correct 441 ms 80068 KB Output is correct
9 Correct 968 ms 136524 KB Output is correct
10 Correct 443 ms 68396 KB Output is correct
11 Correct 948 ms 124776 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 6 ms 11988 KB Output is correct
15 Correct 6 ms 11988 KB Output is correct
16 Correct 6 ms 11988 KB Output is correct
17 Correct 6 ms 11988 KB Output is correct
18 Correct 60 ms 44780 KB Output is correct
19 Correct 58 ms 44900 KB Output is correct
20 Correct 64 ms 44780 KB Output is correct
21 Correct 64 ms 44868 KB Output is correct
22 Correct 887 ms 135076 KB Output is correct
23 Execution timed out 1102 ms 144560 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 67828 KB Output is correct
2 Correct 575 ms 77312 KB Output is correct
3 Correct 63 ms 44852 KB Output is correct
4 Correct 60 ms 44800 KB Output is correct
5 Execution timed out 1090 ms 158776 KB Time limit exceeded
6 Halted 0 ms 0 KB -