Submission #1119004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119004		knot222	Rice Hub (IOI11_ricehub)	C++14	0 / 100	282 ms	262144 KiB

ricehub

#include<bits/stdc++.h>
#define ll long long int
using namespace std;

ll dpl[5005][5005];
ll dpr[5005][5005];
int besthub(int R, int L, int X[], long long B) {
    for (int i=0;i<R;i++) {
        for (int j=0;j<R;j++) {
            dpl[i][j] = LLONG_MAX/3;
            dpr[i][j] = LLONG_MAX/3;
            if (j==0) {
                dpl[i][0] = 0;
                dpr[i][0] = 0;
            }
        }
    }
    for (int i=1;i<R;i++) {
        for (int j=1;j<=R;j++) {
            dpl[i][j] = min(dpl[i-1][j-1]+(X[i]-X[i-1])*(j-1), LLONG_MAX/3);
        }
    }
    for (int i=R-2;i>=0;i--) {
        for (int j=0;j<=R;j++) {
            dpr[i][j] = min(dpr[i+1][j-1]+(X[i]-X[i+1])*(j-1), LLONG_MAX/3);
        }
    }
    int best = 0;
    for (int i=0;i<R;i++) {
        int l = R-1;
        int r = 0;
        while (l>=0&&r<R) {
            if (dpl[i][l]+dpr[i][r]<=B) {
                best = max(best, l+r);
            } 
            while (dpl[i][l]+dpr[i][r+1]<=B && r<R-2) {
                r++;
            }
            l--;
        }
    }
    return best-1;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32