oj.uz

Submission #167334

# Submission time Handle Problem Language Result Execution time Memory
167334 2019-12-07T12:23:41 Z umutcangs1 Segway (COI19_segway) C++14
100 / 100
 926 ms 3184 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 31 ms 504 KB Output is correct
4 Correct 119 ms 888 KB Output is correct
5 Correct 926 ms 2544 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 9 ms 376 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 12 ms 376 KB Output is correct
11 Correct 10 ms 376 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 31 ms 504 KB Output is correct
4 Correct 119 ms 888 KB Output is correct
5 Correct 926 ms 2544 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 9 ms 376 KB Output is correct
14 Correct 9 ms 376 KB Output is correct
15 Correct 12 ms 376 KB Output is correct
16 Correct 10 ms 376 KB Output is correct
17 Correct 39 ms 532 KB Output is correct
18 Correct 68 ms 632 KB Output is correct
19 Correct 349 ms 1396 KB Output is correct
20 Correct 489 ms 1520 KB Output is correct
21 Correct 631 ms 1964 KB Output is correct
22 Correct 836 ms 2712 KB Output is correct
23 Correct 913 ms 3184 KB Output is correct