Submission #851110

#	Time	Username	Problem	Language	Result	Execution time	Memory
851110		oneloveforever	Overtaking (IOI23_overtaking)	C++17	65 / 100	3547 ms	63356 KiB

overtaking

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
const int MAXN=1e3+7;
set<pair<long long ,long long> >place[MAXN];
ll M,X;
vector<int>S;
void init(int L,int N,vector<long long>T,vector<int>W,int _X,int _M,vector<int>_S)
{
    M=_M;
    X=_X;
    S=_S;
    vector<pair<long long,long long> >block;
    for(int i=0;i<=N-1;i++)block.push_back({W[i],T[i]});
    sort(block.begin(),block.end());
    for(int i=0;i<=M-1;i++)place[i].insert(make_pair(0,0));
    for(int i=(int)block.size()-1;i>=0;i--)
    {
        long long Time=block[i].y;
        long long C=block[i].x;
        for(int cnt=1;cnt<=M-1;cnt++)
        {
            auto pre=prev(place[cnt].lower_bound(make_pair(Time,0)));
            long long newTime=max(pre->y,(long long)Time+C*(S[cnt]-S[cnt-1]));
            place[cnt].insert(make_pair(Time,newTime));
            Time=newTime;
        }
    }
}
long long arrival_time(long long Time)
{
    for(int cnt=1;cnt<=M-1;cnt++)
    {
        auto pre=prev(place[cnt].lower_bound(make_pair(Time,0)));
        long long newTime=max(pre->y,(long long)Time+X*(S[cnt]-S[cnt-1]));
        Time=newTime;
    }
    return Time;
}
/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int L,N;
    vector<long long>T;
    vector<int>W;
    int X,M;
    vector<int>S;
    cin>>L>>N;
    for(int i=1;i<=N;i++)
    {
        long long value;
        cin>>value;
        T.push_back(value);
    }
    for(int i=1;i<=N;i++)
    {
        long long value;
        cin>>value;
        W.push_back(value);
    }
    cin>>X>>M;
    for(int i=1;i<=M;i++)
    {
        int value;
        cin>>value;
        S.push_back(value);
    }
    init(L,N,T,W,X,M,S);
    int Time;
    cin>>Time;
    cout<<arrival_time(Time);
}
*/

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