Submission #1067006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067006		ZanP	Overtaking (IOI23_overtaking)	C++17	39 / 100	3567 ms	8600 KiB

overtaking

#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long

vector<vector<ll>> a;
int n,m,x;
vector<ll> s;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S)
{
    n = N; m = M; x = X;
    s.resize(m);
    for(int i = 0;i<m;i++){s[i] = (ll)S[i];}
    a.resize(m);
    vector<pair<ll,ll>> b(n);
    for(int i = 0;i<n;i++){b[i].first = -W[i]; b[i].second = (ll)T[i]; }
    sort(b.begin(), b.end());
    for(int i = 0;i<n;i++){
        a[0].push_back(b[i].second);
        //cout << "{ " << b[i].second;
        for(int j = 1;j<m;j++){
            ll n_t = a[j-1][i] + (s[j] - s[j-1])*(-b[i].first);
            for(int k = 0;k<i; k++){
                if(a[j-1][k] < a[j-1][i] && a[j][k] > n_t){
                    n_t = a[j][k];
                }
            }
            a[j].push_back(n_t);
            //cout << " - " << n_t;
        }
        //cout << "}\n";
    }
}

ll arrival_time(ll y)
{
    ll prev_t = y;
    //cout << "{ " << y;
    for(int j = 1;j<m;j++){
        ll n_t = prev_t + (s[j] - s[j-1])*x;
        for(int k = 0;k<n; k++){
            if(a[j-1][k] < prev_t && a[j][k] > n_t){
                n_t = a[j][k];
            }
        }
        prev_t = n_t;
        //cout << " - " << n_t;
    }
    //cout << "}\n";
    return prev_t;
}

// int main(){
//     init(6, 4, {20,10,40,0}, {5,20,20,30}, 10, 4, {0,1,3,6});
//     int t; cin >> t;
//     while(t--){
//         int h; cin >> h;
//         cout << arrival_time(h) << '\n';
//     }
// }

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