| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 572583 |
2022-06-04T17:52:36 Z |
Leo121 |
Holiday (IOI14_holiday) |
C++14 |
|
26 ms |
1564 KB |
#include <bits/stdc++.h>
#include"holiday.h"
#define for0(i, n) for(int i = 0; i < int(n); ++ i)
#define far0(i, n) for(int i = int(n) - 1; i >= 0; -- i)
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
using namespace std;
typedef long long ll;
priority_queue<int> pq;
const int maxn = 3000;
const int maxd = 2 * maxn + maxn / 2;
ll dp[2][maxd + 2];
ll tabla[maxd + 2];
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
ll res = 0, aux = 0;
int cantidad, aux2;
if(!start){
for0(i, n){
aux += (ll) attraction[i];
pq.push(-1 * attraction[i]);
cantidad = max(d - i, 0);
if(cantidad == 0){
break;
}
while((int) pq.size() > cantidad){
aux2 = pq.top();
pq.pop();
aux -= (ll) aux2 * -1LL;
}
res = max(res, aux);
}
return res;
}
if(start == n - 1){
far0(i, n){
aux += (ll) attraction[i];
pq.push(-1 * attraction[i]);
cantidad = max(d - (n - i - 1), 0);
if(cantidad == 0){
break;
}
while((int) pq.size() > cantidad){
aux2 = pq.top();
pq.pop();
aux -= (ll) aux2 * -1LL;
}
res = max(res, aux);
}
return res;
}
if(!d){
return 0;
}
if(n <= maxn){
dp[(start - 1) % 2][1] = (ll) attraction[start - 1];
tabla[1] = dp[(start - 1) % 2][1];
int maximo = 1;
far0(i, start - 1){
for0(j, maxd + 2){
dp[i % 2][j] = 0;
}
forn(j, start - 1 - i, (start - 1 - i) * 2){
dp[i % 2][j] = max(dp[(i + 1) % 2][j - 1], dp[i % 2][j]);
dp[i % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i + 1) % 2][j - 1] + (ll) attraction[i]);
tabla[j] = max(tabla[j], dp[i % 2][j]);
tabla[j + 1] = max(tabla[j + 1], dp[i % 2][j + 1]);
maximo = max(maximo, j + 1);
}
}
for0(j, maxd + 2){
dp[0][j] = 0;
dp[1][j] = 0;
}
dp[start % 2][1] = (ll) attraction[start];
res = max(res, tabla[max(min(maximo, d - 1), 0)]);
res = max(res, tabla[max(min(maximo, d - 2), 0)] + dp[start % 2][1]);
forn(i, start + 1, n - 1){
for0(j, maxd + 2){
dp[i % 2][j] = 0;
}
forn(j, i - start, (i - start) * 2){
dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - 1]);
dp[i % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i - 1) % 2][j - 1] + (ll) attraction[i]);
if(j <= d){
res = max(res, dp[i % 2][j]);
res = max(res, dp[i % 2][j] + tabla[max(min(maximo, d - j - (i - start + 1)), 0)]);
}
if(j + 1 <= d){
res = max(res, dp[i % 2][j + 1]);
res = max(res, dp[i % 2][j + 1] + tabla[max(min(maximo, d - (j + 1) - (i - start + 1)), 0)]);
}
}
}
for0(i, maxd + 2){
tabla[i] = 0;
}
for0(j, maxd + 2){
dp[0][j] = 0;
dp[1][j] = 0;
}
dp[(start + 1) % 2][1] = (ll) attraction[start + 1];
tabla[1] = dp[(start + 1) % 2][1];
maximo = 1;
forn(i, start + 2, n - 1){
for0(j, maxd + 2){
dp[i % 2][j] = 0;
}
forn(j, i - start - 1, (i - start - 1) * 2){
dp[i % 2][j] = max(dp[(i - 1) % 2][j - 1], dp[i % 2][j]);
dp[i % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i - 1) % 2][j - 1] + (ll) attraction[i]);
tabla[j] = max(tabla[j], dp[i % 2][j]);
tabla[j + 1] = max(tabla[j + 1], dp[i % 2][j + 1]);
maximo = max(maximo, j + 1);
}
}
for0(j, maxd + 2){
dp[0][j] = 0;
dp[1][j] = 0;
}
dp[start % 2][1] = (ll) attraction[start];
res = max(res, tabla[max(min(maximo, d - 1), 0)]);
res = max(res, tabla[max(min(maximo, d - 2), 0)] + dp[start % 2][1]);
far0(i, start){
for0(j, maxd + 2){
dp[i % 2][j] = 0;
}
forn(j, start - i, (start - i) * 2){
dp[i % 2][j] = max(dp[i % 2][j], dp[(i + 1) % 2][j - 1]);
dp[i % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i + 1) % 2][j - 1] + (ll) attraction[i]);
if(j <= d){
res = max(res, dp[i % 2][j]);
res = max(res, dp[i % 2][j] + tabla[max(min(maximo, d - j - (start - i + 1)), 0)]);
}
if(j + 1 <= d){
res = max(res, dp[i % 2][j + 1]);
res = max(res, dp[i % 2][j + 1] + tabla[max(min(maximo, d - (j + 1) - (start - i + 1)), 0)]);
}
}
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
852 KB |
Output is correct |
| 6 |
Correct |
1 ms |
852 KB |
Output is correct |
| 7 |
Correct |
1 ms |
828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1488 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1488 KB |
Output is correct |
| 3 |
Correct |
8 ms |
1488 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1524 KB |
Output is correct |
| 5 |
Correct |
20 ms |
1332 KB |
Output is correct |
| 6 |
Correct |
4 ms |
980 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
9 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
4 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
26 ms |
848 KB |
Output is correct |
| 5 |
Correct |
23 ms |
864 KB |
Output is correct |
| 6 |
Correct |
6 ms |
820 KB |
Output is correct |
| 7 |
Correct |
6 ms |
860 KB |
Output is correct |
| 8 |
Correct |
5 ms |
852 KB |
Output is correct |
| 9 |
Correct |
6 ms |
868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
1480 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1564 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
936 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
