Submission #701917

# Submission time Handle Problem Language Result Execution time Memory
701917 2023-02-22T10:41:01 Z PCTprobability Holiday (IOI14_holiday) C++17
47 / 100
1758 ms 11852 KB
#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

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)){
      |             ~~~~~~~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 0 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Correct 0 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 72 ms 10008 KB Output is correct
2 Correct 70 ms 10060 KB Output is correct
3 Correct 74 ms 10052 KB Output is correct
4 Correct 71 ms 9976 KB Output is correct
5 Correct 59 ms 6784 KB Output is correct
6 Correct 49 ms 9236 KB Output is correct
7 Correct 34 ms 4760 KB Output is correct
8 Correct 36 ms 4580 KB Output is correct
9 Correct 60 ms 11852 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1733 ms 1036 KB Output is correct
2 Correct 1758 ms 1012 KB Output is correct
3 Correct 1713 ms 1016 KB Output is correct
4 Correct 419 ms 852 KB Output is correct
5 Correct 601 ms 860 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 21 ms 596 KB Output is correct
8 Correct 24 ms 688 KB Output is correct
9 Correct 27 ms 596 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 688 KB Output isn't correct
2 Halted 0 ms 0 KB -