Submission #50494

#	Time	Username	Problem	Language	Result	Execution time	Memory
50494		mirbek01	Holiday (IOI14_holiday)	C++17	30 / 100	179 ms	1168 KiB

holiday

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

using namespace std;

const int N = 1e5 + 2;

int n, cnt[N];

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 {
            if(n <= 20){
                  for(int mask = 1; mask < (1 << n); mask ++){
                        int kol = 0;
                        long long res = 0, last = start;
                        for(int i = start; i < n; i ++){
                              int bit = (1 << i) & mask;
                              if(bit){
                                    res += attraction[i];
                                    kol ++;
                                    last = i;
                              }
                        }
                        kol += (last - start) * 2;
                        last = start;
                        for(int i = start - 1; i >= 0; i --){
                              int bit = (1 << i) & mask;
                              if(bit){
                                    res += attraction[i];
                                    kol ++;
                                    last = i;
                              }
                        }
                        kol += start - last;
                        if(kol <= d) ans = max(ans, res);
                        kol = res = 0, last = start;
                        for(int i = start; i >= 0; i --){
                              int bit = (1 << i) & mask;
                              if(bit){
                                    res += attraction[i];
                                    kol ++;
                                    last = i;
                              }
                        }
                        kol += (start - last) * 2;
                        last = start;
                        for(int i = start + 1; i < n; i ++){
                              int bit = (1 << i) & mask;
                              if(bit){
                                    res += attraction[i];
                                    kol ++;
                                    last = i;
                              }
                        }
                        kol += last - start;
                        if(kol <= d) ans = max(ans, res);
                  }
            }
      }
      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