Submission #1105472

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1105472	2024-10-26T13:18:36 Z	VinhLuu	Catfish Farm (IOI22_fish)	C++17	52 / 100	1000 ms	724412 KB

fish

#include <bits/stdc++.h>
#define ll long long
#include "fish.h"
using namespace std;

const int N = 3e3 + 5;
const ll oo = -1e16;

int n, m;
ll a[N][N], f[3][N][N], g[3][N][N];

void vin(ll &x,ll y){
  x = max(x, y);
}

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 = 1; i <= m; i ++){
    int x = X[i - 1] + 1, y = Y[i - 1] + 1, c = W[i - 1];
    a[x][y] += c;
  }
//  for(int i = 1; i <= n; i ++){
//    for(int j = 1; j <= n; j ++) cerr << a[i][j] << " ";
//    cerr << "\n";
//  }
  for(int i = 0; i <= n; i ++){
    for(int j = 0; j <= n + 1; j ++){
      a[i][j] += (j > 0 ? a[i][j - 1] : 0);
      for(int k = 0; k <= 1; k ++){
        f[k][i][j] = g[k][i][j] = oo;
      }
    }
  }

  f[0][0][0] = f[1][0][0] = 0;
  g[1][0][0] = 0;
  for(int i = 1; i <= n; i ++){
    g[1][0][i] = g[1][0][i - 1];
  }

//  cerr << " g\n";

  ll ans = 0;

  for(int i = 1; i <= n; i ++){
    ll ret = oo;
    for(int j = 0; j <= n; j ++) ret = max({ret, f[0][i - 1][j], f[1][i - 1][j]});
    f[0][i][0] = f[1][i][0] = ret;
    for(int j = 0; j <= n; j ++){
      vin(f[1][i][j], 0);
      vin(f[0][i][j], 0);
      if(j > 0) vin(f[1][i][j], a[i - 1][j] + g[1][i - 1][j - 1]);
      vin(f[0][i][j], g[0][i - 1][j + 1] - a[i][j]);
//      cerr << i << " " << j << " " << f[0][i][j] << " " << f[1][i][j] << " h\n";
      vin(ans, max(f[1][i][j], f[0][i][j]));
    }

    for(int j = 0; j <= n; j ++){
      g[1][i][j] = f[1][i][j] - a[i][j];
      if(j > 0) vin(g[1][i][j], g[1][i][j - 1]);
//      cerr << "      " << 1 << " " << i << " " << j << " " << g[1][i][j] << " uuu\n";
    }
    for(int j = n; j >= 0; j --){
      g[0][i][j] = max(f[0][i][j], f[1][i][j]) + a[i + 1][j];
      if(j < n) vin(g[0][i][j], g[0][i][j + 1]);
//      cerr << "     " << 0 << " " << i << " " << j << " " << g[0][i][j] <<" ooo\n";
    }
  }

  return ans;
}

//#define LOCAL

#ifdef LOCAL

int main() {

  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  int _N, M;
  assert(2 == scanf("%d %d", &_N, &M));

  std::vector<int> X(M), Y(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
  }

  long long result = max_weights(_N, M, X, Y, W);
  printf("%lld\n", result);
  return 0;
}

/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

#endif // LOCAL

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1068 ms	724412 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8528 KB	Output is correct
2	Execution timed out	1140 ms	710436 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1114 ms	720652 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8528 KB	Output is correct
2	Correct	2 ms	10692 KB	Output is correct
3	Correct	1 ms	8528 KB	Output is correct
4	Correct	1 ms	8528 KB	Output is correct
5	Correct	1 ms	8528 KB	Output is correct
6	Correct	2 ms	8528 KB	Output is correct
7	Correct	1 ms	8528 KB	Output is correct
8	Correct	1 ms	8528 KB	Output is correct
9	Correct	3 ms	26960 KB	Output is correct
10	Correct	6 ms	45696 KB	Output is correct
11	Correct	4 ms	27132 KB	Output is correct
12	Correct	7 ms	45648 KB	Output is correct
13	Correct	3 ms	18768 KB	Output is correct
14	Correct	6 ms	45648 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8528 KB	Output is correct
2	Correct	2 ms	10692 KB	Output is correct
3	Correct	1 ms	8528 KB	Output is correct
4	Correct	1 ms	8528 KB	Output is correct
5	Correct	1 ms	8528 KB	Output is correct
6	Correct	2 ms	8528 KB	Output is correct
7	Correct	1 ms	8528 KB	Output is correct
8	Correct	1 ms	8528 KB	Output is correct
9	Correct	3 ms	26960 KB	Output is correct
10	Correct	6 ms	45696 KB	Output is correct
11	Correct	4 ms	27132 KB	Output is correct
12	Correct	7 ms	45648 KB	Output is correct
13	Correct	3 ms	18768 KB	Output is correct
14	Correct	6 ms	45648 KB	Output is correct
15	Correct	6 ms	45648 KB	Output is correct
16	Correct	4 ms	19024 KB	Output is correct
17	Correct	16 ms	47440 KB	Output is correct
18	Correct	15 ms	45392 KB	Output is correct
19	Correct	15 ms	47440 KB	Output is correct
20	Correct	16 ms	47440 KB	Output is correct
21	Correct	16 ms	47288 KB	Output is correct
22	Correct	25 ms	49224 KB	Output is correct
23	Correct	8 ms	45904 KB	Output is correct
24	Correct	13 ms	46672 KB	Output is correct
25	Correct	7 ms	45544 KB	Output is correct
26	Correct	8 ms	45904 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8528 KB	Output is correct
2	Correct	2 ms	10692 KB	Output is correct
3	Correct	1 ms	8528 KB	Output is correct
4	Correct	1 ms	8528 KB	Output is correct
5	Correct	1 ms	8528 KB	Output is correct
6	Correct	2 ms	8528 KB	Output is correct
7	Correct	1 ms	8528 KB	Output is correct
8	Correct	1 ms	8528 KB	Output is correct
9	Correct	3 ms	26960 KB	Output is correct
10	Correct	6 ms	45696 KB	Output is correct
11	Correct	4 ms	27132 KB	Output is correct
12	Correct	7 ms	45648 KB	Output is correct
13	Correct	3 ms	18768 KB	Output is correct
14	Correct	6 ms	45648 KB	Output is correct
15	Correct	6 ms	45648 KB	Output is correct
16	Correct	4 ms	19024 KB	Output is correct
17	Correct	16 ms	47440 KB	Output is correct
18	Correct	15 ms	45392 KB	Output is correct
19	Correct	15 ms	47440 KB	Output is correct
20	Correct	16 ms	47440 KB	Output is correct
21	Correct	16 ms	47288 KB	Output is correct
22	Correct	25 ms	49224 KB	Output is correct
23	Correct	8 ms	45904 KB	Output is correct
24	Correct	13 ms	46672 KB	Output is correct
25	Correct	7 ms	45544 KB	Output is correct
26	Correct	8 ms	45904 KB	Output is correct
27	Correct	275 ms	355420 KB	Output is correct
28	Correct	66 ms	102728 KB	Output is correct
29	Correct	330 ms	367856 KB	Output is correct
30	Correct	350 ms	367944 KB	Output is correct
31	Correct	302 ms	367944 KB	Output is correct
32	Correct	63 ms	84424 KB	Output is correct
33	Correct	308 ms	367988 KB	Output is correct
34	Correct	285 ms	367856 KB	Output is correct
35	Correct	250 ms	360012 KB	Output is correct
36	Correct	285 ms	367688 KB	Output is correct

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1114 ms	720652 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1068 ms	724412 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #1105472

Compilation message