답안 #259636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259636	2020-08-08T06:00:43 Z	lyc	Santa Claus (RMI19_santa)	C++14	20 / 100	1000 ms	1656 KB

santa

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int mxN = 96068 + 5;

int T, N, X[mxN], H[mxN], V[mxN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
	cin >> T;
	while (T--) {
		cin >> N;
		FOR(i,1,N){ cin >> X[i]; }
		FOR(i,1,N){ cin >> H[i]; }
		FOR(i,1,N){ cin >> V[i]; }
		
		int totElf = 0;
		FOR(i,1,N) if (H[i] == 0) ++totElf;
		
		FOR(i,1,N){
			int ans = -1;
		
			X[0] = -1;
			FOR(k,0,N){
				if (X[k] > X[i]) break;
			
				int cnt = 0;
				multiset<int> gifts;
				multiset<int> received;
				int rt = -1;
				FOR(j,1,N){
					if (X[j] > X[i]) break;
					rt = j;
					if (H[j] == 0) {
						gifts.insert(V[j]);
						++cnt;
					} else if (X[j] <= X[k]) {
						auto it = gifts.lower_bound(V[j]);
						if (it != gifts.end()) {
							gifts.erase(it);
							received.insert(j);
						}
					}
				}
				if (cnt != totElf) break;
				
				//~ if (k < 5) continue;
				int lt = -1;
				RFOR(j,rt,1){
					if (H[j] == 1 && received.count(j) == 0) {
						auto it = gifts.lower_bound(V[j]);
						//~ if (it != gifts.end()) TRACE(j _ V[j] _ *it);
						if (it != gifts.end()) gifts.erase(it);
						if (gifts.empty()) { lt = j; break; }
					}
				}
				
				if (lt != -1) {
					int cur = 2*X[rt]-X[lt];
					//~ TRACE(k _ cur);
					if (ans == -1 || ans > cur) ans = cur;
				} //else TRACE("");
			}
			
			cout << ans << ' ';
		}
		cout << '\n';
	}
}

Subtask #1

20.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	384 KB	Output is correct
2	Correct	377 ms	504 KB	Output is correct
3	Execution timed out	1059 ms	384 KB	Time limit exceeded
4	Execution timed out	1082 ms	512 KB	Time limit exceeded
5	Execution timed out	1073 ms	632 KB	Time limit exceeded
6	Execution timed out	1085 ms	920 KB	Time limit exceeded
7	Execution timed out	1086 ms	1144 KB	Time limit exceeded
8	Execution timed out	1087 ms	1188 KB	Time limit exceeded
9	Execution timed out	1099 ms	1528 KB	Time limit exceeded
10	Execution timed out	1098 ms	1656 KB	Time limit exceeded