제출 #918396

#제출 시각아이디문제언어결과실행 시간메모리
918396contest_alt휴가 (IOI14_holiday)C++17
24 / 100
162 ms27228 KiB
#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 + ((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[] ) { 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 ); }

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

holiday.cpp: In function 'll Solver::patratic(int, int, int, int*)':
holiday.cpp:56:43: warning: capture of variable 'Solver::v' with non-automatic storage duration
   56 |     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];
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...