Submission #1025423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025423		LIF	Overtaking (IOI23_overtaking)	C++17	65 / 100	3534 ms	106580 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
long long int tt[5005][5005];
long long int ee[5005][5005];

struct node
{
    int id;
    long long int val;
};
bool cmp(node x,node y)
{
    return x.val < y.val;
}
long long int preval;
int n;
int m;
vector<int> station;
map<long long int,long long int> mp[5005]; // key ：車到第j個車站所用時間，value: 車到第j+1個車站的時間;
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    station = S;
    m = M;
    n = N;
    preval = X;
    for(int i=0;i<T.size();i++)tt[i][0] = T[i];
    for(int j=1;j<S.size();j++) // 第j個站
    {
        for(int i=0;i<N;i++) // 第i輛車
        {
            long long int s = (S[j] - S[j-1]);
            long long int cost = W[i];
            tt[i][j] = tt[i][j-1] + (s*cost);
        }
        vector<node> pp;
        for(int i=0;i<N;i++)
        {
            pp.push_back(node{i,tt[i][j-1]});
        }
        sort(pp.begin(),pp.end(),cmp);
        long long int maxn = -1;
        for(int nod = 0;nod<pp.size();nod++)
        {
            long long int fir = pp[nod].val;
            tt[pp[nod].id][j] = max(maxn,tt[pp[nod].id][j]);
            long long int max2 = (tt[pp[nod].id][j]);
            
            while(pp[nod+1].val == fir && nod+1 < pp.size())
            {
                nod++;
                tt[pp[nod].id][j] = max(maxn,tt[pp[nod].id][j]);
                max2 = max(max2,tt[pp[nod].id][j]);
            }
            maxn = max(max2,maxn);
        }
        //處理mp[j]
        for(int i=0;i<N;i++)
        {
            mp[j-1][tt[i][j-1]] = max(mp[j-1][tt[i][j-1]],tt[i][j]);
        }
    }
    /*for(int i=0;i<M;i++)
    {
        for(int j=0;j<N;j++)
        {
            cout<<tt[j][i]<<" ";
        }
        cout<<endl;
    }*/
    return;
}
long long arrival_time(long long Y)
{
    tt[n][0] = Y;
    for(int i=1;i<m;i++)
    {
        long long int s = station[i] - station[i-1];
        long long int cost = preval;
        tt[n][i] = tt[n][i-1] + (cost*s);
        auto it = mp[i-1].lower_bound(tt[n][i-1]);
        if(it != mp[i-1].begin())
        {
            tt[n][i] = max(tt[n][i],(--it)->second);
        }
    }
    
    return tt[n][m-1];
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<T.size();i++)tt[i][0] = T[i];
      |                 ~^~~~~~~~~
overtaking.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int j=1;j<S.size();j++) // 第j個站
      |                 ~^~~~~~~~~
overtaking.cpp:43:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int nod = 0;nod<pp.size();nod++)
      |                         ~~~^~~~~~~~~~
overtaking.cpp:49:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             while(pp[nod+1].val == fir && nod+1 < pp.size())
      |                                           ~~~~~~^~~~~~~~~~~

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