oj.uz

Submission #918397

# Submission time Handle Problem Language Result Execution time Memory
918397 2024-01-29T19:13:24 Z contest_alt Holiday (IOI14_holiday) C++17
47 / 100
 159 ms 27288 KB 
#include "holiday.h"

using ll = long long;

#include <algorithm>
#include <vector>

#include <set>

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

  int v[MAXN];

  int nractiv[1 + ((1 + SMALLER) >> 2)][1 + SMALLER];
  ll sp[1 + ((1 + SMALLER) >> 2)][1 + SMALLER];

  int idx[MAXN];
  int val[MAXN];

  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;

      int nract = nractiv[mij >> 2][right] - nractiv[mij >> 2][left];
      for( int i = mij - (mij & 3) ; i < mij ; i++ )
        nract += (idx[i] >= left && idx[i] <= right);

      if( nract < x )
        st = mij;
      else
        dr = mij;
    }

    ll ret = sp[dr >> 2][right] - sp[dr >> 2][left];
    for( int i = dr - (dr & 3) ; i < dr ; i++ )
      ret += (idx[i] >= left && idx[i] <= right) ? val[i] : 0;

    return ret;
  }

  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 ){
      idx[activ] = _idx;
      val[activ] = v[_idx];
      activ++;

      for( int A = ((activ - 1) >> 2) + 1 ; (A << 2) <= n ; A++ ){
        nractiv[A][_idx + 1]++;
        sp[A][_idx + 1] += v[_idx];
      }
    }

    for( int A = 0 ; (A << 2) <= n ; A++ )
      for( int i = 1 ; i <= n ; i++ ){
        nractiv[A][i] += nractiv[A][i - 1];
        sp[A][i] += sp[A][i - 1];
      }
    
    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[] ) {
    // start == 0
    ll ret = 0;

    std::multiset<int> vals;
    ll setsum = 0;
    
    for( int i = 0 ; i < n ; i++ ){
      int nr = d - i;
      if( nr <= 0 )
        break;

      vals.insert( v[i] );
      setsum += v[i];

      while( (int)vals.size() > nr ){
        setsum -= *vals.begin();
        vals.erase( vals.begin() );
      }

      ret = setsum > ret ? setsum : ret;
    }
    
    return ret;
  }
}

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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2824 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5464 KB Output is correct
2 Correct 22 ms 5460 KB Output is correct
3 Correct 23 ms 5444 KB Output is correct
4 Correct 22 ms 5504 KB Output is correct
5 Correct 22 ms 3936 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 12 ms 2908 KB Output is correct
8 Correct 14 ms 2908 KB Output is correct
9 Correct 5 ms 1624 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27288 KB Output is correct
2 Correct 15 ms 27224 KB Output is correct
3 Correct 18 ms 27228 KB Output is correct
4 Correct 159 ms 26804 KB Output is correct
5 Correct 115 ms 25952 KB Output is correct
6 Correct 5 ms 11100 KB Output is correct
7 Correct 8 ms 11100 KB Output is correct
8 Correct 9 ms 11100 KB Output is correct
9 Correct 10 ms 11232 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5468 KB Output is correct
2 Correct 29 ms 6536 KB Output is correct
3 Incorrect 5 ms 1376 KB Output isn't correct
4 Halted 0 ms 0 KB -