Submission #50513

#	Time	Username	Problem	Language	Result	Execution time	Memory
50513		mirbek01	Holiday (IOI14_holiday)	C++17	30 / 100	5020 ms	2652 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 3e3 + 2;

int n, cnt[N], t[N * 4], ar[N];
long long sum[N * 4];

void update(int pos, int val, int v = 1, int tl = 1, int tr = N - 1){
      if(tl == tr){
            t[v] += val;
            sum[v] += val * ar[tl];
      } else {
            int tm = (tl + tr) >> 1;
            if(pos <= tm){
                  update(pos, val, v << 1, tl, tm);
            } else {
                  update(pos, val, (v << 1) | 1, tm + 1, tr);
            }
            t[v] = t[v << 1] + t[(v << 1) | 1];
            sum[v] = sum[v << 1] + sum[(v << 1) | 1];
      }
}

pair <long long, int> get(int x, int v = 1, int tl = 1, int tr = N - 1){
      if(!x || !sum[v]) return {0ll, 0};
      if(t[v] <= x) return {sum[v], t[v]};
      int tm = (tl + tr) >> 1;
      pair <long long, int> f = get(x, (v << 1) | 1, tm + 1, tr);
      pair <long long, int> s = get(x - f.second, (v << 1), tl, tm);
      return {f.first + s.first, s.second + f.second};
}

long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
      n = N;
      int fl = 1;
      long long ans = 0;
      for(int i = 0; i < n; i ++)
            if(attraction[i] > 100) fl = 0;
      if(!start && fl){
            for(int i = 0; i < n; i ++){
                  cnt[attraction[i]] ++;
                  long long res = 0;
                  if(i < d){
                        int now = d - i;
                        for(int i = 100; i >= 0; i --){
                              if(now >= cnt[i]){
                                    res += cnt[i] * i;
                                    now -= cnt[i];
                              } else {
                                    res += now * i;
                                    now = 0;
                              }
                        }
                  }
                  ans = max(ans, res);
            }
      } else {
            vector <int> v;
            for(int i = 0; i < n; i ++)
                  v.push_back(attraction[i]);
            sort(v.begin(), v.end());
            v.resize(unique(v.begin(), v.end()) - v.begin());
            for(int i = 0; i < n; i ++){
                  attraction[i] = lower_bound(v.begin(), v.end(), attraction[i]) - v.begin() + 1;
            }
            for(int i = 1; i <= n; i ++)
                  ar[i] = v[i - 1];
            for(int t = 4; t <= d; t ++){
                  long long res1 = 0, res2 = 0;
                  for(int i = start; i < n; i ++){
                        if((i - start) * 2 >= t) break;
                        update(attraction[i], 1);
                        res1 = max(res1, get(t - (i - start) * 2).first);
                  }
                  for(int i = start; i < n; i ++){
                        if((i - start) * 2 >= t) break;
                        update(attraction[i], -1);
                  }
                  for(int i = start - 1; i >= 0; i --){
                        if((start - i) >= (d - t)) break;
                        update(attraction[i], 1);
                        res2 = max(res2, get((d - t) - (start - i)).first);
                  }
                  for(int i = start - 1; i >= 0; i --){
                        if((start - i) >= (d - t)) break;
                        update(attraction[i], -1);
                  }
                  ans = max(ans, res1 + res2);
            }
            for(int t = 0; t <= d; t ++){
                  long long res1 = 0, res2 = 0;
                  for(int i = start; i < n; i ++){
                        if((i - start) >= t) break;
                        update(attraction[i], 1);
                        res1 = max(res1, get(t - (i - start)).first);
                  }
                  for(int i = start; i < n; i ++){
                        if((i - start) >= t) break;
                        update(attraction[i], -1);
                  }
                  for(int i = start - 1; i >= 0; i --){
                        if((start - i) * 2 >= (d - t)) break;
                        update(attraction[i], 1);
                        res2 = max(res2, get((d - t) - (start - i) * 2).first);
                  }
                  for(int i = start - 1; i >= 0; i --){
                        if((start - i) * 2 >= (d - t)) break;
                        update(attraction[i], -1);
                  }
                  ans = max(ans, res1 + res2);
            }
      }
      return ans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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