Submission #411629

#	Time	Username	Problem	Language	Result	Execution time	Memory
411629		losmi247	Horses (IOI15_horses)	C++14	34 / 100	1589 ms	20084 KiB

horses

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+23;
const int mod = 1000000007;

int n;
ll x[N],y[N];


ll dp[105][1005];
ll dajdp(){
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= 1000; j++){
            dp[i][j] = -1;
        }
    }
    dp[0][1] = 0;
    for(int i = 1; i <= n; i++){  /// nakon kraja i-te godine
        for(ll j = 0; j <= 1000; j++){   /// imam j konja posle prodavanja
            int nagore = (j+x[i]-1)/x[i];
            nagore *= x[i];
            for(ll pre = nagore; pre <= 1000; pre += x[i]){   /// koliko sam konja imao pre prodavanja
                if(dp[i-1][pre/x[i]] != -1) dp[i][j] = max(dp[i][j],dp[i-1][pre/x[i]]+(pre-j)*y[i]);
            }
        }
    }

    return dp[n][0];
}


bool cmp(int i,int j){
    if(i == j) return 0;
    if(i < j){
        ll prod = y[j];
        for(int h = i+1; h <= j; h++){ /// da li nekad prestigne ili postane jednako y[i]?
            if(x[h] >= (y[i]+prod-1)/prod) return 0;
            else prod *= x[h];
        }
        return 1;
    }
    else{
        ll prod = y[i];
        for(int h = j+1; h <= i; h++){
            if(x[h] >= (y[j]+prod-1)/prod) return 1;
            else prod *= x[h];
        }
        return 0;
    }
}

ll probaj(){
    vector <int> v;
    for(int i = 1; i <= n; i++) v.push_back(i);
    sort(v.begin(),v.end(),cmp);

    int pos = v[0];
    ll sol = 1;
    for(int i = 1; i <= pos; i++){
        sol *= x[i];
        sol %= mod;
    }
    sol *= y[pos];
    sol %= mod;

    return sol;
}


vector <ll> novx,novy;
bool cmp1(int i,int j){
    if(i == j) return 0;
    if(i < j){
        ll prod = novy[j];
        for(int h = i+1; h <= j; h++){ /// da li nekad prestigne ili postane jednako y[i]?
            if(novx[h] >= (novy[i]+prod-1)/prod) return 0;
            else prod *= novx[h];
        }
        return 1;
    }
    else{
        ll prod = novy[i];
        for(int h = j+1; h <= i; h++){
            if(novx[h] >= (novy[j]+prod-1)/prod) return 1;
            else prod *= novx[h];
        }
        return 0;
    }
}

ll probaj1(){
    novx = {0},novy = {0};
    for(int i = 1; i <= n; i++){
        novx.push_back(x[i]);
        novy.push_back(y[i]);
    }

    int cnt = 1;
    for(int i = 1; i <= n; ){   /// otarasi se jedinica u x-u, mozda ostane jedna na pocetku ali to nije problem
        int j = i;
        ll maxi = 0;
        while(j < n && novx[j+1] == 1){
            maxi = max(maxi,novy[j+1]);
            j++;
        }

        if(j != i) novy[i] = max(novy[i],maxi);

        novx[cnt] = novx[i];
        novy[cnt] = novy[i];
        cnt++;

        i = j+1;
    }
    cnt--;

    /// sad je dovoljno da uzmes maks za poslednjih 30
    vector <int> v;
    for(int i = max(1,cnt-29); i <= cnt; i++) v.push_back(i);
    sort(v.begin(),v.end(),cmp1);

    int pos = v[0];
    ll sol = 1;
    for(int i = 1; i <= pos; i++){
        sol *= novx[i];
        sol %= mod;
    }
    sol *= novy[pos];
    sol %= mod;

    return sol;
}

ll init(int n1,int *x1,int *y1){
    n = n1;
    for(int i = 1; i <= n; i++) x[i] = x1[i-1], y[i] = y1[i-1];

    /*ll pr = 1,prvi = 1;
    for(int i = 1; i <= n; i++){
        if(x[i] > 1000/pr) prvi = 0;
        else pr *= x[i];
    }
    if(n <= 10 && prvi){
        return dajdp();
    }*/

    /*if(n <= 2000)*/ return probaj1();

}

ll updateX(int pos,int val){
    pos++;

    //if(n <= 2000){
        x[pos] = val;
        return probaj1();
    //}

}

ll updateY(int pos,int val){
    pos++;

    //if(n <= 2000){
        y[pos] = val;
        return probaj1();
    //}
}

/*int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int a;
    cin >> a;
    int *prvi = (int*)malloc(sizeof(int)*a);
    int *drugi = (int*)malloc(sizeof(int)*a);
    for(int i = 1; i <= a; i++){
        int x;
        cin >> x;
        prvi[i-1] = x;
    }
    for(int i = 1; i <= a; i++){
        int x;
        cin >> x;
        drugi[i-1] = x;
    }

    cout << init(a,prvi,drugi) << endl;

    cout << updateY(1,2) << endl;
}*/

Compilation message (stderr)

horses.cpp: In function 'll dajdp()':
horses.cpp:21:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   21 |             int nagore = (j+x[i]-1)/x[i];
      |                          ~~~~~~~~~~^~~~~
horses.cpp:22:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   22 |             nagore *= x[i];
      |             ~~~~~~~^~~~~~~

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