#include <bits/stdc++.h>
using namespace std;
const int MAX_M = 300;
int MAX_S;
int MIN_S;
const long long INF = 1e18;
int m;
unordered_map<int, long long> taken, untaken;
unordered_map<int, long long> dpCrt, dpPrv;
void add( int x, int k ) {
swap( dpCrt, dpPrv );
for ( int s = MIN_S; s <= MAX_S; s++ )
dpCrt[s] = dpPrv[s];
/*if ( x > 0 ) {
for ( int r = 0; r < x; r++ ) {
deque<pair<int, int>> d;
for ( int i = 0, s = MIN_S + r; s <= MAX_S; i++, s += x ) {
if ( !d.empty() && i - d.front().second > k )
d.pop_front();
while ( !d.empty() && dpPrv[s] - i >= dpPrv[d.back().first] - d.back().second )
d.pop_back();
d.push_back( { s, i } );
dpCrt[s] = dpPrv[d.front().first] + i - d.front().second;
}
}
} else {
x = -x;
for ( int r = 0; r < x; r++ ) {
deque<pair<int, int>> d;
for ( int i = 0, s = MAX_S - r; s >= MAX_S; i++, s -= x ) {
if ( !d.empty() && i - d.front().second > k )
d.pop_front();
while ( !d.empty() && dpPrv[s] - i >= dpPrv[d.back().first] - d.back().second )
d.pop_back();
d.push_back( { s, i } );
dpCrt[s] = dpPrv[d.front().first] + i - d.front().second;
}
}
}*/
for ( int s = MIN_S; s <= MAX_S; s++ ) {
for ( int i = 0; i <= k; i++ ) {
if ( MIN_S <= s - x * i && s - x * i <= MAX_S )
dpCrt[s] = max( dpCrt[s], dpPrv[s - x * i] + i );
}
}
for ( int s = MIN_S; s <= MAX_S; s++ )
dpCrt[s] = (dpCrt[s] <= -INF + m ? -INF : dpCrt[s]);
}
void substract( int x, int k ) {
swap( dpCrt, dpPrv );
for ( int s = MIN_S; s <= MAX_S; s++ )
dpCrt[s] = dpPrv[s];
/*if ( x < 0 ) {
x = -x;
for ( int r = 0; r < x; r++ ) {
deque<pair<int, int>> d;
for ( int i = 0, s = MIN_S + r; s <= MAX_S; i++, s += x ) {
if ( !d.empty() && i - d.front().second > k )
d.pop_front();
while ( !d.empty() && dpPrv[s] + i >= dpPrv[d.back().first] + d.back().second )
d.pop_back();
d.push_back( { s, i } );
dpCrt[s] = dpPrv[d.front().first] - i + d.front().second;
}
}
} else {
for ( int r = 0; r < x; r++ ) {
deque<pair<int, int>> d;
for ( int i = 0, s = MAX_S - r; s >= MAX_S; i++, s -= x ) {
if ( !d.empty() && i - d.front().second > k )
d.pop_front();
while ( !d.empty() && dpPrv[s] + i >= dpPrv[d.back().first] + d.back().second )
d.pop_back();
d.push_back( { s, i } );
dpCrt[s] = dpPrv[d.front().first] - i + d.front().second;
}
}
}*/
for ( int s = MIN_S; s <= MAX_S; s++ ) {
for ( int i = 0; i <= k; i++ ) {
if ( MIN_S <= s + x * i && s + x * i <= MAX_S )
dpCrt[s] = max( dpCrt[s], dpPrv[s + x * i] - i );
}
}
for ( int s = MIN_S; s <= MAX_S; s++ )
dpCrt[s] = (dpCrt[s] <= -INF + m ? -INF : dpCrt[s]);
}
void afis() {
for ( int s = MIN_S; s <= MAX_S; s++ ) {
if ( dpCrt[s] != -INF )
cout << dpCrt[s] << " " << s << "\n";
}
cout << "\n";
}
int main() {
long long l, u = 0, t = 0;
cin >> m >> l;
MIN_S = -m * m;
MAX_S = m * m;
for ( int i = -m; i <= m; i++ ) {
cin >> untaken[i];
u += untaken[i];
}
if ( l < 0 ) {
for ( int i = 1; i <= m; i++ )
swap( untaken[i], untaken[-i] );
l = -l;
}
long long s = 0;
for ( int i = -m; i <= 0; i++ ) {
long long x = untaken[i];
s += i * x;
taken[i] += x;
untaken[i] -= x;
t += x;
u -= x;
}
for ( int i = 1; i <= m; i++ ) {
long long x = min( untaken[i], (l - s) / i );
s += i * x;
taken[i] += x;
untaken[i] -= x;
t += x;
u -= x;
}
if ( s + m < l ) {
for ( int i = -m; i < 0; i++ ) {
long long x = min( taken[i], (l - s) / (-i) );
s -= i * x;
taken[i] -= x;
untaken[i] += x;
t -= x;
u += x;
}
}
/*cout << s << "\n";
for ( int i = -m; i <= m; i++ )
cout << i << " " << taken[i] << " " << untaken[i] << "\n";*/
for ( int s = MIN_S; s <= MAX_S; s++ )
dpCrt[s] = -INF;
dpCrt[0] = 0;
for ( int i = -m; i <= m; i++ ) {
add( i, min( (long long)m, untaken[i] ) );
//afis();
substract( i, min( (long long)m, untaken[i] ) );
//afis();
}
//afis();
if ( l - s > MAX_S || dpCrt[l - s] == -INF )
cout << "impossible\n";
else
cout << t + dpCrt[l - s] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
