Submission #995103

#	Time	Username	Problem	Language	Result	Execution time	Memory
995103		fuad27	Holiday (IOI14_holiday)	C++17	24 / 100	5028 ms	10144 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
struct DS {
  vector<int> v;
  void add(int val) {
    v.push_back(val);
  }
  long long get(int x) {
    sort(v.rbegin(), v.rend());
    long long sum=0;
    for(int i = 0;i<min((int)v.size(), x);i++) {
      sum+=v[i];
    }
    return sum;
  }
  void erase(int x) {
    sort(v.begin(), v.end());
    v.erase(find(v.begin(), v.end(), 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);
  assert(ds.v.size() == (start-pr-1));
}
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 (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from holiday.cpp:2:
holiday.cpp: In function 'void calcs2(int, int, int, int)':
holiday.cpp:113:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |   assert(ds.v.size() == (start-pr-1));
      |          ~~~~~~~~~~~~^~~~~~~~~~~~~~~

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