Submission #777831

#	Time	Username	Problem	Language	Result	Execution time	Memory
777831		mindiyak	Garage (IOI09_garage)	C++14	100 / 100	2 ms	340 KiB

garage

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

/* clang-format off */

/* TYPES  */
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vb vector<bool>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>

/* FUNCTIONS */
#define f(i,s,e) for(long long int i=s;i<e;i++)
#define cf(i,s,e) for(long long int i=s;i<=e;i++)
#define rf(i,e,s) for(long long int i=e-1;i>=s;i--)
#define forn(i,n) for(long long int i=0; i<n; i++)
#define pb push_back

/* PRINTS */
template <class T>
void print_v(vector<T> &v) { cout << "{"; for (auto x : v) cout << x << ","; cout << "\b}"; }

/* UTILS */
#define MOD 1000000007
#define PI 3.1415926535897932384626433832795
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) if (a%i==0) return 0; return 1; }
void yes() { cout<<"YES\n"; }
void no() { cout<<"NO\n"; }
#define op() ios_base::sync_with_stdio(0);cin.tie(0);//cout.tie(0);

/*  All Required define Pre-Processors and typedef Constants */
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;


/* clang-format on */


void solve(){

    int N,M;cin>>N>>M;
    ll cost = 0;
    int pos = 0;
    vll rate(N);
    vb parking(M,false);
    vll parked_pos(M,-1);
    queue<ll> wait;

    forn(i,N){
        cin >> rate[i];
    }

    vll cars(M);
    forn(i,M){
        cin >> cars[i];
    }

    f(i,0,(2*M)){
        int id;cin >> id;
        //cout << i << " " << id << " " << cost << endl;
        if(id > 0){
            if(pos >= N){
                wait.push(id);
            }else{
                cost += rate[pos] * cars[id-1];
                parking[pos] = true;
                parked_pos[id-1] = pos;
                //cout << "Parked " << id-1 << " " << parked_pos[id-1] << " at " << pos << " next parking spot ";
                while(parking[pos] == true){
                    pos += 1;
                    if(pos >= N){
                        pos = N;
                        break;
                    }
                }
                //cout << pos << endl;
            }
        }else{
            id = -id;
            id --;
            //cout << id << " vehicle removing from " << parked_pos[id] << " new lowest point ";
            pos = min(parked_pos[id],pos);
            //cout << pos << endl;
            parking[parked_pos[id]] = false;
            parked_pos[id] = -1;

            if(wait.empty() != true){
                id = wait.front();
                wait.pop();
                cost += rate[pos] * cars[id-1];
                parking[pos] = true;
                parked_pos[id-1] = pos;
                //cout << "Parked " << id-1 << " " << parked_pos[id-1] << " at " << pos << " next parking spot ";
                while(parking[pos] == true){
                    pos += 1;
                    if(pos >= N){
                        pos = N;
                        break;
                    }
                }
                //cout << pos << endl;
            }
        }
    }


    cout << cost << endl;
}





/* Main()  function */
int main()
{
    // op();
	int tc = 1;
	// cin >> tc;

	while(tc--){
        solve();
	}
	return 0;
}
/* Main() Ends Here */

• Subtask 1: 100 / 100