답안 #625752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625752	2022-08-10T18:33:57 Z	d4xn	메기 농장 (IOI22_fish)	C++17	23 / 100	1000 ms	169668 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 tuple3 tuple<int, int, int>
 
const int N = 1e5+1;
 
int n, m;
vi c[N];
map<int, int> w[N];
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

#	결과	실행 시간	메모리	Grader output
1	Correct	331 ms	69240 KB	Output is correct
2	Correct	397 ms	79008 KB	Output is correct
3	Correct	56 ms	46412 KB	Output is correct
4	Correct	58 ms	46432 KB	Output is correct
5	Execution timed out	1102 ms	169668 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	11988 KB	Output is correct
2	Execution timed out	1099 ms	71276 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	46424 KB	Output is correct
2	Correct	69 ms	46412 KB	Output is correct
3	Correct	180 ms	62992 KB	Output is correct
4	Correct	166 ms	60392 KB	Output is correct
5	Correct	479 ms	81596 KB	Output is correct
6	Correct	463 ms	81672 KB	Output is correct
7	Correct	450 ms	81688 KB	Output is correct
8	Correct	499 ms	81604 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	12048 KB	Output is correct
2	Correct	7 ms	11944 KB	Output is correct
3	Correct	7 ms	11988 KB	Output is correct
4	Correct	6 ms	11988 KB	Output is correct
5	Correct	7 ms	11988 KB	Output is correct
6	Correct	7 ms	11988 KB	Output is correct
7	Correct	7 ms	11988 KB	Output is correct
8	Correct	7 ms	11988 KB	Output is correct
9	Correct	11 ms	12372 KB	Output is correct
10	Correct	63 ms	13900 KB	Output is correct
11	Correct	23 ms	12744 KB	Output is correct
12	Correct	28 ms	13132 KB	Output is correct
13	Correct	7 ms	12164 KB	Output is correct
14	Correct	16 ms	12756 KB	Output is correct

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	12048 KB	Output is correct
2	Correct	7 ms	11944 KB	Output is correct
3	Correct	7 ms	11988 KB	Output is correct
4	Correct	6 ms	11988 KB	Output is correct
5	Correct	7 ms	11988 KB	Output is correct
6	Correct	7 ms	11988 KB	Output is correct
7	Correct	7 ms	11988 KB	Output is correct
8	Correct	7 ms	11988 KB	Output is correct
9	Correct	11 ms	12372 KB	Output is correct
10	Correct	63 ms	13900 KB	Output is correct
11	Correct	23 ms	12744 KB	Output is correct
12	Correct	28 ms	13132 KB	Output is correct
13	Correct	7 ms	12164 KB	Output is correct
14	Correct	16 ms	12756 KB	Output is correct
15	Correct	8 ms	12420 KB	Output is correct
16	Execution timed out	1099 ms	15648 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	12048 KB	Output is correct
2	Correct	7 ms	11944 KB	Output is correct
3	Correct	7 ms	11988 KB	Output is correct
4	Correct	6 ms	11988 KB	Output is correct
5	Correct	7 ms	11988 KB	Output is correct
6	Correct	7 ms	11988 KB	Output is correct
7	Correct	7 ms	11988 KB	Output is correct
8	Correct	7 ms	11988 KB	Output is correct
9	Correct	11 ms	12372 KB	Output is correct
10	Correct	63 ms	13900 KB	Output is correct
11	Correct	23 ms	12744 KB	Output is correct
12	Correct	28 ms	13132 KB	Output is correct
13	Correct	7 ms	12164 KB	Output is correct
14	Correct	16 ms	12756 KB	Output is correct
15	Correct	8 ms	12420 KB	Output is correct
16	Execution timed out	1099 ms	15648 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	46424 KB	Output is correct
2	Correct	69 ms	46412 KB	Output is correct
3	Correct	180 ms	62992 KB	Output is correct
4	Correct	166 ms	60392 KB	Output is correct
5	Correct	479 ms	81596 KB	Output is correct
6	Correct	463 ms	81672 KB	Output is correct
7	Correct	450 ms	81688 KB	Output is correct
8	Correct	499 ms	81604 KB	Output is correct
9	Correct	969 ms	138056 KB	Output is correct
10	Correct	522 ms	69116 KB	Output is correct
11	Execution timed out	1050 ms	126264 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	331 ms	69240 KB	Output is correct
2	Correct	397 ms	79008 KB	Output is correct
3	Correct	56 ms	46412 KB	Output is correct
4	Correct	58 ms	46432 KB	Output is correct
5	Execution timed out	1102 ms	169668 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

답안 #625752

Compilation message