제출 #1125900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125900		ntdaccode	메기 농장 (IOI22_fish)	C++20	52 / 100	1104 ms	361188 KiB

fish

#include<bits/stdc++.h>
#include <vector>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back


using namespace std;

typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;

const int M = 1e6 + 10;
const int N = 3e3 + 10;
const int mod = 1e9 + 7;

int n, m;
long long D[N][N], f[2][N][N];
long long tmp[2][N], mx[2][N][N];

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++) {
    X[i]++;
    Y[i]++;
    D[X[i]][Y[i]] = 1ll * W[i];
  }
    memset(f,-61,sizeof(f));
  for(int i = 0;i <= n; i++) f[0][1][i] = f[1][1][i] = 0;

  for(int i = 2;i <= n; i++) {
    //
    long long cur = 0;
    for(int j = 0;j <= n; j++) {
      cur += D[i][j];
      tmp[0][j] = f[0][i - 1][j] + cur;
      tmp[1][j] = f[1][i - 1][j] + cur;
    }
    for(int j = n; j >= 0; j--) {
      for(int e = 0;e <= 1; e++) {
        mx[e][i][j] = max(mx[e][i][j + 1], tmp[e][j]);
      }
    }
    cur = 0;
    for(int j = 0;j <= n; j++) {
        cur -= D[i][j];
        f[1][i][j] = max(mx[0][i][j], mx[1][i][j]) + cur;
    }
    //
    cur = 0;
    for(int j = n; j >= 0; j--) {
      tmp[0][j] = f[0][i - 1][j] + cur;
      tmp[1][j] = f[1][i - 1][j];
      cur += D[i - 1][j];
    }
    mx[0][i][0] = tmp[0][0];
    mx[1][i][0] = tmp[1][0];
    for(int j = 1;j <= n; j++) {
      for(int e = 0;e <= 1; e++) mx[e][i][j] = max(mx[e][i][j - 1], tmp[e][j]);
    }
    cur = 0;
    for(int j = n; j >= 0; j--) {
      f[0][i][j] = max({mx[0][i][j] + cur,mx[1][i][j]});
      cur -= D[i - 1][j];
    }

  }
  long long kq = 0;
  for(int i = 0;i <= n; i++) kq = max({kq, f[0][n][i], f[1][n][i]});
  return kq;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16