Submission #50985

#	Time	Username	Problem	Language	Result	Execution time	Memory
50985		Talant	Holiday (IOI14_holiday)	C++17	47 / 100	5012 ms	5620 KiB

holiday

#include"holiday.h"

#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back

using namespace std;

const int N = (1e6 + 5);

long long ans;
int u[N];

multiset<int> st;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
      if (start == 0 && n > 3000) {
            for (int i = 0; i < n; i ++) {
                  u[attraction[i]] ++;

                  int cn = d - i;

                  if (cn <= 0)
                        continue;

                  long long sum = 0;


                  for (int j = 100; j >= 1; j --) {
                        int o = min(u[j],cn);
                        sum += (o * 1ll * j);
                        cn -= o;
                  }
                  ans = max(ans,sum);
            }
            return ans;
      }
      else {
            for (int i = 0; i <= start; i ++) {
                  st.clear();
                  long long sum = 0;
                  for (int j = i; j < n; j ++) {
                        st.insert(attraction[j]);
                        sum += attraction[j];

                        int dist = 0;
                        if (j <= start) dist = d - (start - i);
                        else if (start <= i) dist = d - (j - start);
                        else dist = d - ((abs(start - i) + abs(j - start)) + min(abs(start - i),abs(j - start)));

                        if (dist <= 0)
                              break;
                        while (!st.empty() && st.size() > dist) {
                              sum -= (*st.begin());
                              st.erase(st.begin());
                        }
                        ans = max(ans,sum);
                  }
            }
            return ans;
      }
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:56:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         while (!st.empty() && st.size() > dist) {
                                               ~~~~~~~~~~^~~~~~
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