oj.uz

Submission #995113

# Submission time Handle Problem Language Result Execution time Memory
995113 2024-06-08T13:07:52 Z fuad27 Holiday (IOI14_holiday) C++17
100 / 100
 2345 ms 14604 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
struct DS {
  multiset<int> s1, s2;
  long long ans=0;
  void add(int val) {
    if(s1.size() and val > (*s1.begin())) {
      s1.insert(val);
      ans+=val;
    }
    else s2.insert(val);
  }
  long long get(int x) {
    if(x<=0)return 0;
    while(s1.size()>x) {
      ans-=(*s1.begin());
      s2.insert(*s1.begin());
      s1.erase(s1.begin());
    }
    while(s1.size() < x and s2.size()) {
      long long val = *(--s2.end());
      s1.insert(val);
      ans+=val;
      s2.erase(s2.find(val));
    }
    return ans;
  }
  void erase(int x) {
    if(s2.find(x)!=s2.end())s2.erase(s2.find(x));
    else {
      ans-=x;
      s1.erase(s1.find(x));
    }
  }
} ds;
 
int n, start, d;
vector<int> attraction;
vector<long long> F, S, F2, S2;
 
void calcf1(int l, int r, int pl, int pr) {
  if(l>r)return;
  int mid = (l+r)/2;
  long long res=0;
  int opt = pl;
  for(int i = pl;i<=pr;i++) {
    ds.add(attraction[i]);
    long long val = ds.get(mid-abs(i-start));
    if(val >= res) {
      res=val;
      opt=i;
    }
  }
  F[mid] = res;
  for(int i = opt;i<=pr;i++)ds.erase(attraction[i]);
  calcf1(mid+1, r, opt, pr);
  for(int i = pl;i<opt;i++)ds.erase(attraction[i]);
  calcf1(l, mid-1, pl, opt);
}
void calcs1(int l, int r, int pl, int pr) {
  if(l>r)return;
  int mid = (l+r)/2;
  long long res=0;
  int opt = pl;
  for(int i = pl;i<=pr;i++) {
    ds.add(attraction[i]);
    long long val = ds.get(mid-2*abs(i-start));
    if(val >= res) {
      res=val;
      opt=i;
    }
  }
  S[mid] = res;
  for(int i = opt;i<=pr;i++)ds.erase(attraction[i]);
  calcs1(mid+1, r, opt, pr);
  for(int i = pl;i<opt;i++)ds.erase(attraction[i]);
  calcs1(l, mid-1, pl, opt);
}
//
void calcf2(int l, int r, int pl, int pr) {
  if(l>r)return;
  if(pl > pr) {
    for(int i = l;i<=r;i++) {
      F2[i] = 0;
    }
  }
  int mid = (l+r)/2;
  long long res=0;
  int opt = pr;
  for(int i = pr;i>=pl;i--) {
    ds.add(attraction[i]);
    long long val = ds.get(mid-abs(i-start));
    if(val >= res) {
      res=val;
      opt=i;
    }
  }
  F2[mid] = res;
  for(int i = pl;i<=opt;i++)ds.erase(attraction[i]);
  calcf2(mid+1, r, pl, opt);
  for(int i = opt+1;i<=pr;i++)ds.erase(attraction[i]);
  calcf2(l, mid-1, opt, pr);
}
void calcs2(int l, int r, int pl, int pr) {
  if(l>r)return;
  if(pl > pr) {
    for(int i = l;i<=r;i++) {
      S2[i] = 0;
    }
  }
  int mid = (l+r)/2;
  long long res=0;
  int opt = pr;
  for(int i = pr;i>=pl;i--) {
    ds.add(attraction[i]);
    long long val = ds.get(mid-2*abs(i-start));
    if(val >= res) {
      res=val;
      opt=i;
    }
  }
  S2[mid] = res;
  for(int i = pl;i<=opt;i++)ds.erase(attraction[i]);
  calcs2(mid+1, r, pl, opt);
  for(int i = opt+1;i<=pr;i++)ds.erase(attraction[i]);
  calcs2(l, mid-1, opt, pr);
}
long long int findMaxAttraction(int _n, int _start, int _d, int _attraction[]) {
  n=_n;
  start=_start;
  d=_d;
  S.resize(d+1);
  F.resize(d+1);
  S2.resize(d+1);
  F2.resize(d+1);
  attraction=vector<int>(_attraction, _attraction+_n);
  calcf1(1, _d, _start, _n-1);
  calcs1(1, _d, _start, _n-1);
  calcf2(1, _d, 0, _start-1);
  calcs2(1, _d, 0, _start-1);
  long long res=0;
  for(int i = 0;i<=d;i++) {
    res=max(res, F[i]+S2[d-i]);
    res=max(res, S[i]+F2[d-i]);
  }
  return res;
}

Compilation message

holiday.cpp: In member function 'long long int DS::get(int)':
holiday.cpp:16:20: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |     while(s1.size()>x) {
      |           ~~~~~~~~~^~
holiday.cpp:21:21: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |     while(s1.size() < x and s2.size()) {
      |           ~~~~~~~~~~^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 12164 KB Output is correct
2 Correct 632 ms 12380 KB Output is correct
3 Correct 980 ms 12376 KB Output is correct
4 Correct 1055 ms 12116 KB Output is correct
5 Correct 2345 ms 10048 KB Output is correct
6 Correct 811 ms 8024 KB Output is correct
7 Correct 1338 ms 6324 KB Output is correct
8 Correct 1442 ms 6740 KB Output is correct
9 Correct 563 ms 9372 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1116 KB Output is correct
2 Correct 16 ms 1116 KB Output is correct
3 Correct 16 ms 1064 KB Output is correct
4 Correct 28 ms 856 KB Output is correct
5 Correct 27 ms 972 KB Output is correct
6 Correct 7 ms 860 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 6 ms 860 KB Output is correct
9 Correct 6 ms 864 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 13648 KB Output is correct
2 Correct 2336 ms 14604 KB Output is correct
3 Correct 518 ms 3156 KB Output is correct
4 Correct 19 ms 856 KB Output is correct
5 Correct 7 ms 860 KB Output is correct
6 Correct 6 ms 856 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 1840 ms 5960 KB Output is correct
9 Correct 1820 ms 5716 KB Output is correct