제출 #73565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73565		funcsr	휴가 (IOI14_holiday)	C++17	7 / 100	2137 ms	66560 KiB

holiday

#include "holiday.h"
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y)-x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF (1LL<<60)
using namespace std;
typedef pair<long long, long long> P;

#define MAX_N (1<<17)
struct SegTree {
  const int num;
  const long long sum;
  SegTree *left = NULL, *right = NULL;
  SegTree(int n, long long s) : num(n), sum(s) {}

  long long rsum(int n, int l=0, int r=MAX_N) {
    if (n == 0) return 0;
    if (r-l==1) return sum;

    long long s = 0;
    if (right==NULL || n >= right->num) {
      if (right) {
        n -= right->num;
        s += right->sum;
      }
      if (left) s += left->rsum(n, l, (l+r)/2);
    }
    else {
      if (right) s += right->rsum(n, (l+r)/2);
    }
    return s;
  }
  SegTree *update(int p, int val, int l=0, int r=MAX_N) {
    if (r-l == 1) {
      SegTree *ret = new SegTree(1, val);
      return ret;
    }

    int mid = (l+r)/2;

    SegTree *a = left, *b = right;
    if (p < mid) {
      if (!left) left = new SegTree(0, 0);
      a = left->update(p, val, l, mid);
    }
    else {
      if (!right) right = new SegTree(0, 0);
      b = right->update(p, val, mid, r);
    }

    SegTree *ret = new SegTree(num+1, sum+val);
    ret->left = a;
    ret->right = b;
    return ret;
  }
};
int D, W;
SegTree *seg[100001];
long long f(int d, int e) {
  if (d < e*W) return -INF;
  return seg[e]->rsum(d-e*W);
}
int best(int x, int bottom, int top) {
  P mp = P(-1, -1);
  for (int i=bottom; i<=top; i++) mp = max(mp, P(f(x, i), -i));
  return -mp._2;
}

void solve(int l, int r, int bottom, int top, vector<long long> &ret) {
  if (l > r) return;
  if (l == r) {
    ret[l] = best(l, bottom, top);
    return;
  }
  int mid = (l+r)/2;
  int q = ret[mid] = best(mid, bottom, top);
  solve(l, mid-1, bottom, q, ret);
  solve(mid+1, r, q, top, ret);
}

vector<long long> solve(vector<int> A, int w) {
  W = w;
  vector<P> ps;
  rep(i, A.size()) ps.pb(P(A[i], i));
  sort(all(ps));

  seg[0] = new SegTree(0, 0);
  rep(i, A.size()) {
    int p = index(ps, P(A[i], i));
    seg[i+1] = seg[i]->update(p, A[i]);
  }

  vector<long long> ret(D+1, 0);
  solve(0, D, 0, A.size(), ret);
  rep(i, D+1) ret[i] = f(i, ret[i]);
  return ret;
}

long long findMaxAttraction(int N, int S, int DD, int A[]) {
  D = DD;
  vector<int> left, right;
  rep(i, S) left.pb(A[i]);
  for (int i=S+1; i<N; i++) right.pb(A[i]);
  reverse(all(left));
  long long m = 0;
  rep(w, 2) {
    vector<long long> dpL = solve(left, 1+w);
    vector<long long> dpR = solve(right, 1+(w^1));
    rep(i, D+1) m = max(m, dpL[i]+dpR[D-i]);
    rep(i, D) m = max(m, dpL[i]+dpR[D-i-1]+A[S]);
  }
  return m;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'std::vector<long long int> solve(std::vector<int>, int)':
holiday.cpp:6:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
holiday.cpp:92:3: note: in expansion of macro 'rep'
   rep(i, A.size()) ps.pb(P(A[i], i));
   ^~~
holiday.cpp:6:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
holiday.cpp:96:3: note: in expansion of macro 'rep'
   rep(i, A.size()) {
   ^~~
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: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53