제출 #990923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990923		alex_2008	추월 (IOI23_overtaking)	C++17	0 / 100	0 ms	348 KiB

overtaking

#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
vector<vector <pair<ll, ll>>> dp;
vector<vector <ll>> esim;
vector <ll> t;
vector <ll> w, s;
ll n;
ll x;
ll l;
ll m;
bool cmp(pair<ll, ll> x, pair<ll, ll> y) {
    if (x.first != y.first) return x.first < y.first;
    if (w[x.second] != w[y.second]) return w[x.second] < w[y.second];
    return x.second < y.second;
}
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    t.clear();
    w.clear();
    s.clear();
    esim.clear();
    dp.clear();
    //dp[i][j] = [1, i] avtoneri simulyaciayi jamanak (j-rd) stanciayum hertakanutyun
    m = M;
    l = L;
    x = X;
    for (auto &it : S) {
        s.push_back(it);
    }
    dp.clear();
    for (ll i = 0; i < N; i++) {
        if (W[i] > x) {
            //cout << "? " << T[i] << " " << W[i] << "\n";
            t.push_back(T[i]);
            w.push_back(W[i]);
            n++;
        }
    }
    dp.resize(m);
    esim.resize(m);
    for (ll i = 0; i < n; i++) {
        dp[0].push_back({ t[i], i });
    }
    sort(dp[0].begin(), dp[0].end(), cmp);
    for (ll j = 1; j < m; j++) {
        ll cur_mx = 0;
        for (auto& it : dp[j - 1]) {
            cur_mx = max(cur_mx, it.first + w[it.second] * 1ll * (s[j] - s[j - 1]));
            dp[j].push_back({ cur_mx, it.second });
        }
        sort(dp[j].begin(), dp[j].end(), cmp);
        map <ll, ll> mp;
        for (auto& it : dp[j]) {
            mp[it.second] = it.first;
        }
        cur_mx = 0;
        for (auto& it : dp[j - 1]) {
            cur_mx = max(cur_mx, mp[it.second]);
            esim[j].push_back(cur_mx);
        }
    }
}
ll arrival_time(ll Y) {
    ll cur_ind = 0;
    for (auto &it : t) {
        if (it < Y) cur_ind++;
    }
    if (cur_ind == 0) {
        return l * 1ll * x;
    }
    ll time = Y;
    for (ll i = 1; i < m; i++) {
        time = max(time + (s[i] - s[i - 1]) * 1ll * x, esim[i][cur_ind - 1]);
        while (cur_ind > 0 && dp[i][cur_ind - 1].first == time) {
            cur_ind--;
        }
        if (cur_ind == 0) {
            return (l - s[i]) * 1ll * x + time;
        }
    }
    return time;
}
/*
int main() {
    init(10, 1, { 5 }, { 4 }, 3, 4, { 0, 1, 4, 10 });
    cout << arrival_time(6) << "\n";
    cout << arrival_time(7) << "\n";
    cout << arrival_time(8) << "\n";
    cout << arrival_time(9) << "\n";
    cout << arrival_time(10) << "\n";
    cout << arrival_time(11) << "\n";
    cout << arrival_time(12) << "\n";
    cout << arrival_time(13) << "\n";

}
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35