oj.uz

Submission #625788

# Submission time Handle Problem Language Result Execution time Memory
625788 2022-08-10T19:14:57 Z d4xn Catfish Farm (IOI22_fish) C++17
43 / 100
 1000 ms 231728 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);

      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;
    }

    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 42 ms 25052 KB Output is correct
2 Correct 50 ms 27012 KB Output is correct
3 Correct 13 ms 19860 KB Output is correct
4 Correct 13 ms 19796 KB Output is correct
5 Execution timed out 1097 ms 150704 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18264 KB Output is correct
2 Correct 77 ms 30456 KB Output is correct
3 Correct 94 ms 34300 KB Output is correct
4 Correct 45 ms 25096 KB Output is correct
5 Correct 49 ms 27064 KB Output is correct
6 Correct 10 ms 18236 KB Output is correct
7 Correct 10 ms 18260 KB Output is correct
8 Correct 12 ms 18260 KB Output is correct
9 Correct 11 ms 18260 KB Output is correct
10 Correct 14 ms 19748 KB Output is correct
11 Correct 14 ms 19796 KB Output is correct
12 Correct 41 ms 25044 KB Output is correct
13 Correct 50 ms 27048 KB Output is correct
14 Correct 42 ms 25084 KB Output is correct
15 Correct 48 ms 26516 KB Output is correct
16 Correct 42 ms 25124 KB Output is correct
17 Correct 45 ms 26484 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19800 KB Output is correct
2 Correct 46 ms 52708 KB Output is correct
3 Correct 125 ms 72524 KB Output is correct
4 Correct 100 ms 68456 KB Output is correct
5 Correct 200 ms 94100 KB Output is correct
6 Correct 203 ms 94228 KB Output is correct
7 Correct 244 ms 94200 KB Output is correct
8 Correct 208 ms 94108 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 12 ms 18260 KB Output is correct
3 Correct 10 ms 18240 KB Output is correct
4 Correct 12 ms 18388 KB Output is correct
5 Correct 10 ms 18176 KB Output is correct
6 Correct 11 ms 18236 KB Output is correct
7 Correct 10 ms 18260 KB Output is correct
8 Correct 14 ms 18260 KB Output is correct
9 Correct 13 ms 18632 KB Output is correct
10 Correct 35 ms 20120 KB Output is correct
11 Correct 18 ms 19028 KB Output is correct
12 Correct 23 ms 19412 KB Output is correct
13 Correct 12 ms 18388 KB Output is correct
14 Correct 15 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 12 ms 18260 KB Output is correct
3 Correct 10 ms 18240 KB Output is correct
4 Correct 12 ms 18388 KB Output is correct
5 Correct 10 ms 18176 KB Output is correct
6 Correct 11 ms 18236 KB Output is correct
7 Correct 10 ms 18260 KB Output is correct
8 Correct 14 ms 18260 KB Output is correct
9 Correct 13 ms 18632 KB Output is correct
10 Correct 35 ms 20120 KB Output is correct
11 Correct 18 ms 19028 KB Output is correct
12 Correct 23 ms 19412 KB Output is correct
13 Correct 12 ms 18388 KB Output is correct
14 Correct 15 ms 19028 KB Output is correct
15 Correct 13 ms 18644 KB Output is correct
16 Execution timed out 1099 ms 26596 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 12 ms 18260 KB Output is correct
3 Correct 10 ms 18240 KB Output is correct
4 Correct 12 ms 18388 KB Output is correct
5 Correct 10 ms 18176 KB Output is correct
6 Correct 11 ms 18236 KB Output is correct
7 Correct 10 ms 18260 KB Output is correct
8 Correct 14 ms 18260 KB Output is correct
9 Correct 13 ms 18632 KB Output is correct
10 Correct 35 ms 20120 KB Output is correct
11 Correct 18 ms 19028 KB Output is correct
12 Correct 23 ms 19412 KB Output is correct
13 Correct 12 ms 18388 KB Output is correct
14 Correct 15 ms 19028 KB Output is correct
15 Correct 13 ms 18644 KB Output is correct
16 Execution timed out 1099 ms 26596 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19800 KB Output is correct
2 Correct 46 ms 52708 KB Output is correct
3 Correct 125 ms 72524 KB Output is correct
4 Correct 100 ms 68456 KB Output is correct
5 Correct 200 ms 94100 KB Output is correct
6 Correct 203 ms 94228 KB Output is correct
7 Correct 244 ms 94200 KB Output is correct
8 Correct 208 ms 94108 KB Output is correct
9 Correct 325 ms 138012 KB Output is correct
10 Correct 221 ms 76140 KB Output is correct
11 Correct 436 ms 134136 KB Output is correct
12 Correct 10 ms 18260 KB Output is correct
13 Correct 12 ms 18260 KB Output is correct
14 Correct 11 ms 18260 KB Output is correct
15 Correct 10 ms 18260 KB Output is correct
16 Correct 11 ms 18260 KB Output is correct
17 Correct 11 ms 18212 KB Output is correct
18 Correct 14 ms 19864 KB Output is correct
19 Correct 13 ms 19868 KB Output is correct
20 Correct 59 ms 52640 KB Output is correct
21 Correct 52 ms 52684 KB Output is correct
22 Correct 450 ms 133012 KB Output is correct
23 Correct 926 ms 210048 KB Output is correct
24 Correct 956 ms 231728 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 25052 KB Output is correct
2 Correct 50 ms 27012 KB Output is correct
3 Correct 13 ms 19860 KB Output is correct
4 Correct 13 ms 19796 KB Output is correct
5 Execution timed out 1097 ms 150704 KB Time limit exceeded
6 Halted 0 ms 0 KB -