Submission #841683

#	Time	Username	Problem	Language	Result	Execution time	Memory
841683		7mody	Overtaking (IOI23_overtaking)	C++17	39 / 100	3507 ms	8344 KiB

overtaking

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

vector<pair<ll,ll>> arr;
vector<vector<ll>> s;
vector<ll> station;
ll all,n,x,m;

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    n=N;all=L;x=X;m=M;;
    for(int i=0; i < n;i++){
        arr.push_back({W[i],(ll)T[i]});
    }
    s.resize(m);
    for(int i=0; i  < m;i++){
        
    }
    station.resize(m);
    for(int i=0; i < m;i++){
        station[i]=ll(S[i]);
    }
    sort(arr.begin(),arr.end());
    reverse(arr.begin(),arr.end());
    for(int i=0; i < m;i++){
        s[i].resize(n);
    }
    for(int i=0; i < n;i++) s[0][i]=arr[i].second;
    for(int i=1; i < m;i++){
        ll length=S[i]-S[i-1];
        for(int j=0; j < n;j++){
            ll start=s[i-1][j];
            ll expected=start+(arr[j].first * length);
            ll actual=expected;
            for(int k=j-1; k >=0;k--){
                if(s[i-1][k] < start && s[i][k] > expected) actual=max(actual,s[i][k]);    
            }
            s[i][j]=actual;
        }
    }
}

long long arrival_time(long long Y)
{
    ll ans=Y;
    for(int i=1; i < m;i++){
        ll length = station[i]-station[i-1];
        ll expected=ans + (x*length);
        ll curr=expected;
        for(int j=0; j < n;j++){
            if(s[i-1][j] < ans && s[i][j] > expected) curr=max(curr,s[i][j]);
        }
        ans=curr;
    }
    return ans;
}

// void solve(){
//     int l,q; cin >> l >> n >> x >> m >> q;
//     vector<ll> T(n);
//     vector<int> W(n);
//     for(int i=0; i < n;i++) cin >> T[i];
//     for(int i=0; i < n;i++) cin >> W[i];
//     vector<int> S(m);
//     for(int i=0; i < m;i++) cin >> S[i];
//     init(l,n,T,W,x,m,S);
//     while(q--){
//         ll temp; cin >> temp;
//         cout << arrival_time(temp) << endl;
//     }
// }

// int main(){
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     cout.tie(NULL);
//     int t=1;
//     // cin >> t;
//     while(t--) solve();
//     return 0;
// }

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