Submission #701917

#	Time	Username	Problem	Language	Result	Execution time	Memory
701917		PCTprobability	Holiday (IOI14_holiday)	C++17	47 / 100	1758 ms	11852 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
using ll = long long;
ll findMaxAttraction(int n,int start,int d,int attraction[]){
  ll ans=0;
  if(n<=3000){
    for(int i=start;i>=0;i--){
      if(d-(start-i)<0) continue;
      multiset<ll> s;
      ll sum=0;
      for(int j=start;j>=i;j--){
        s.insert(attraction[j]);
        sum+=attraction[j];
      }
      while(s.size()<d-(start-i)) s.insert(0);
      while(s.size()>d-(start-i)){
        auto itr=s.begin();
        sum-=(*itr);
        s.erase(itr);
      }
      ans=max(sum,ans);
      for(int j=start+1;j<n;j++){
        s.insert(attraction[j]);
        sum+=attraction[j];
        auto itr=s.begin();
        sum-=(*itr);
        s.erase(itr);
        if(s.size()){
          auto itr2=s.begin();
          sum-=(*itr2);
          s.erase(itr2);
        }
        if(start-i>=j-start&&s.size()){
          auto itr2=s.begin();
          sum-=(*itr2);
          s.erase(itr2);
        }
        ans=max(sum,ans);
      }
    }
  }
  else if(start==0){
    multiset<ll> s;
    s.insert(attraction[0]);
    for(int i=0;i<d-1;i++) s.insert(0);
    ll sum=attraction[0];
    ans=max(sum,ans);
    for(int i=1;i<n;i++){
      s.insert(attraction[i]);
      sum+=attraction[i];
      auto itr=s.begin();
      sum-=(*itr);
      s.erase(itr);
      if(s.size()){
        auto itr2=s.begin();
        sum-=(*itr2);
        s.erase(itr2);
      }
      ans=max(sum,ans);
    }
  }
  return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:16:21: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |       while(s.size()<d-(start-i)) s.insert(0);
      |             ~~~~~~~~^~~~~~~~~~~~
holiday.cpp:17:21: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |       while(s.size()>d-(start-i)){
      |             ~~~~~~~~^~~~~~~~~~~~

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