#include <bits/stdc++.h>
#ifndef TEST
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif
using namespace std;
typedef long long ll;
const ll LIM = 30;
void imp(){
puts("impossible");
exit(0);
}
ll dq1[1000002];
ll dq2[1000002];
int fr, sz;
ll f(ll x, ll y, bool b){
if(b) return max(x, y);
return min(x, y);
}
void calculateMax(int n, ll* arr, int lim, vector<ll>& ret){
ret = vector<ll>(lim+1, -1e18);
ret[0] = 0;
vector<ll> tvec (lim+1, -1e18);
for(int i=1; i<=n; i++){
tvec.swap(ret);
for(int s=0; s<i; s++){
fr=sz=0;
for(int j=s, p=0; j<=lim; j+=i, p++){
ret[j] = max(ret[j], tvec[j]);
while(fr!=sz && dq2[fr] < p) fr++;
ll nf = tvec[j]-p;
while(fr!=sz && dq1[sz-1] < nf) sz--;
dq1[sz] = nf;
dq2[sz++] = p+arr[i];
ret[j] = max(ret[j], dq1[fr] + p);
}
}
}
}
void calculateMin(int n, ll* arr, int lim, vector<ll>& ret){
ret = vector<ll>(lim+1, 1e18);
ret[0] = 0;
vector<ll> tvec (lim+1, 1e18);
for(int i=1; i<=n; i++){
tvec.swap(ret);
for(int s=0; s<i; s++){
fr=sz=0;
for(int j=s, p=0; j<=lim; j+=i, p++){
ret[j] = min(ret[j], tvec[j]);
while(fr!=sz && dq2[fr] < p) fr++;
int nf = tvec[j]-p;
while(fr!=sz && dq1[sz-1] > nf) sz--;
dq1[sz] = nf;
dq2[sz++] = p+arr[i];
ret[j] = min(ret[j], dq1[fr] + p);
}
}
}
}
int n;
ll k;
ll arr[302];
ll used[302];
ll rem[302];
vector<ll> DP, DP2;
ll ans = -1e18;
ll frontCnt;
int main(){
scanf("%lld %lld", &n, &k);
for(int i=0; i<n; i++) scanf("%lld", &arr[i]);
for(int i=0; i<=n; i++) scanf("%lld", &arr[i]);
if(k<=0) imp();
for(int i=0; i<=n; i++){
if(k >= arr[i]*i){
k -= arr[i]*i;
used[i] = arr[i];
rem[i] = 0;
}
else{
ll tmp = k/i;
used[i] = tmp;
rem[i] = arr[i]-tmp;
k -= tmp*i;
}
}
if(accumulate(rem, rem+n+1, 0LL) == 0) imp();
frontCnt = accumulate(used, used+n+1, 0LL);
calculateMax(n, rem, LIM, DP); /// �ִ�
calculateMin(n, used, LIM, DP2); /// �ּ�
for(ll i=k; i<=LIM; i++){
ll j = i-k;
ans = max(ans, frontCnt + DP[i] + DP2[j]);
}
if(ans <= 0) imp();
printf("%lld", ans);
}
Compilation message
vault.cpp: In function 'int main()':
vault.cpp:81:15: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
81 | scanf("%lld %lld", &n, &k);
| ~~~^ ~~
| | |
| | int*
| long long int*
| %d
vault.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%lld %lld", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
vault.cpp:82:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | for(int i=0; i<n; i++) scanf("%lld", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
vault.cpp:83:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | for(int i=0; i<=n; i++) scanf("%lld", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
