제출 #997492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997492		MuhammadSaram	수열 (APIO14_sequence)	C++17	0 / 100	180 ms	14344 KiB

sequence

// Time: 12-06-2024 16:32:12
// Problem: B - Split the sequence
// Contest: Virtual Judge - APIO 2014
// URL: https://vjudge.net/contest/633835#problem/B
// Memory Limit: 128 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main()
{
	int n,k,su=0;
	cin>>n>>k;
	int a[n],ans=0,pre[n+1]={};
	for (int i=0;i<n;i++)
	{
		cin>>a[i];
		su+=a[i];
		ans-=a[i]*a[i];
		pre[i+1]=su;
	}
	ans+=su*su;
	ans/=2;
	set<pair<int,int>> se;
	map<int,pair<int,int>> bar;
	for (int i=0;i<n-1;i++)
	{
		se.insert({a[i]*a[i+1],i+1});
		bar[i+1]={i,i+1};
	}
	while (se.size()>k)
	{
		auto te=se.begin();
		auto p=*te;
		se.erase(te);
		ans-=p.first;
		int su=pre[bar[p.second].second+1]-pre[bar[p.second].first];
		auto x=bar.upper_bound(p.second);
		if (x!=bar.end())
		{
			int a=pre[bar[p.second].second+1]-pre[p.second],b=pre[(*x).second.second+1]-pre[(*x).first];
			se.erase({a*b,(*x).first});
			se.insert({su*b,(*x).first});
			bar[(*x).first]={bar[p.second].first,(*x).second.second};
		}
		auto y=bar.lower_bound(p.second);
		if (y!=bar.begin())
		{
			y--;
			int a=pre[(*y).first]-pre[(*y).second.first],b=pre[(*y).second.second+1]-pre[(*y).first];
			se.erase({a*b,(*y).first});
			se.insert({su*a,(*y).first});
			bar[(*y).first]={(*y).second.first,bar[p.second].second};
		}
		bar.erase(p.second);
	}
	cout<<ans<<endl;
	
	return 0;
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:35:18: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   35 |  while (se.size()>k)
      |         ~~~~~~~~~^~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29