oj.uz

Submission #1011324

# Submission time Handle Problem Language Result Execution time Memory
1011324 2024-06-30T10:28:59 Z sadeep Horses (IOI15_horses) C++17
0 / 100
 12 ms 10584 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 10584 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -