oj.uz

Submission #997492

# Submission time Handle Problem Language Result Execution time Memory
997492 2024-06-12T11:38:50 Z MuhammadSaram Split the sequence (APIO14_sequence) C++17
0 / 100
 180 ms 14344 KB 
// 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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 1832 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 180 ms 14344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -