Submission #155779

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
155779	2019-09-30T13:56:01 Z	m1sch3f	Garage (IOI09_garage)	C++17	100 / 100	5 ms	376 KB

garage

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

// types - only for stuff used a lot 
using ll = long long;
#define vv vector
#define Pp pair

// IO
#define get(x) scanf("%d",&x)
#define getl(x) scanf("%lld",&x);

// Operations
#define pb push_back
#define pob pop_back
#define sz(a) int(a.size()) 
#define re(a,b) a=max(a,b) // relax
#define ri(a,b) a=min(a,b) // relaxi

// Debugging

#ifndef LOCAL
#define cerr if (0) cerr
#else
#define cerr cout
#endif

#define print(arr,n) {for (int _ = 0; _ < n; _++) cerr<<arr[_]<<" "; cerr << endl; }
#define printv(vec)  {for (int _ : vec) cerr<<_<<" "; cerr<<endl;}

const int mod = 1e9+7, oo = 1e9;
const ll loo = 1e18;

// Functions 
ll modpow(ll a, ll b) {
	ll ans = 1; // faster modpow than recursive
	for (; b; b/=2,a=a*a%mod)
		if (b&1) ans = (ans*a)%mod;
	return ans;
}
ll gcd(ll a, ll b) {
	while (a) b%=a,swap(a,b);
	return b;
}
#define bitcount __builtin_popcountll
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)


/* 

   ALRIGHT HACKERS, THIS IS WHERE THE ACTUAL CODE BEGINS

 */

const bool DEBUG = 1;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

#ifdef LOCAL
	if (DEBUG) freopen("input.txt", "r", stdin);
	if (DEBUG) freopen("output.txt", "w", stdout);
	clock_t start = clock();
#endif

	int n,m; cin>>n>>m;
	int s[n];
	f(i,0,n) cin>>s[i];
	int w[m];
	f(i,0,m) cin>>w[i];
	
	ll ans = 0;
	priority_queue<int,vector<int>,greater<int>> pq;
	queue<int> ppq;
	f(i,0,n) pq.push(i);
	int a[m];
	fill(a,a+m,-1);
	f(e,0,2*m) {
		int x; cin>>x;
		if (x<0) {
			x = -x-1;
			pq.push(a[x]);	
			a[x] = -2;
		} else ppq.push(x-1);
		while (pq.size() && ppq.size()) {
			int v = ppq.front(); ppq.pop();
			if (a[v] != -2) {
				int i = pq.top(); pq.pop();
				a[v] = i;
				ans += 1LL*w[v]*s[i];
			}	
		}
	}	
	cout << ans << endl;

#ifdef LOCAL
	cout << setprecision(12) << (long double)(clock()-start) / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 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	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	372 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	3 ms	376 KB	Output is correct
17	Correct	3 ms	376 KB	Output is correct
18	Correct	3 ms	376 KB	Output is correct
19	Correct	3 ms	376 KB	Output is correct
20	Correct	3 ms	376 KB	Output is correct