Submission #1119022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119022		knot222	Rice Hub (IOI11_ricehub)	C++14	42 / 100	365 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;
            }
            if (j==1) {
                dpl[i][1] = 0;
                dpr[i][1] = 0;
            }
        }
    }
    ll one = 1;
    for (int i=1;i<R;i++) {
        for (int j=1;j<=R;j++) {
            dpl[i][j] = min(dpl[i-1][j-1]+one*(X[i]-X[i-1])*(j-1), LLONG_MAX/3);
        }
    }
    for (int i=R-2;i>=0;i--) {
        for (int j=1;j<=R;j++) {
            dpr[i][j] = min(dpr[i+1][j-1]+one*(X[i+1]-X[i])*(j-1), LLONG_MAX/3);
        }
    }
    int best = 0;
    for (int i=0;i<R;i++) {
        int l = R;
        int r = 0;
        while (l>=0&&r<=R) {
            while (dpl[i][l]+dpr[i][r+1]<=B && r<R) {
                r++;
            }
            if (dpl[i][l]+dpr[i][r]<=B) {
                best = max(best, l+r-1);
            } 
            l--;
        }
    }
    /*
    for (int i=0;i<6;i++) {
        for (int j=0;j<6;j++) {
            cout << dpl[i][j] << ' ';
        }
        cout << endl;
    }
    for (int i=0;i<6;i++) {
        for (int j=0;j<6;j++) {
            cout << dpr[i][j] << ' ';
        }
        cout << endl;
    }*/
    return best;
}

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