Submission #918393

#	Time	Username	Problem	Language	Result	Execution time	Memory
918393		contest_alt	Holiday (IOI14_holiday)	C++17	7 / 100	18 ms	65536 KiB

holiday

#include "holiday.h"

using ll = long long;

#include <algorithm>
#include <vector>

namespace Solver {
  const int MAXN = 1e5;
  const int SMALLER = 3000;

  int v[MAXN];

  int nractiv[1 + SMALLER][1 + SMALLER];
  ll sp[1 + SMALLER][1 + SMALLER];

  int n;

  ll query( int left, int right, int x ) {
    int st = 0, dr = n;

    right++;

    while( dr - st > 1 ){
      int mij = (st + dr) >> 1;

      if( nractiv[mij][right] - nractiv[mij][left] < x )
        st = mij;
      else
        dr = mij;
    }

    return sp[dr][right] - sp[dr][left];
  }

  ll patratic( int N, int start, int d, int w[] ) {
    n = N;
    
    std::vector<int> vals( n );
    for( int i = 0 ; i < n ; i++ ){
      v[i] = w[i];
      vals[i] = i;
    }

    std::sort( vals.begin(), vals.end(), [v]( int a, int b ) -> bool {
      return v[a] > v[b];
    } );

    for( int i = 0 ; i <= n ; i++ )
      nractiv[0][i] = sp[0][i] = 0;

    int activ = 0;
    for( int idx : vals ){
      for( int i = 0 ; i <= idx ; i++ ){
        nractiv[activ + 1][i] = nractiv[activ][i];
        sp[activ + 1][i] = sp[activ][i];
      }

      for( int i = idx + 1 ; i <= n ; i++ ){
        nractiv[activ + 1][i] = nractiv[activ][i] + 1;
        sp[activ + 1][i] = sp[activ][i] + v[idx];
      }

      activ++;
    }
    
    ll ret = 0;
    
    for( int st = 0 ; st <= start ; st++ )
      for( int dr = start ; dr < n ; dr++ ){
        int nr = d - (dr - st + std::min( start - st, dr - start ));

        if( nr <= 0 )
          continue;

        ll cand = query( st, dr, nr );

        ret = cand > ret ? cand : ret;
      }

    return ret;
  }
  
  ll main( int n, int start, int d, int v[] ) {
    return 0;
  }
}

long long int findMaxAttraction( int n, int start, int d, int attraction[] ) {
  if( n <= 3000 )
    return Solver::patratic( n, start, d, attraction );

  return Solver::main( n, start, d, attraction );
}

Compilation message (stderr)

holiday.cpp: In function 'll Solver::patratic(int, int, int, int*)':
holiday.cpp:45:43: warning: capture of variable 'Solver::v' with non-automatic storage duration
   45 |     std::sort( vals.begin(), vals.end(), [v]( int a, int b ) -> bool {
      |                                           ^
holiday.cpp:12:7: note: 'int Solver::v [100000]' declared here
   12 |   int v[MAXN];
      |       ^

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