Submission #347272

#	Time	Username	Problem	Language	Result	Execution time	Memory
347272		CaroLinda	Candies (JOI18_candies)	C++14	100 / 100	712 ms	27584 KiB

candies

#include <bits/stdc++.h>

#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() ) 

const int MAXN = 2e5+10 ;

using namespace std ;

int N ;
ll valCandies[MAXN] ;
set< pair<ll,int> > candies ;
set<int> orderCandies ;

int main()
{

	scanf("%d", &N ) ;
	for(int i = 1 ; i <= N ; i++ )
	{	
		scanf("%lld", &valCandies[i] ) ;

		candies.insert(make_pair(-valCandies[i], i) );
		orderCandies.insert(i) ;

	}


	ll ans = 0LL ;

	for(int i = 1 ; i <= ( (N+1)>>1 ) ; i++ )
	{
		
		ll val = -candies.begin()->first ;
		int idx = candies.begin()->second ;

		candies.erase( candies.begin() ) ;

		auto itPrev = orderCandies.find(idx) ; 
		
		int idxPrev = -1 ;
		int idxNxt = -1 ;

		if( itPrev != orderCandies.begin() )
		{
			itPrev-- ;
			idxPrev = *itPrev ;

			candies.erase( candies.find(make_pair(-valCandies[idxPrev] , idxPrev ) ) ) ;
			orderCandies.erase( itPrev ) ;

		}

		auto itNxt = orderCandies.find(idx) ; itNxt++ ;

		if(itNxt != orderCandies.end() )
		{
			idxNxt = *itNxt ;

			candies.erase( candies.find(make_pair(-valCandies[idxNxt], idxNxt) ) ) ;
			orderCandies.erase( itNxt ) ;

		}

		if(idxNxt != -1 && idxPrev != -1 )
		{
			valCandies[idxPrev] += valCandies[idxNxt] ;
			valCandies[idxPrev] -= val ;

			candies.insert(make_pair(-valCandies[idxPrev] , idxPrev ) ) ;
			orderCandies.insert( idxPrev ) ;

		}

		orderCandies.erase( orderCandies.find(idx) ) ;

		printf("%lld\n", ans += val ) ;

	}

}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
candies.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |   scanf("%lld", &valCandies[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92