Submission #844124

#	Time	Username	Problem	Language	Result	Execution time	Memory
844124		Andrey	Overtaking (IOI23_overtaking)	C++17	65 / 100	3557 ms	25904 KiB

overtaking

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

long long haha[1001][1001];
vector<pair<long long,long long>> dp[1001];
vector<long long> w(0);
long long n,m,x;
vector<long long> s(0);

void init(int L, int N, std::vector<long long> t, std::vector<int> W, int X, int M, std::vector<int> S) {
    n = N;
    m = M;
    x = X;
    vector<pair<long long, long long>> wow(0);
    for(int i = 0; i < n; i++) {
        wow.push_back({W[i],t[i]});
    }
    long long l,r;
    for(int i = 0; i < n; i++) {
        w.push_back(wow[i].first);
    }
    for(int i = 0; i < m; i++) {
        s.push_back(S[i]);
    }
    for(long long i = 0; i < n; i++) {
        haha[0][i] = wow[i].second;
    }
    for(long long i = 1; i < m; i++) {
        for(long long j = 0; j < n; j++) {
            haha[i][j] = haha[i-1][j]+(s[i]-s[i-1])*w[j];
        }
        vector<pair<long long,long long>> wut(0);
        for(int j = 0; j < n; j++) {
            wut.push_back({haha[i-1][j],haha[i][j]});
        }
        sort(wut.begin(),wut.end());
        for(int j = 1; j < n; j++) {
            wut[j] = {wut[j].first,max(wut[j].second,wut[j-1].second)};
        }
        for(long long j = 0; j < n; j++) {
            dp[i].push_back(wut[j]);
            if(haha[i-1][j] > wut[0].first) {
                l = 0;
                r = n-1;
                while(l < r) {
                    int mid = (l+r+1)/2;
                    if(wut[mid].first < haha[i-1][j]) {
                        l = mid;
                    }
                    else {
                        r = mid-1;
                    }
                }
                haha[i][j] = max(haha[i][j],wut[l].second);
            }
        }
    }
    return;
}

long long arrival_time(long long y)
{
    vector<long long> ans(m);
    ans[0] = y;
    long long l,r;
    for(long long i = 1; i < m; i++) {
        ans[i] = ans[i-1]+(s[i]-s[i-1])*x;
        l = 0;
        r = n-1;
        if(ans[i-1] > dp[i][0].first) {
            while(l < r) {
                int mid = (l+r+1)/2;
                if(dp[i][mid].first < ans[i-1]) {
                    l = mid;
                }
                else {
                    r = mid-1;
                }
            }
            ans[i] = max(ans[i],dp[i][l].second);
        }
    }
    return ans[m-1];
}

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