結果

問題 No.3407 Birds-of-Paradise' Christmas Live
コンテスト
ユーザー hos.lyric
提出日時 2025-12-19 00:38:16
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,875 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,329 ms
コンパイル使用メモリ 130,752 KB
実行使用メモリ 24,912 KB
最終ジャッジ日時 2025-12-19 00:38:23
合計ジャッジ時間 5,876 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:58:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |         scanf("%lld", &A[i][j]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


/*
  problem
    given two 01 seqs (RLE)
    choose intervals
    - only 1
    - disjoint
*/

constexpr Int INF = 1001001001001001001LL;

int N[2];
vector<Int> A[2];

int main() {
  for (; ; ) {
    for (int i = 0; i < 2; ++i) {
      if (!~scanf("%d", &N[i])) return 0;
      A[i].resize(N[i]);
      for (int j = 0; j < N[i]; ++j) {
        scanf("%lld", &A[i][j]);
      }
    }
    
    vector<Int> xs{0};
    vector<pair<Int, Int>> pss[2];
    for (int i = 0; i < 2; ++i) {
      Int x = 0;
      for (int j = 0; j < N[i]; ++j) {
        if (!(j & 1)) pss[i].emplace_back(x, x + A[i][j]);
        x += A[i][j];
        xs.push_back(x);
      }
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    const int xsLen = xs.size();
    
    vector<int> lss[2];
    for (int i = 0; i < 2; ++i) {
      vector<int> can(xsLen, 0);
      for (const auto &p : pss[i]) {
        const int l = lower_bound(xs.begin(), xs.end(), p.first ) - xs.begin();
        const int r = lower_bound(xs.begin(), xs.end(), p.second) - xs.begin();
        for (int k = l; k < r; ++k) can[k] = 1;
      }
      lss[i].assign(xsLen, 0);
      for (int k = 1; k < xsLen; ++k) lss[i][k] = can[k - 1] ? lss[i][k - 1] : k;
    }
// cerr<<"xs = "<<xs<<", lss = ";pv(lss,lss+2);
    
    vector<Int> dp(xsLen, -INF);
    dp[0] = 0;
    deque<int> que[2];
    for (int r = 0; r < xsLen; ++r) {
      if (r) chmax(dp[r], dp[r - 1]);
      for (int i = 0; i < 2; ++i) {
        auto eval = [&](int l) -> Int {
          return dp[l] + xs[l]*xs[l] - 2*xs[l]*xs[r];
        };
        for (; que[i].size() >= 1 && que[i][0] < lss[i][r]; que[i].pop_front()) {}
        for (; que[i].size() >= 2 && eval(que[i][0]) <= eval(que[i][1]); que[i].pop_front()) {}
        if (que[i].size() >= 1) chmax(dp[r], eval(que[i][0]) + (Int)xs[r]*xs[r]);
      }
      for (int i = 0; i < 2; ++i) {
        for (; que[i].size() >= 2; ) {
          const int l2 = que[i].end()[-2];
          const int l1 = que[i].end()[-1];
          // a - b x
          const Int a2 = dp[l2] + xs[l2]*xs[l2], b2 = 2*xs[l2];
          const Int a1 = dp[l1] + xs[l1]*xs[l1], b1 = 2*xs[l1];
          const Int a0 = dp[r ] + xs[r ]*xs[r ], b0 = 2*xs[r ];
          // (a1-a2)/(b1-b2) >= (a0-a1)/(b0-b1)
          if ((__int128)(a1 - a2) * (b0 - b0) >= (__int128)(a0 - a1) * (b1 - b2)) {
            que[i].pop_back();
          } else {
            break;
          }
        }
        que[i].push_back(r);
      }
    }
// cerr<<"dp = "<<dp<<endl;
    
    const Int ans = *max_element(dp.begin(), dp.end());
    printf("%lld\n", ans);
  }
  return 0;
}
0