oj.uz

Submission #625755

# Submission time Handle Problem Language Result Execution time Memory
625755 2022-08-10T18:36:16 Z d4xn Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 147524 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];
unordered_map<int, int> w[N];
unordered_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 284 ms 65964 KB Output is correct
2 Correct 325 ms 76536 KB Output is correct
3 Correct 68 ms 49536 KB Output is correct
4 Correct 69 ms 49608 KB Output is correct
5 Execution timed out 1099 ms 147524 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13612 KB Output is correct
2 Execution timed out 1087 ms 67048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 49516 KB Output is correct
2 Correct 67 ms 49468 KB Output is correct
3 Correct 230 ms 69148 KB Output is correct
4 Correct 218 ms 65416 KB Output is correct
5 Correct 507 ms 90972 KB Output is correct
6 Correct 505 ms 91084 KB Output is correct
7 Correct 533 ms 91032 KB Output is correct
8 Correct 546 ms 91072 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13524 KB Output is correct
2 Correct 11 ms 13524 KB Output is correct
3 Correct 10 ms 13524 KB Output is correct
4 Correct 8 ms 13524 KB Output is correct
5 Correct 11 ms 13524 KB Output is correct
6 Correct 9 ms 13616 KB Output is correct
7 Correct 10 ms 13612 KB Output is correct
8 Correct 11 ms 13612 KB Output is correct
9 Correct 16 ms 13920 KB Output is correct
10 Correct 65 ms 15324 KB Output is correct
11 Correct 23 ms 14292 KB Output is correct
12 Correct 31 ms 14672 KB Output is correct
13 Correct 12 ms 13732 KB Output is correct
14 Correct 18 ms 14292 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13524 KB Output is correct
2 Correct 11 ms 13524 KB Output is correct
3 Correct 10 ms 13524 KB Output is correct
4 Correct 8 ms 13524 KB Output is correct
5 Correct 11 ms 13524 KB Output is correct
6 Correct 9 ms 13616 KB Output is correct
7 Correct 10 ms 13612 KB Output is correct
8 Correct 11 ms 13612 KB Output is correct
9 Correct 16 ms 13920 KB Output is correct
10 Correct 65 ms 15324 KB Output is correct
11 Correct 23 ms 14292 KB Output is correct
12 Correct 31 ms 14672 KB Output is correct
13 Correct 12 ms 13732 KB Output is correct
14 Correct 18 ms 14292 KB Output is correct
15 Correct 11 ms 13908 KB Output is correct
16 Execution timed out 1091 ms 18880 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13524 KB Output is correct
2 Correct 11 ms 13524 KB Output is correct
3 Correct 10 ms 13524 KB Output is correct
4 Correct 8 ms 13524 KB Output is correct
5 Correct 11 ms 13524 KB Output is correct
6 Correct 9 ms 13616 KB Output is correct
7 Correct 10 ms 13612 KB Output is correct
8 Correct 11 ms 13612 KB Output is correct
9 Correct 16 ms 13920 KB Output is correct
10 Correct 65 ms 15324 KB Output is correct
11 Correct 23 ms 14292 KB Output is correct
12 Correct 31 ms 14672 KB Output is correct
13 Correct 12 ms 13732 KB Output is correct
14 Correct 18 ms 14292 KB Output is correct
15 Correct 11 ms 13908 KB Output is correct
16 Execution timed out 1091 ms 18880 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 49516 KB Output is correct
2 Correct 67 ms 49468 KB Output is correct
3 Correct 230 ms 69148 KB Output is correct
4 Correct 218 ms 65416 KB Output is correct
5 Correct 507 ms 90972 KB Output is correct
6 Correct 505 ms 91084 KB Output is correct
7 Correct 533 ms 91032 KB Output is correct
8 Correct 546 ms 91072 KB Output is correct
9 Execution timed out 1027 ms 134868 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 65964 KB Output is correct
2 Correct 325 ms 76536 KB Output is correct
3 Correct 68 ms 49536 KB Output is correct
4 Correct 69 ms 49608 KB Output is correct
5 Execution timed out 1099 ms 147524 KB Time limit exceeded
6 Halted 0 ms 0 KB -