제출 #1334440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1334440		SmuggingSpun	Bitaro the Brave 2 (JOI25_ho_t2)	C++20	100 / 100	81 ms	16088 KiB

Main

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
const int INF = 1e9 + 36;
const int lim = 5e5 + 5;
int n, a[lim], b[lim];
namespace sub12{
  void solve(){
    int ans = INF;
    for(int i = 1; i <= n; i++){
      for(int low = 0, high = ans; low <= high; ){
        int mid = (low + high) >> 1, x = mid;
        for(int j = i; j <= n; x = min(INF, x + b[j++])){
          if(x < a[j]){
            x = -1;
            break;
          }
        }
        if(x != -1){
          for(int j = 1; j < i; x = min(INF, x + b[j++])){
            if(x < a[j]){
              x = -1;
              break;
            }
          }
        }
        if(x != -1){
          high = (ans = mid) - 1;
        }
        else{
          low = mid + 1;
        }
      }
    }
    cout << ans;
  }
}
namespace sub345{
  const ll LINF = 1e18;
  ll fb[lim], sfd_min[lim], pfd_max[lim];
  void solve(){
    pfd_max[fb[0] = 0] = -(sfd_min[n + 1] = LINF);
    for(int i = 1; i <= n; i++){
      fb[i] = fb[i - 1] + b[i];
      pfd_max[i] = max(pfd_max[i - 1], a[i] - fb[i - 1]);
    }
    for(int i = n; i > 0; i--){
      sfd_min[i] = min(sfd_min[i + 1], fb[i - 1] - a[i]);
    }
    int ans = INF;
    for(int i = 1; i <= n; i++){
      for(int low = a[i], high = ans - 1; low <= high; ){
        int mid = (low + high) >> 1;
        if(fb[i - 1] - mid <= sfd_min[i] && mid + fb[n] - fb[i - 1] >= pfd_max[i]){
          high = (ans = mid) - 1;
        }
        else{
          low = mid + 1;
        }
      }
    }
    cout << ans;
  }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    cin >> b[i];
  }
  if(n <= 2000){
    sub12::solve();
  }
  else{
    sub345::solve();
  }
}

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

Main.cpp: In function 'int main()':
Main.cpp:69:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 10 / 10
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 22 / 22
• Subtask 6: 28 / 28