제출 #1343384

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1343384		jmuzhen	메기 농장 (IOI22_fish)	C++20	3 / 100	51 ms	10332 KiB

fish

#include "fish.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  bool is_sub1=1, is_sub2=1, is_sub3 = 1;
  for (int i = 0; i < M; i++) {
    if (X[i] % 2 != 0) is_sub1 = 0;
    if (X[i] > 1) is_sub2 = 0;
    if (Y[i] != 0) is_sub3 = 0;
  }

  if (is_sub1) {
    long long ans = 0;
    for (int i = 0; i < M; i++) ans += W[i];
    return ans;
  }
  else if (is_sub2) {
    long long ans = 0;
    vector<int> exist_row(N, -1);
    for (int i = 0; i < M; i++) {
      if (exist_row[Y[i]] != -1) {
        if ( W[i] > exist_row[Y[i]]) {
          ans += (W[i] - exist_row[Y[i]]);
        }
      }
      else {
        exist_row[Y[i]] = W[i];
        ans += W[i];
      }
    }
    return ans;
  }
  else if (is_sub3) {
    long long dp[100000+10][2][2]; // {prev built, next built}
    vector<int> w(N, 0);
    for (int i = 0; i < M; i++) {
      w[X[i]] = W[i];
    }

    for (int i = 0; i < N; i++) {
      for (int prevb = 0; prevb <= 1; prevb++) {
        for (int nextb = 0; nextb <= 1; nextb++) {
          // prune
          if (i == 0 && prevb) continue;
          if (i == N-1 && nextb) continue;

          // case1. don't build
          long long case1 = 0;
          {
            if ((prevb || nextb)) {
              // can take this one
              // case1a:take here
              if (i>0) {
                case1 = max(case1, w[i] + max(dp[i-1][0][0], dp[i-1][1][0]));
              }
              else {
                case1 = max(case1, (long long)w[i]);
              }
            }
          }
          // case2. build
          long long case2 = 0;
          {
            if (i > 0) {
              case2 = max(case2, max(dp[i-1][0][1], dp[i-1][1][1]));
            }
          }
        }
      } // end dp

    } // for (N) loop


    return max(dp[N-1][0][0],dp[N-1][1][0]);
  }
}

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
   80 | }
      | ^

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