oj.uz

Submission #625826

# Submission time Handle Problem Language Result Execution time Memory
625826 2022-08-10T20:22:30 Z d4xn Catfish Farm (IOI22_fish) C++17
18 / 100
 344 ms 139580 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 (min(h1, h2) > 0) return dp[curr][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;
 
  ll sum = 0;
  bool odd = 0;
  int mxX = 0;
  for (int i = 0; i < m; i++) {
    sum += W[i];
    if (X[i]%2) odd = 1;
    mxX = max(mxX, X[i]);

    w[X[i]][Y[i]] = W[i];
    c[X[i]].push_back(Y[i]);
  }
 
  if (!odd) return sum;
  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;
    }

    if (n == 2) return max(pre0[n-1], pre1[n-1]);

    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 >= 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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 23632 KB Output is correct
2 Correct 48 ms 25628 KB Output is correct
3 Correct 10 ms 18212 KB Output is correct
4 Correct 11 ms 18248 KB Output is correct
5 Correct 153 ms 40352 KB Output is correct
6 Correct 269 ms 42572 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18224 KB Output is correct
2 Correct 76 ms 30464 KB Output is correct
3 Correct 95 ms 34300 KB Output is correct
4 Correct 48 ms 23608 KB Output is correct
5 Correct 50 ms 25644 KB Output is correct
6 Correct 12 ms 18272 KB Output is correct
7 Correct 11 ms 18240 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 11 ms 18260 KB Output is correct
10 Correct 10 ms 18260 KB Output is correct
11 Correct 10 ms 18212 KB Output is correct
12 Correct 41 ms 25164 KB Output is correct
13 Correct 52 ms 27008 KB Output is correct
14 Correct 42 ms 25084 KB Output is correct
15 Correct 48 ms 26480 KB Output is correct
16 Correct 43 ms 25084 KB Output is correct
17 Correct 48 ms 26360 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18244 KB Output is correct
2 Correct 57 ms 54220 KB Output is correct
3 Correct 149 ms 73912 KB Output is correct
4 Correct 109 ms 69992 KB Output is correct
5 Correct 214 ms 95772 KB Output is correct
6 Correct 225 ms 95764 KB Output is correct
7 Correct 232 ms 95692 KB Output is correct
8 Correct 215 ms 95864 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 18260 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 18260 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 18260 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18244 KB Output is correct
2 Correct 57 ms 54220 KB Output is correct
3 Correct 149 ms 73912 KB Output is correct
4 Correct 109 ms 69992 KB Output is correct
5 Correct 214 ms 95772 KB Output is correct
6 Correct 225 ms 95764 KB Output is correct
7 Correct 232 ms 95692 KB Output is correct
8 Correct 215 ms 95864 KB Output is correct
9 Incorrect 344 ms 139580 KB 1st lines differ - on the 1st token, expected: '99999', found: '74999'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 23632 KB Output is correct
2 Correct 48 ms 25628 KB Output is correct
3 Correct 10 ms 18212 KB Output is correct
4 Correct 11 ms 18248 KB Output is correct
5 Correct 153 ms 40352 KB Output is correct
6 Correct 269 ms 42572 KB Output is correct
7 Correct 11 ms 18224 KB Output is correct
8 Correct 76 ms 30464 KB Output is correct
9 Correct 95 ms 34300 KB Output is correct
10 Correct 48 ms 23608 KB Output is correct
11 Correct 50 ms 25644 KB Output is correct
12 Correct 12 ms 18272 KB Output is correct
13 Correct 11 ms 18240 KB Output is correct
14 Correct 11 ms 18260 KB Output is correct
15 Correct 11 ms 18260 KB Output is correct
16 Correct 10 ms 18260 KB Output is correct
17 Correct 10 ms 18212 KB Output is correct
18 Correct 41 ms 25164 KB Output is correct
19 Correct 52 ms 27008 KB Output is correct
20 Correct 42 ms 25084 KB Output is correct
21 Correct 48 ms 26480 KB Output is correct
22 Correct 43 ms 25084 KB Output is correct
23 Correct 48 ms 26360 KB Output is correct
24 Correct 11 ms 18244 KB Output is correct
25 Correct 57 ms 54220 KB Output is correct
26 Correct 149 ms 73912 KB Output is correct
27 Correct 109 ms 69992 KB Output is correct
28 Correct 214 ms 95772 KB Output is correct
29 Correct 225 ms 95764 KB Output is correct
30 Correct 232 ms 95692 KB Output is correct
31 Correct 215 ms 95864 KB Output is correct
32 Incorrect 10 ms 18260 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
33 Halted 0 ms 0 KB -