oj.uz

Submission #1011326

# Submission time Handle Problem Language Result Execution time Memory
1011326 2024-06-30T10:37:09 Z sadeep Horses (IOI15_horses) C++17
0 / 100
 32 ms 8540 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 (year == -1) {
        if (horsesLeft == 1)return 0;
        return -1;
    }

    if (cache[year][horsesLeft] != -2)return cache[year][horsesLeft];

    int maxSoFar = -1;
    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;

    dpProfitAtYearWithHorsesLeft(0, 0);

    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:56:17: warning: unused parameter 'pos' [-Wunused-parameter]
   56 | int updateX(int pos, int val) {
      |             ~~~~^~~
horses.cpp:56:26: warning: unused parameter 'val' [-Wunused-parameter]
   56 | int updateX(int pos, int val) {
      |                      ~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:60:17: warning: unused parameter 'pos' [-Wunused-parameter]
   60 | int updateY(int pos, int val) {
      |             ~~~~^~~
horses.cpp:60:26: warning: unused parameter 'val' [-Wunused-parameter]
   60 | int updateY(int pos, int val) {
      |                      ~~~~^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Incorrect 31 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Incorrect 31 ms 464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Incorrect 32 ms 444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Incorrect 32 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -