Submission #625785

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
625785	2022-08-10T19:10:09 Z	d4xn	Catfish Farm (IOI22_fish)	C++17	9 / 100	1000 ms	150588 KB

fish

#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)) pre1[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	49 ms	25044 KB	Output is correct
2	Correct	54 ms	27000 KB	Output is correct
3	Correct	13 ms	19796 KB	Output is correct
4	Correct	12 ms	19796 KB	Output is correct
5	Execution timed out	1081 ms	150588 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	18260 KB	Output is correct
2	Correct	83 ms	30472 KB	Output is correct
3	Incorrect	101 ms	34328 KB	1st lines differ - on the 1st token, expected: '50032678213482', found: '50049263855627'
4	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	19800 KB	Output is correct
2	Correct	56 ms	52684 KB	Output is correct
3	Correct	135 ms	72436 KB	Output is correct
4	Correct	108 ms	68540 KB	Output is correct
5	Correct	214 ms	94156 KB	Output is correct
6	Correct	239 ms	94256 KB	Output is correct
7	Correct	219 ms	94236 KB	Output is correct
8	Correct	219 ms	94152 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	18260 KB	Output is correct
2	Correct	11 ms	18248 KB	Output is correct
3	Incorrect	13 ms	18296 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	10 ms	18260 KB	Output is correct
2	Correct	11 ms	18248 KB	Output is correct
3	Incorrect	13 ms	18296 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	10 ms	18260 KB	Output is correct
2	Correct	11 ms	18248 KB	Output is correct
3	Incorrect	13 ms	18296 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	14 ms	19800 KB	Output is correct
2	Correct	56 ms	52684 KB	Output is correct
3	Correct	135 ms	72436 KB	Output is correct
4	Correct	108 ms	68540 KB	Output is correct
5	Correct	214 ms	94156 KB	Output is correct
6	Correct	239 ms	94256 KB	Output is correct
7	Correct	219 ms	94236 KB	Output is correct
8	Correct	219 ms	94152 KB	Output is correct
9	Correct	364 ms	137940 KB	Output is correct
10	Correct	240 ms	76112 KB	Output is correct
11	Correct	519 ms	134068 KB	Output is correct
12	Incorrect	11 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	49 ms	25044 KB	Output is correct
2	Correct	54 ms	27000 KB	Output is correct
3	Correct	13 ms	19796 KB	Output is correct
4	Correct	12 ms	19796 KB	Output is correct
5	Execution timed out	1081 ms	150588 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Submission #625785

Compilation message