oj.uz

답안 #1105472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1105472 2024-10-26T13:18:36 Z VinhLuu 메기 농장 (IOI22_fish) C++17
52 / 100
 1000 ms 724412 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;
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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1068 ms 724412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1114 ms 720652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1068 ms 724412 KB Time limit exceeded
2 Halted 0 ms 0 KB -