Submission #167334

#	Time	Username	Problem	Language	Result	Execution time	Memory
167334		umutcangs1	Segway (COI19_segway)	C++14	100 / 100	926 ms	3184 KiB

segway

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define INF 9e18
#define M (ll)(1e5+5)
const int MAXN = 20005;
typedef long long ll;
typedef vector <ll> vi;
typedef pair <ll,ll> pll;
typedef vector <pll> vpll;
ll mx(ll a,ll b){if(a>=b) return a;return b;}
ll mn(ll a,ll b){if(a<b) return a;return b;}
struct event{
    ll time,pos,who;
    bool operator<(const event &e)const{
        return time>e.time;
    }
};
priority_queue<event> evQueue;
ll n,m,t[MAXN][3],boostUntil[MAXN];
ll ahead[305],ans[MAXN],chk[305];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<3;j++)
            cin>>t[i][j];
        event f;f.time=0,f.pos=0,f.who=i;
        evQueue.push(f);
    }
    cin>>m;
    for(ll i=0;i<m;i++){
        ll x;cin>>x;
        chk[x]=1;
    }
    while(!evQueue.empty()){
        auto x=evQueue.top();
        evQueue.pop();
        vector<event> proc;
        proc.pb(x);
        while(!evQueue.empty() and evQueue.top().time==x.time){
            proc.pb(evQueue.top());
            evQueue.pop();
        }
        for(auto &i : proc){
            if(i.pos==300){
                ans[i.who]=i.time;
                continue;
            }
            ll nxtTime=i.time;
            bool good=0;
            if(boostUntil[i.who]>i.pos){
                nxtTime++;
                good=1;
            }
            else if(chk[i.pos]){
                boostUntil[i.who]=i.pos+(ahead[i.pos]%20);
                if(boostUntil[i.who]>i.pos){
                    nxtTime++;
                    good=1;
                }
            }
            if(!good)
                nxtTime+=t[i.who][i.pos/100];
            event f;f.time=nxtTime,f.pos=i.pos+1,f.who=i.who;
            evQueue.push(f);
        }
        for(auto &i : proc)
            ahead[i.pos]++;
    }
    for(ll i=1;i<=n;i++)
        cout<<ans[i]<<endl;
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45