Submission #675045

#	Time	Username	Problem	Language	Result	Execution time	Memory
675045		Hacv16	Horses (IOI15_horses)	C++17	17 / 100	16 ms	10624 KiB

horses

#include <bits/stdc++.h>
using namespace std;

#define fr first
#define sc second

typedef long long ll;
const int MAX = 1010;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

int n, memo[15][MAX], x[15], y[15];

int dp(int i, int j){
    if(memo[i][j] != -1) return memo[i][j];
    if(i == n + 1) return 0;

    int ans = -INF;

    for(int sell = 0; sell <= j; sell++){
        int cur = dp(i + 1, (j - sell) * x[i + 1]) + sell * y[i];
        ans = max(ans, cur);
    }

    return memo[i][j] = ans;
}

int init(int _n, int _x[], int _y[]){
    n = _n; 

    for(int i = 1; i <= n; i++)
        x[i] = _x[i - 1], y[i] = _y[i - 1];

    memset(memo, -1, sizeof(memo));

    return dp(1, x[1]);
}

int updateX(int pos, int val){
    pos++; x[pos] = val;
    return dp(1, x[1]);
}

int updateY(int pos, int val){
    pos++; y[pos] = val;
    return dp(1, x[1]);
}

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