Submission #701909

#	Time	Username	Problem	Language	Result	Execution time	Memory
701909		PCTprobability	Holiday (IOI14_holiday)	C++17	30 / 100	75 ms	11928 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<=20){
    for(int i=start;i>=0;i--){
      for(int j=start;j<n;j++){
        int ca=d-(start-i)-(j-start)-min(start-i,j-start);
        if(ca<0) continue;
        vector<int> a;
        for(int l=i;l<=j;l++) a.push_back(attraction[l]);
        sort(a.begin(),a.end());
        reverse(a.begin(),a.end());
        ll now=0;
        for(int l=0;l<ca&&l<a.size();l++) now+=a[l];
        ans=max(ans,now);
      }
    }
  }
  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:17:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for(int l=0;l<ca&&l<a.size();l++) now+=a[l];
      |                           ~^~~~~~~~~

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