oj.uz

Submission #413778

# Submission time Handle Problem Language Result Execution time Memory
413778 2021-05-29T12:38:49 Z Antekb Holiday (IOI14_holiday) C++14
100 / 100
 3093 ms 7632 KB 
#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll dp[N], opt[N];
int tab[N];
int n, s, d;
multiset<int> S, S2;//S-dobre, S2-reszta
//multiset<int> co;
ll sum=0;
void dodaj(int i){
	//cout<<"+ "<<i<<"\n";
	//co.insert(i);
	S.insert(tab[i]);
	sum+=tab[i];
}
void usun(int i){
	//cout<<"- "<<i<<"\n";
	//co.erase(co.find(i));
	if(S.find(tab[i])!=S.end()){
		sum-=tab[i];
		S.erase(S.find(tab[i]));
	}
	else S2.erase(S2.find(tab[i]));
}
/*void out(){
	cout<<co.size()<<"\n";
	for(int i:co)cout<<i<<" ";
	cout<<"\n";
}*/
int L=0, R=0;
void solve(int l, int r, int lopt, int ropt){
	//cout<<l<<" "<<r<<" "<<lopt<<" "<<ropt<<endl;
	//out();
	if(l>r) return;
	int m=(l+r+1)>>1;
	while(L>m)dodaj(--L);
	while(R<max(m, lopt))dodaj(R++);
	while(L<m)usun(L++);
	while(R>max(m, lopt))usun(--R);
	//cout<<L<<" "<<R<<"\n";
	/*for(int i=m; i<=r && i<lopt; i++){
		dodaj(i);
	}*/
	opt[m]=max(lopt, m);
	for(int i=opt[m]; i<=ropt; i++){
		dodaj(i);
		while(S.size()>max(0, d+2*m-s-i)){
			sum-=*S.begin();
			S2.insert(*S.begin());
			S.erase(S.begin());
		}
		while(S.size()<max(0, d+2*m-s-i) && S2.size()){
			sum+=*S2.crbegin();
			S.insert(*S2.crbegin());
			S2.erase(S2.find(*S2.crbegin()));
		}
		//cout<<m<<" "<<i<<" "<<sum<<"\n";
		if(sum>dp[m]){
			opt[m]=i;
			dp[m]=sum;
		}
	}
	R=ropt+1;
	/*for(int i=ropt; i>=opt[m]; i--){
		usun(i);
	}*/
	//cout<<m<<" "<<dp[m]<<" opt: "<<opt[m]<<endl;
	//for(int i=lopt; i<m; i++)usun(i);
	solve(l, m-1, lopt, opt[m]);
	//for(int i=m; i<opt[m] && i<=r; i++)usun(i);
	solve(m+1, r, opt[m], ropt);
}
long long int findMaxAttraction(int _n, int start, int _d, int attraction[]) {
	n=_n;
	d=_d;
	s=start;
	for(int i=0; i<n; i++)tab[i]=attraction[i];
	solve(max(0, s-d), s, 0, n-1);
	ll ans=0;
	for(int i=0; i<=s; i++)ans=max(ans, dp[i]);
    for(int i=0; i<n; i++)tab[i]=attraction[n-1-i];
    L=0, R=0;
    for(int i=0; i<n; i++)dp[i]=opt[i]=0;
    //co.clear();
    S.clear();
    S2.clear();
    sum=0;
    s=n-1-s;
    solve(max(0, s-d), s, 0, n-1);
	for(int i=0; i<=s; i++)ans=max(ans, dp[i]);
    return ans;
}

Compilation message

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:49:17: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   49 |   while(S.size()>max(0, d+2*m-s-i)){
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~
holiday.cpp:54:17: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   54 |   while(S.size()<max(0, d+2*m-s-i) && S2.size()){
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 7312 KB Output is correct
2 Correct 259 ms 7236 KB Output is correct
3 Correct 720 ms 7336 KB Output is correct
4 Correct 932 ms 7320 KB Output is correct
5 Correct 1926 ms 6768 KB Output is correct
6 Correct 276 ms 2644 KB Output is correct
7 Correct 860 ms 4216 KB Output is correct
8 Correct 1153 ms 4956 KB Output is correct
9 Correct 185 ms 1996 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 864 KB Output is correct
2 Correct 10 ms 856 KB Output is correct
3 Correct 11 ms 868 KB Output is correct
4 Correct 34 ms 872 KB Output is correct
5 Correct 36 ms 844 KB Output is correct
6 Correct 8 ms 760 KB Output is correct
7 Correct 9 ms 768 KB Output is correct
8 Correct 10 ms 716 KB Output is correct
9 Correct 10 ms 716 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 7320 KB Output is correct
2 Correct 599 ms 7316 KB Output is correct
3 Correct 572 ms 3268 KB Output is correct
4 Correct 29 ms 844 KB Output is correct
5 Correct 9 ms 716 KB Output is correct
6 Correct 11 ms 752 KB Output is correct
7 Correct 10 ms 696 KB Output is correct
8 Correct 3086 ms 7604 KB Output is correct
9 Correct 3093 ms 7632 KB Output is correct