Submission #558770

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

garage

#include <bits/stdc++.h>
// #include "laugh.h"
#define pb push_back
#define rs resize
#define debug printf("Hello\n")
#define Pi 3.141592653589793 
#define sz(a)                 ll((a).size()) 
#define all(x)                (x).begin(), (x).end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl "\n"
#define mp make_pair
#define f first
#define s second
#define vt vector
#define rst(a,b) memset((a),(b), sizeof(a))
#define FOR(a, b, c) for (ll a = (b); (a) <  (c); ++(a))
#define FORE(a, b, c) for (ll a = (b); (a) <= (c); ++(a))
#define FORR(a, b, c) for (ll a = (b); (a) >= (c); --(a))
#define umap unordered_map
#define len(a) (a).length()
#define pqueue priority_queue
 
using namespace std;
using vi = vector<int>;    
using ui = unsigned int;                
using ll = long long;                    
using pll = pair<ll,ll>;
using vll = vector<ll>;
using ull = unsigned long long;          
using pii = pair<int, int>;

bool cmp(const vt<int> &a, const vt<int> &b){
	if(a[0] != b[0])return a[0]>b[0];
	if(a[1] != b[1])return a[1]>b[1];
	return a[2] < b[2];
}
int parent[2010];
int find(int x){
	if(parent[x] == -1)return x;
	return find(parent[x]);
}


void solve(){
	 int n,m;cin >> n >> m;
	 int rate[101], w[2001], imap[2001];
	 rst(parent,-1);
	 FOR(i,1,n+1)cin >> rate[i];
	 FOR(i,1,m+1)cin >> w[i];
	 ll ans = 0;
	 queue<int> que;
	 FOR(i,0,2*m){
	 	int q;cin >> q;
	 	if(q>0){
	 		int tmp = find(1);
	 		if(tmp == n+1){
	 			que.push(q);
	 			continue;
	 		}
	 		ans += w[q]*rate[tmp];
	 		parent[tmp] = tmp + 1;
	 		imap[q] = tmp;
	 	}else{
	 		q = -q;
	 		parent[imap[q]] = -1;
	 		if(!que.empty()){
	 			int f = que.front();
	 			que.pop();
	 			int tmp = find(1);
	 			ans+=w[f]*rate[tmp];
	 			parent[tmp] = tmp + 1;
	 			imap[f] = tmp;
	 		}
	 	}
	 }
	 cout << ans << endl;
}

int main(){
	fastio;

	solve();
		
}

• Subtask 1: 100 / 100