oj.uz

Submission #777831

# Submission time Handle Problem Language Result Execution time Memory
777831 2023-07-09T17:38:53 Z mindiyak Garage (IOI09_garage) C++14
100 / 100
 2 ms 340 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct