제출 #884245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884245		charleehp	Shortcut (IOI16_shortcut)	C++14	38 / 100	198 ms	14456 KiB

shortcut

#include "shortcut.h"
#include <cstdio>

#define MAX_N 1000

using namespace std;

int N;
long long C;
long long farthestLeft[MAX_N][MAX_N];
long long farthestRight[MAX_N][MAX_N];
long long worstPair[MAX_N][MAX_N];
long long sum[MAX_N];
long long D[MAX_N];

long long summ(int i, int j) {
    return sum[j] - sum[i];
}

long long dist(int i, int j) {
    return summ(i, j) + D[i] + D[j];
}

long long farthestPair(int a, int b) {
    long long ans;

    // op1: i,j outside the cycle, same side
    long long op1 = max(worstPair[0][a], worstPair[b][N - 1]);
    //printPair(op1, op1);
    ans = op1;

    // op2: i,j outside the cycle, opposite sides
    if (a > 0 && b < N - 1) {
        long long K2 = min( C, summ(a, b) );
        long long op2 = farthestLeft[a][0] + farthestRight[b][N - 1] + K2;
        ans = max(ans, op2);
        //printPair(op2, op2);
    }

    // op3: i, inside; j, outside
    if (b < N  - 1) {
        for (int i = a; i <= b; i++) {
            long long Ki = min(summ(a, i) + C, summ(i, b)) + D[i];
            ans = max(ans, Ki + farthestRight[b][N - 1]);
            //printPair(i, Ki + farthestRight[b][N - 1]);
        }
    }

    // op4: i, outside; j, inside
    if (a > 0) {
        for (int j = a; j <= b; j++){
            long long Kj = min(summ(a, j), summ(j, b) + C) + D[j];
            ans = max(ans, Kj + farthestLeft[a][0]);
            //printPair(j,  Kj + farthestLeft[a][0]);
        }
    }

    // op5: both i and j inside
    int j = a;
    long long opA, opB;
    long long S = summ(a, b);
    //printPair(99, sum[3]);
    for (int i = a; i <= b; i++) {
        opA = summ(i, j);
        opB = S - opA + C;
        //printISum(i, opA, opB);

        while (j <= b && opA <= opB) {
            j++;
            opA = summ(i, j);
            opB = S - opA + C;
            //printJSum(j, opA, opB);
        }

        //op5.1 
        //printISum(i, 99, farthestRight[i][j - 1] + D[i]);
        if (i < j - 1)
            ans = max(ans, farthestRight[i][j - 1] + D[i]);
        //op5.2
        if (j <= b)
            ans = max(ans, summ(a, i) + C + D[i] + max(farthestLeft[b][j], D[b]));
    }

    return ans;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    // init
    N = n;
    C = (long long) c;
    for (int i = 0; i < n; i++) {
        D[i] = (long long) d[i];
    }

    for (int i = 1; i < n; i++)
        sum[i] = sum[i - 1] + (long long) l[i - 1];

    for (int i = 0; i < n; i++) {
        // farthestLeft[i][i] = D[i];
        for (int j = i - 1; j >= 0; j--) 
            farthestLeft[i][j] = max(farthestLeft[i][j + 1], dist(j, i) - D[i]);
    }
    
    for (int i = 0; i < n; i++) {
        // farthestRight[i][i] = D[i];
        for (int j = i + 1; j < n; j++) 
            farthestRight[i][j] = max(farthestRight[i][j - 1], dist(i, j) - D[i]);
    }

    for (int k = 1; k < n; k++) {
        int i = 0;
        for (int j = i + k; j < n; i++, j++) {
            worstPair[i][j] = max(worstPair[i][j - 1], worstPair[i + 1][j]);
            worstPair[i][j] = max(worstPair[i][j], dist(i, j));
        }
    }

    // find best pair to place the shortcut
    long long ans = -1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (ans == -1 || farthestPair(i, j) < ans) {
                ans = farthestPair(i, j);
                //printPair(i, j);
            }
        }
    }
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3