제출 #1240957

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

horses

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

const int M = 1000000007;

vector<int> x, y, prices;
vector<long long> horses;

int find_max(){
    int ma = 0;
    for(auto r : prices){
        ma = max(r, ma);
    }
    return ma;
}

int init(int N, int X[], int Y[]){
    x.resize(N);
    y.resize(N);
    horses.resize(N);
    prices.resize(N);

    for(int i = 0; i < N; i++){
        x[i] = X[i] % M;
        y[i] = Y[i] % M;

        if(i == 0){
            horses[i] = (long long) x[i];
            long long cost = (horses[i] * y[i]) % M;
            prices[i] = (int) cost;
            continue;
        }
        horses[i] = ((long long) x[i] * horses[i-1]) % M;
        long long cost = (horses[i] * y[i]) % M;
        prices[i] = (int) cost;
    }
    return find_max();
}

int updateX(int pos, int val){
    x[pos] = val % M;
    if(pos == 0){
        horses[0] = (long long) x[pos] % M;
        prices[0] = (int) (((long long) (y[0] % M) * horses[0]) % M);

        for(int i = 1; i <  x.size(); i++){
            horses[i] = ((long long) (x[i] % M) * horses[i-1]) % M;
            long long cost = ((long long) (y[i] % M) * horses[i]) % M;
            prices[i] = (int) cost;
        }

    } else {

        horses[pos] = ((long long) (x[pos] % M) * horses[pos-1]) % M;
        long long cost = ((long long) (y[pos] % M) * horses[pos]) % M;
        prices[pos] = (int) cost;

        for(int i = pos; i < x.size() - 1; i++){
            horses[i+1] = (horses[i]  * (long long) (x[i+1] % M)) % M;
            cost = (horses[i+1] * (y[i+1] % M)) % M;
            prices[i+1] = int(cost);
        }
    }
    return find_max();
}
int updateY(int pos, int val){
    y[pos] = val;
    long long cost = (horses[pos] * y[pos])% M;
    prices[pos] = (int) cost;
    /* for(int i = 0; i < x.size(); i++){
        cout << y[i] << ' '; 
    }
    cout << '\n'; */
    return find_max();
}

/* int main(){
    int X[] = {2, 1, 3};
    int Y[] = { 3, 4, 1};
    cout << init(3, X, Y) << '\n';
    
    int m;
    cin >> m;
    
    while(m--){
        int type, pos, val;
        cin >> type >> pos >> val;
        if(type == 1){
            cout << updateX(pos, val) << '\n';
        } else {
            cout << updateY(pos, val) << '\n';
        }
    }
    return 0;    
} */

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