Submission #1019530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019530		pcc	Holiday (IOI14_holiday)	C++17	47 / 100	438 ms	2004 KiB

holiday

#include"holiday.h"

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

#define ll long long

struct DS{
	priority_queue<ll,vector<ll>,greater<ll>> pq;
	ll sum = 0;
	DS(){
		sum = 0;
	}
	void init(){
		sum = 0;
		while(!pq.empty())pq.pop();
	}
	void add(ll k){
		pq.push(k);
		sum += k;
	}
	void shape(int len){
		while(!pq.empty()&&(ll)pq.size()>len){
			sum -= pq.top();
			pq.pop();
		}
		assert(pq.empty()||pq.size()<=len);
		return;
	}
};

namespace ZERO{
	const ll mxn = 1e5+10;
	DS ds;
	ll GO(int n,int s,int d,int arr[]){
		ds.init();
		ll ans = 0;
		for(int i = 0;i<=min(d,n-1);i++){
			ds.add(arr[i]);
			int rest = d-i;
			ds.shape(d-i);
			ans = max(ans,ds.sum);
		}
		return ans;
	}
}

namespace BRUTE{
	const ll mxn = 3030;
	int tr1[mxn],tr2[mxn];
	ll arr[mxn];
	DS ds;
	int n,s,d;

	ll calc(int e){
		ll re = 0;

		ds.init();
		for(int i = e;i>s;i--)ds.add(arr[i]);
		ll tans = 0;
		for(int i = s;i>=0;i--){
			ds.add(arr[i]);
			int rest = d-((e-s)*2+(s-i));
			ds.shape(rest);
			//cerr<<"L FIRST: "<<i<<' '<<e<<"::"<<rest<<','<<ds.pq.size()<<','<<ds.sum<<endl;
			if(tans<ds.sum){
				tans = ds.sum;
				tr1[e] = i;
			}
		}
		re = max(re,tans);

		ds.init();
		tans = 0;
		for(int i = e;i>s;i--)ds.add(arr[i]);
		for(int i = s;i>=0;i--){
			ds.add(arr[i]);
			int rest = d-((e-s)+(s-i)*2);
			ds.shape(rest);
			if(tans<ds.sum){
				tans = ds.sum;
				tr2[e] = i;
			}
		}
		re = max(re,tans);

		return re;
	}
	void check(int tr[]){
		vector<int> v;
		for(int i = 0;i<n;i++)if(tr[i] != -1)v.push_back(i);
		for(int i = 1;i<v.size();i++){
			assert(tr[v[i-1]]<=tr[v[i]]);
			assert(v[i-1] == v[i]-1);
		}
		return;
	}
	ll GO(int nn,int ss,int dd,int tarr[]){
		memset(tr1,-1,sizeof(tr1));
		memset(tr2,-1,sizeof(tr2));
		n = nn,s = ss,d = dd;
		for(int i = 0;i<n;i++)arr[i] = tarr[i];
		ll ans = 0;
		for(int i = s;i<min(s+d,n);i++)ans = max(ans,calc(i));
		check(tr1);
		check(tr2);
		return ans;
	}
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	/*
	auto t1 = BRUTE::GO(n,start,d,attraction),t2 = ZERO::GO(n,start,d,attraction);
	cerr<<t1<<','<<t2<<endl;
	assert(t1 == t2);
	*/
	if(start == 0)return ZERO::GO(n,start,d,attraction);
	else return BRUTE::GO(n,start,d,attraction);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from holiday.cpp:3:
holiday.cpp: In member function 'void DS::shape(int)':
holiday.cpp:27:31: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |   assert(pq.empty()||pq.size()<=len);
      |                      ~~~~~~~~~^~~~~
holiday.cpp: In function 'long long int ZERO::GO(int, int, int, int*)':
holiday.cpp:40:8: warning: unused variable 'rest' [-Wunused-variable]
   40 |    int rest = d-i;
      |        ^~~~
holiday.cpp: In function 'void BRUTE::check(int*)':
holiday.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(int i = 1;i<v.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53