Submission #1011324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011324		sadeep	Horses (IOI15_horses)	C++17	0 / 100	12 ms	10584 KiB

horses

#include "horses.h"

int N;
int *X;
int *Y;

int max(int a,int b) { if (a>b) return a; return b; }


const int MAX_HORSES = 1001;
int cache[12][MAX_HORSES + 1];

int dpProfitAtYearWithHorsesLeft(int year, int horsesLeft) {
    if (cache[year][horsesLeft] != -2)return cache[year][horsesLeft];

    if (year == -1) {
        if (horsesLeft == 1)return 0;
        return -1;
    }

    int maxSoFar = -2;
    for (int lastYearHorseCount = 0; lastYearHorseCount < MAX_HORSES; lastYearHorseCount++) {
        int thisYearHorseCountBeforeSell = lastYearHorseCount * X[year];
        if (thisYearHorseCountBeforeSell < horsesLeft)continue;

        int horsesToSell = thisYearHorseCountBeforeSell - horsesLeft;
        int profitUptoLastYear = dpProfitAtYearWithHorsesLeft(year - 1, lastYearHorseCount);
        if (profitUptoLastYear < 0)continue;
        int profit = horsesToSell * Y[year] + dpProfitAtYearWithHorsesLeft(year - 1, lastYearHorseCount);

        maxSoFar = max(maxSoFar, profit);
    }

    cache[year][horsesLeft] = maxSoFar;
    return cache[year][horsesLeft];
}

int init(int n, int xx[], int yy[]) {
    for (auto &c: cache)for (int &i: c)i = -2;

    N = n;
    X = xx;
    Y = yy;

    int maxSoFar = 0;
    for(int i=0; i<MAX_HORSES; i++){
        maxSoFar = max(maxSoFar, dpProfitAtYearWithHorsesLeft(N, i));
    }

    return maxSoFar;
}

int updateX(int pos, int val) {
    return 0;
}

int updateY(int pos, int val) {
    return 0;
}

Compilation message (stderr)

horses.cpp: In function 'int updateX(int, int)':
horses.cpp:53:17: warning: unused parameter 'pos' [-Wunused-parameter]
   53 | int updateX(int pos, int val) {
      |             ~~~~^~~
horses.cpp:53:26: warning: unused parameter 'val' [-Wunused-parameter]
   53 | int updateX(int pos, int val) {
      |                      ~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:57:17: warning: unused parameter 'pos' [-Wunused-parameter]
   57 | int updateY(int pos, int val) {
      |             ~~~~^~~
horses.cpp:57:26: warning: unused parameter 'val' [-Wunused-parameter]
   57 | int updateY(int pos, int val) {
      |                      ~~~~^~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23