Submission #1286715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286715		MMihalev	Overtaking (IOI23_overtaking)	C++20	0 / 100	1 ms	340 KiB

overtaking

#include<iostream>
#include<algorithm>
#include<vector>
#include "overtaking.h"
using namespace std;
const int MAX_N=1e3+3;
struct line
{
    long long m,c;
    long long calc(long long x){return m*x+c;}
    long double intersect(line l){return (long double)(c-l.c)/(l.m-m);}
};
vector<line>lines;
vector<int>s;
long long l,n,m,x;
long double nxtpoint[MAX_N];
int nxtid[MAX_N];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    l=L;
    n=N;
    x=X;
    m=M;
    s=S;
    vector<pair<int,int>>order;
    for(int i=0;i<n;i++)
    {
        order.push_back({W[i],i});
    }
    sort(order.begin(),order.end());
    for(int i=0;i<n;i++)
    {
        int id=order[i].second;
        line l;
        l.m=W[id];
        l.c=T[id];
        lines.push_back(l);
    }

    for(int i=0;i<n;i++)
    {
        line cur=lines[i];
        nxtpoint[i]=-1;
        for(int j=i+1;j<n;j++)
        {
            line l=lines[j];
            auto curpoint=cur.intersect(l);
            if(nxtpoint[i]==-1 or curpoint<=nxtpoint[i])
            {
                nxtpoint[i]=curpoint;
                nxtid[i]=j;
            }
        }
    }
}

long long arrival_time(long long Y)
{
    line cur;
    cur.m=x;
    cur.c=Y;

    long double point=-1;
    int id,idd=0;
    for(auto l:lines)
    {
        if(l.m>cur.m)
        {
            auto curpoint=cur.intersect(l);
            if(point==-1 or curpoint<=point)
            {
                point=curpoint;
                id=idd;
            }
        }
        idd++;
    }

    if(point>=l or point==-1)
    {
        return cur.calc(l);
    }

    long long ans;

    while(point<l && nxtpoint[id]!=-1)
    {
        ans=lines[id].calc(l);
        point=nxtpoint[id];
        id=nxtid[id];
    }

    return ans;
}

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