oj.uz

Submission #625784

# Submission time Handle Problem Language Result Execution time Memory
625784 2022-08-10T19:09:25 Z d4xn Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 150644 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);
      if (w[0].count(i)) pre0[i] += w[0][i];
      if (w[1].count(i)) pre0[i] += w[1][i];
    }

    ll ans = 0;
    for (int i = 0; i < n; i++) {
      ans = max(ans, pre0[i] + pre1[n-1] - pre1[i]);
      ans = max(ans, pre1[i] + pre0[n-1] - pre0[i]);
    }

    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 44 ms 25064 KB Output is correct
2 Correct 52 ms 27012 KB Output is correct
3 Correct 12 ms 19856 KB Output is correct
4 Correct 13 ms 19796 KB Output is correct
5 Execution timed out 1107 ms 150644 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Incorrect 76 ms 30496 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19844 KB Output is correct
2 Correct 59 ms 52724 KB Output is correct
3 Correct 163 ms 72400 KB Output is correct
4 Correct 108 ms 68512 KB Output is correct
5 Correct 214 ms 94112 KB Output is correct
6 Correct 205 ms 94156 KB Output is correct
7 Correct 210 ms 94136 KB Output is correct
8 Correct 210 ms 94220 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18280 KB Output is correct
2 Correct 11 ms 18308 KB Output is correct
3 Incorrect 11 ms 18260 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18280 KB Output is correct
2 Correct 11 ms 18308 KB Output is correct
3 Incorrect 11 ms 18260 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18280 KB Output is correct
2 Correct 11 ms 18308 KB Output is correct
3 Incorrect 11 ms 18260 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19844 KB Output is correct
2 Correct 59 ms 52724 KB Output is correct
3 Correct 163 ms 72400 KB Output is correct
4 Correct 108 ms 68512 KB Output is correct
5 Correct 214 ms 94112 KB Output is correct
6 Correct 205 ms 94156 KB Output is correct
7 Correct 210 ms 94136 KB Output is correct
8 Correct 210 ms 94220 KB Output is correct
9 Correct 375 ms 137948 KB Output is correct
10 Correct 217 ms 76164 KB Output is correct
11 Correct 449 ms 134092 KB Output is correct
12 Incorrect 10 ms 18260 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
13 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 25064 KB Output is correct
2 Correct 52 ms 27012 KB Output is correct
3 Correct 12 ms 19856 KB Output is correct
4 Correct 13 ms 19796 KB Output is correct
5 Execution timed out 1107 ms 150644 KB Time limit exceeded
6 Halted 0 ms 0 KB -