Submission #1069477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069477		boyliguanhan	Overtaking (IOI23_overtaking)	C++17	100 / 100	1580 ms	131340 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define GO(l,r) (sped*(dis[r]-dis[l]))
typedef long long ll;
map<ll,ll> station[1010];
#define MP make_pair
vector<ll> dis;
unordered_map<ll,ll>memo[1010];
ll dp[1010][1010],XTH[1010][1010],pos[1010][1010];
ll sped;
ll st[1010][1010];
int M,N2;
inline int onezsmaller(int station,ll T){
    return lower_bound(XTH[station],XTH[station]+N2+1,T)-XTH[station]-1;
}
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M_, vector<int> S){
    for(auto i:S)dis.push_back(i);
    sped=X;
    M=M_;
    for(int i=1;i<=N;i++)
        dp[i][0]=T[i-1];
    int x=clock();
    vector<int>VV(N);
    iota(VV.begin(),VV.end(),1);
    sort(VV.begin(),VV.end(),[T](int a,int b){
        return T[a-1]<T[b-1];
    });
    for(auto i:VV)
        if(W[i-1]>X)
            XTH[0][++N2]=T[i-1],
            pos[0][N2]=i;
    XTH[0][0]=-1;
    for(int j=1;j<M;j++) {for(int i=1;i<=N;i++)
        dp[i][j]=dp[i][j-1]+(dis[j]-dis[j-1])*W[i-1];
        vector<int>V(N);
        iota(V.begin(),V.end(),1);
        sort(V.begin(),V.end(),[j](int a,int b){
            return dp[a][j-1]-dp[b][j-1]?dp[a][j-1]<dp[b][j-1]:dp[a][j]<dp[b][j];
        });
        ll prv=0;
        int N22=0;
        for(auto i:V) {
            prv=dp[i][j]=max(dp[i][j],prv);
            if(W[i-1]>X)
                XTH[j][++N22]=dp[i][j],
                pos[j][N22]=i;
        }
        XTH[j][0]=-1;
    }
    int y=clock();
    for(int j=0;j<M-1;j++)
        station[j][-1]=0;
    cerr<<(y-x)/1.0/CLOCKS_PER_SEC<<'\n';
}
ll CCCALC(int STA,ll T){
    int ST=STA;
    ll org=T;
    if(memo[ST][T])
        return memo[ST][T];
    int C=onezsmaller(ST,T);
    if(XTH[M-1][C]<GO(ST,M-1)+T)
        return GO(ST,M-1)+T;
    int l=ST,r=M-1,res=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(XTH[mid][C]<GO(ST,mid)+T)
            l=mid+1,res=mid;
        else r=mid-1;
    }
    assert(res>=0);
    T+=GO(ST,res);
    ST=res;
    return memo[STA][org]=CCCALC(res+1,dp[pos[ST+1][C]][res+1]);
}
int ans,CC;
ll arrival_time(ll Y){
    ll res= CCCALC(0,Y);
    return res;
}

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:35:27: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   35 |     for(int j=1;j<M;j++) {for(int i=1;i<=N;i++)
      |                           ^~~
overtaking.cpp:37:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   37 |         vector<int>V(N);
      |         ^~~~~~
overtaking.cpp: In function 'll CCCALC(int, ll)':
overtaking.cpp:67:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |         int mid=l+r>>1;
      |                 ~^~

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