oj.uz

Submission #892601

# Submission time Handle Problem Language Result Execution time Memory
892601 2023-12-25T15:07:00 Z Trisanu_Das Catfish Farm (IOI22_fish) C++17
0 / 100
 45 ms 12580 KB 
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
 
long long f_pref[305][305], dp1[305][305], dp2[305][305], dp_pref[305][305], dp_suff[305][305];
 
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
  for(int i = 0; i < M; i++) f_pref[X[i]][Y[i] + 1] = W[i];
  for(int i = 1; i < N; i++) for(int j = 0; j <= N; j++) f_pref[i][j] += f_pref[i][j - 1];
  for(int l = 1; l < N; l++){
    for(int i = 0; i <= N; i++){
      for(int j = 0; j <= N; j++){
        if(i <= j) dp1[i][j] = dp_pref[j][N] + f_pref[l][j] - f_pref[l][i];
        else{
          dp1[i][j] = max(dp_pref[j][j] + f_pref[l - 1][i] - f_pref[l - 1][j], dp_suff[j][i]);
          if(!j) for(int k = j; k < i; k++) dp1[i][j] = max(dp1[i][j], dp_suff[j][k] + f_pref[l - 1][i] - f_pref[l - 1][k]);
        }
      }
    }
    swap(dp1, dp2);
    memset(dp1, 0, sizeof(dp1));
    memcpy(dp_pref, dp2, sizeof(dp2));
    memcpy(dp_suff, dp2, sizeof(dp2));
    for(int i = 0; i <= N; i++) for(int j = 1; j <= N; j++) dp_pref[i][j] = max(dp_pref[i][j], dp_pref[i][j - 1]);
    for(int i = 0; i <= N; i++) for(int j = N; j >= 0; j--) dp_suff[i][j] = max(dp_suff[i][j + 1], dp_suff[i][j]);
  }
  long long ans = 0;
  for(int i = 0; i <= N; i++) for(int j = 0; j <= N; j++) ans = max(ans, dp2[i][j]);
  return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 7252 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Runtime error 45 ms 12580 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3260 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3332 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Incorrect 38 ms 3676 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '326664473535'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3260 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3332 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Incorrect 38 ms 3676 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '326664473535'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3260 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3332 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Incorrect 38 ms 3676 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '326664473535'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 7252 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -