Submission #51314

#	Time	Username	Problem	Language	Result	Execution time	Memory
51314		mirbek01	Holiday (IOI14_holiday)	C++17	47 / 100	5025 ms	2112 KiB

holiday

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

using namespace std;

const int N = 3e5 + 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 i = 0; i <= start; i ++){
                  int last;
                  for(int j = i; j < n; j ++){
                        update(attraction[j], 1);
                        last = j;
                        if(start <= j){
                              int ost = d - (min(j - start, start - i) + (j - i));
                              if(ost <= 0) break;
                              ans = max(ans, get(ost).first);
                        }
                  }
                  for(int j = i; j <= last; j ++){
                        update(attraction[j], -1);
                  }
            }
      }
      return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:72:23: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
                   int last;
                       ^~~~
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: 17 / 17
• Subtask 4: 0 / 53