結果

問題 No.3407 Birds-of-Paradise' Christmas Live
コンテスト
ユーザー highlighter
提出日時 2025-12-13 16:35:46
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,705 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,818 ms
コンパイル使用メモリ 283,872 KB
実行使用メモリ 15,360 KB
最終ジャッジ日時 2025-12-13 23:30:19
合計ジャッジ時間 6,920 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int main(){
	int n,m;
	cin >> n;
	set<pair<int,int>> w;
	for(int i=0,sum_w=0,W;i<n;i++){
		cin >> W;
		if(i%2==0 && W) w.emplace(sum_w,sum_w+W);
		sum_w+=W;
	}
	cin >> m;
	set<pair<int,int>> s;
	for(int i=0,sum_s=0,S;i<m;i++){
		cin >> S;
		if(i%2==0 && S) s.emplace(sum_s,sum_s+S);
		sum_s+=S;
	}
	for(pair<int,int> p : w){
		for(auto q=s.lower_bound(make_pair(p.first,p.first));q!=s.end() && q->second<=p.second;q=s.erase(q)){}
	}
	for(pair<int,int> p : s){
		for(auto q=w.lower_bound(make_pair(p.first,p.first));q!=w.end() && q->second<=p.second;q=w.erase(q)){}
	}
	long long ans=0,mem=0;
	pair<long long,long long> dp=make_pair(0,0);
	for(auto p=w.begin(),q=s.begin();p!=w.end() || q!=s.end();){
		if(p==w.end() || (q!=s.end() && q->second<=p->first)){
			long long len=q->second-q->first;
			ans+=max(dp.first+len*len,dp.second+(len-mem)*(len-mem));
			dp=make_pair(0,0);
			q=next(q);
		}
		else if(q==s.end() || (p!=w.end() && p->second<=q->first)){
			long long len=p->second-p->first;
			ans+=max(dp.first+len*len,dp.second+(len-mem)*(len-mem));
			dp=make_pair(0,0);
			p=next(p);
		}
		else if(p->first<q->first){
			long long len=p->second-q->first,len_p=p->second-p->first;
			dp=make_pair(max(dp.first+(len_p-len)*(len_p-len),dp.second+(len_p-mem-len)*(len_p-mem-len)),max(dp.first+len_p*len_p,dp.second+(len_p-mem)*(len_p-mem)));
			p=next(p);
			mem=len;
		}
		else{
			long long len=q->second-q->first,len_q=q->second-q->first;
			dp=make_pair(max(dp.first+(len_q-len)*(len_q-len),dp.second+(len_q-mem-len)*(len_q-mem-len)),max(dp.first+len_q*len_q,dp.second+(len_q-mem)*(len_q-mem)));
			q=next(q);
			mem=len;
		}
	}
	cout << ans << '\n';
}
0