Submission #572583

#	Time	Username	Problem	Language	Result	Execution time	Memory
572583		Leo121	Holiday (IOI14_holiday)	C++14	47 / 100	26 ms	1564 KiB

holiday

#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;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53