oj.uz

Submission #1105461

# Submission time Handle Problem Language Result Execution time Memory
1105461 2024-10-26T13:07:32 Z VinhLuu Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 659744 KB 
#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, a[N][N];
ll 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 = 1; j <= n; j ++){
      f[1][i][j] = 0;
      f[0][i][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];
//        cerr << 1 << " " << i << " " << j << " " << f[1][i][j] - a[i][j] << " t\n";

      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 1018 ms 658532 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 1029 ms 659744 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 1039 ms 653204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 1 ms 10576 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 1 ms 8528 KB Output is correct
5 Incorrect 2 ms 8696 KB 1st lines differ - on the 1st token, expected: '8866', found: '7755'
6 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 1 ms 10576 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 1 ms 8528 KB Output is correct
5 Incorrect 2 ms 8696 KB 1st lines differ - on the 1st token, expected: '8866', found: '7755'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 1 ms 10576 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 1 ms 8528 KB Output is correct
5 Incorrect 2 ms 8696 KB 1st lines differ - on the 1st token, expected: '8866', found: '7755'
6 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 653204 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 1018 ms 658532 KB Time limit exceeded
2 Halted 0 ms 0 KB -