Submission #1243221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243221		CyberCow	Overtaking (IOI23_overtaking)	C++20	0 / 100	1 ms	584 KiB

overtaking

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

vector<pair<long long, long long>> v[1005];
long long x, mm;
vector<long long> ss;

void init(int erk, int n, vector<long long> t, vector<int> w, int xx, int m, vector<int> s)
{
   for (int i = 0; i < s.size(); i++)
   {
      ss.push_back(s[i]);
   }
    x = xx;
    mm = m;
    int i;
    for ( i = 0; i < n; i++)
    {
        v[0].push_back({t[i], w[i]});
    }
    sort(v[0].begin(), v[0].end());
    for ( i = 0; i < m; i++)
    {
        if(i == 0)
        {
            v[1].push_back({s[1] * v[0][i].second + v[0][i].first, v[0][i].second});
        }
        else
        {
            v[1].push_back({max(s[1] * v[0][i].second + v[0][i].first, v[1].back().first), v[0][i].second});
        }
    }
    for (int h = 1; h < m; h++)
    {
        sort(v[h].begin(), v[h].end());
        for ( i = 0; i < m; i++)
        {   
            if(i == 0)
            {
                v[h + 1].push_back({(s[h + 1] - s[h]) * v[h][i].second + v[h][i].first, v[h][i].second});
            }
            else
            {
                v[h + 1].push_back({max((s[h + 1] - s[h]) * v[h][i].second + v[h][i].first, v[h + 1].back().first), v[h][i].second});
            }
        }   
    }
}
    
long long arrival_time(long long y)
{
    long long yntac = y;    
    for (int i = 0; i < mm - 1; i++)
    {
        int ind = lower_bound(v[i].begin(), v[i].end(), make_pair(yntac, x)) - v[i].begin() - 1;
        yntac = yntac + (ss[i + 1] - ss[i]) * x;
        if(ind >= 0)
            yntac = max(yntac, v[i + 1][ind].first);
    }
    return yntac;
}

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