제출 #1154412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154412		Zheing	Horses (IOI15_horses)	C++20	17 / 100	1594 ms	12260 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

const int MOD = 1e9 + 7;

vector<int> X, Y;
vector<long long> product;
long long max_profit;

int modInv(int a) {
    int b = MOD - 2, res = 1;
    while (b > 0) {
        if (b & 1) 
            res = (1LL * res * a) % MOD;
        a = (1LL * a * a) % MOD;
        b >>= 1;
    }
    return res;
}

void computeMax() {
    max_profit = 0;
    for (int i = 0; i < (int)product.size(); ++i) {
        long long current = (product[i] * Y[i]) % MOD;
        if (current > max_profit)
            max_profit = current;
    }
}

int init(int N, int* x, int* y) {
    X.resize(N);
    Y.resize(N);
    product.resize(N);
    for (int i = 0; i < N; ++i) {
        X[i] = x[i];
        Y[i] = y[i];
    }
    product[0] = X[0] % MOD;
    for (int i = 1; i < N; ++i) {
        product[i] = (product[i-1] * X[i]) % MOD;
    }
    computeMax();
    return max_profit % MOD;
}

int updateX(int pos, int val) {
    int old_val = X[pos];
    X[pos] = val % MOD;
    int inv_old = modInv(old_val);
    long long ratio = (1LL * val * inv_old) % MOD;
    
    product[pos] = (product[pos] * ratio) % MOD;
    for (int i = pos + 1; i < (int)product.size(); ++i) {
        product[i] = (product[i] * ratio) % MOD;
    }
    
    computeMax();
    return max_profit % MOD;
}

int updateY(int pos, int val) {
    Y[pos] = val % MOD;
    computeMax();
    return max_profit % MOD;
}

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