November 8, 2017

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4double eps = 1e-6;
 5
 6inline int getint() {
 7    int inp; scanf("%d", &inp); return inp;
 8}
 9
10int N;
11int len[100];
12int pos[100];
13
14int C(int level, double mid) {
15    double left = 0, right = 0;
16	
17    for (int i = N - 1; i >= level; i--) {
18		double a = pos[i], b = pos[i] + len[i];
19		double center = (a + b) / 2.0;
20
21		if(center - mid < eps)
22			left += (mid - center) * len[i];
23		else
24			right += (center - mid) * len[i];		
25    }
26
27    if (left - right < eps) {
28        return -1;
29    }
30    return +1;
31}
32
33bool solve() {
34    for (int i = N - 1; i >= 1; i--) {
35        // find center
36        double lb = 0, ub = 200;
37        for (int j = 0; j < 100; j++) {
38            double mid = (lb + ub) / 2;
39            if (C(i, mid) == -1) {
40                lb = mid;
41            }
42            else {
43                ub = mid;
44            }
45        }
46
47        double center = lb;
48        double a = pos[i - 1], b = pos[i - 1] + len[i - 1];
49
50        if (a - center <= +eps && center - b <= +eps) {
51            continue;
52        } else {
53            return false;
54        }
55    }
56
57    return true;
58}
59
60int main() {
61    int TC = getint();
62    while (TC--) {
63        N = getint();
64        for (int i = 0; i < N; i++) {
65            scanf("%d", &len[i]);
66        }
67        for (int i = 0; i < N; i++) {
68            scanf("%d", &pos[i]);
69        }
70
71        if (solve()) {
72            puts("STABLE");
73        }
74        else {
75            puts("DOWN");
76        }
77    }
78
79    return 0;
80}

 1#include <bits/stdc++.h>
 2
 3using namespace std;
 4
 5int main()
 6{
 7	int ncase;
 8	scanf("%d", &ncase);
 9
10	while(ncase--) {
11		int n, m;
12		scanf("%d %d", &n, &m);
13
14		int work[n], worker[m];
15		for(int i = 0; i < n; i++) scanf("%d", &work[i]);
16		for(int i = 0; i < m; i++) scanf("%d", &worker[i]);
17		sort(work, work + n);
18
19		priority_queue<int, vector<int>, greater<int>> pq;
20		for(int i = 0; i < m; i++) 
21			pq.push(worker[i]);
22		
23		long long ans = 0;
24		
25		for(int i = 0; i < n; i++) {
26			bool used = false;
27			while(pq.size() > 0) {
28				long long cur = pq.top(); pq.pop();
29				if(cur >= work[i]) {
30					ans += cur * cur;
31					used = true;
32					break;
33				}		
34			}
35
36			if(used == false) {
37				ans = -1;
38				break;
39			}
40		}
41
42		printf("%lld\n", ans);
43	}
44
45	return 0;
46}

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int main()
 5{
 6	int ncase;
 7	scanf("%d", &ncase);
 8	
 9	while(ncase--) {
10		int n;
11		scanf("%d", &n);
12		
13		int inp[n * 2];
14		int sum = 0;
15		for(int i = 0; i < n; i++) {
16			scanf("%d", &inp[i]);
17			inp[i + n] = inp[i];
18			sum += inp[i];
19		}
20		
21		int l = 0;
22		int mn = 0;
23		int partial = 0;
24		for(int r = 0; r < n * 2; r++) {
25			//printf("just in %d %d %d\n", l, r, partial);
26			while(r - l >= n || (partial > sum / 2 && l < r)) {
27				partial -= inp[l];
28				l++;
29				if(partial <= sum / 2)
30					mn = max(mn, partial);
31				//printf("popped %d %d %d\n", l, r, partial);
32			}
33			
34			partial += inp[r];
35			if(partial <= sum / 2)
36				mn = max(mn, partial);
37			//printf("end for %d %d %d\n", l, r, partial);
38		}
39		
40		// left must be done
41		while(l < n * 2) {
42			//printf("outer %d %d\n", l, partial);
43			partial -= inp[l];
44			l++;
45			if(partial <= sum / 2)
46				mn = max(mn, partial);
47		}
48		
49		printf("%d %d\n", mn, sum - mn);
50	}
51	return 0;
52}