Submission #153961

#	Time	Username	Problem	Language	Result	Execution time	Memory
153961		catalystgma	Holiday (IOI14_holiday)	C++11	23 / 100	5025 ms	2208 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
#define lll long long
#define ldb long double
#define pii pair<int,int>
#define pll pair<lll,lll>
#define pil pair<int,lll>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(int _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define maxn 100000
#define maxf 100

using namespace std;

int n;
int v[maxn+5], fv[maxf+5];
lll ans;

void umax (lll &a, lll b) { a = max(a,b); }

void dfs (int nod, int d, int mask, lll cur) {
  if (nod < 0 || nod >= n || d <= 0) return;
  dfs (nod-1, d-1, mask, cur);
  dfs (nod+1, d-1, mask, cur);
  if ((mask & (1<<nod)) == 0) {
    cur += v[nod];
    mask += (1<<nod);
    umax(ans, cur);
    dfs (nod, d-1, mask, cur);
  }
}

lll biggest (int rem) {
  int nr; lll cur = 0;
  for (nr = maxf; nr > 0 && rem > 0; nr--)
    if (rem > fv[nr]) {
      cur += 1LL * fv[nr] * nr;
      rem -= fv[nr];
    } else {
      cur += 1LL * rem * nr;
      rem = 0;
    }
  return cur;
}

lll findMaxAttraction (int n_, int start_, int d_, int* v_) {
  n = n_;
  int start = start_, d = d_;
  int i, j, z;
  for (i = 0; i < n; i++) v[i] = v_[i];
  if (n <= 20) {
    dfs (start, d, 0, 0);
  } else if (start == 0) {
    for (j = 0; j < n; j++) {
      fv[v[j]]++;
      umax(ans, biggest(d-j));
    }
  }
  return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:61:13: warning: unused variable 'z' [-Wunused-variable]
   int i, j, z;
             ^

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