結果

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

ソースコード

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){
		if(s.contains(p)) s.erase(p);
		for(auto q=s.lower_bound(p);q!=s.end() && q->second<p.second;q=s.erase(q)){}
	}
	for(pair<int,int> p : s){
		for(auto q=w.lower_bound(p);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);
			mem=0;
		}
		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);
			mem=0;
		}
		else if(*p<*q){
			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-p->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