上海市计算机学会月赛 2022年4月丙组

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
    	int y;
    	cin >> y;
    	
    	if (y % 400 == 0 || y % 4 == 0 && y % 100 != 0) {
    		cout << "Leap year";
    	}
    	else {
    		cout << "Common year";
    	}
    
    	return 0;
    }

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
    	int n, m;
    	cin >> n >> m;
    	
    	for (int i = 1; i <= n; i ++) {
    		for (int j = 1; j <= m; j ++) {
    			cout << "+-";
    		}
    		cout << "+\n";
    		
    		for (int j = 1; j <= m; j ++) {
    			cout << "| ";
    		}
    		cout << "|\n";		
    	}
    	
    	for (int j = 1; j <= m; j ++) {
    		cout << "+-";
    	}
    	cout << "+\n";	
    
    	return 0;
    }

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
    	char ch;
    	int cnt = 0, ans = 0;
    	while (cin >> ch) {
    		if (ch == '(') {
    			cnt ++;
    		}
    		else {
    			cnt --;
    			if (cnt == -1) {
    				ans ++;
    				cnt = 0;
    			}
    		}
    	}
    	cout << ans + cnt;
    
    	return 0;
    }

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 5e3 + 10;
    int n, a[N], ans = 1e9;
    
    int check(int x) {
    	int res = 0;
    	for (int i = 0; i < n; i ++) res += abs(a[i] - (x + i));
    	return res;
    }
    
    int main() {
    	scanf("%d", &n);
    	for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    	
    	for (int i = 1; i <= 5000; i ++) {
    		ans = min(ans, check(i));
    	}
    	cout << ans;
    
    	return 0;
    }

    #include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    
    const int N = 5e5 + 10;
    int n, a[N];
    
    LL check(int x) {
    	LL res = 0;
    	for (int i = 0; i < n; i ++) res += abs(a[i] - (x + i));
    	return res;
    }
    
    int main() {
    	scanf("%d", &n);
    	for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    	
    	int l = -1e9, r = 1e9, num;
    	while (l < r) {
    		int mid = l + r >> 1;
    		
    		if (check(mid - 1) >= check(mid) && check(mid) >= check(mid + 1)) {
    			l = mid;
    		}
    		else if (check(mid - 1) >= check(mid) && check(mid) <= check(mid + 1)) {
    			cout << check(mid);
    			return 0;
    		}
    		else {
    			r = mid;
    		}
    	}
    
    	return 0;
    }

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 5e5 + 10;
    int n, a[N];
    
    int main() {
    	cin >> n;
    	for (int i = 0; i < n; i ++) {
    		cin >> a[i];
    		a[i] -= i;
    	}
    	sort(a, a + n);
    	
    	long long ans = 0;
    	for (int i = 0; i < n; i ++) {
    		ans += abs(a[i] - a[n / 2]);
    	}
    	cout << ans;
    
    	return 0;
    }

    #include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    
    const int N = 5e5 + 10;
    int n, a[N];
    LL f[N];	//f[i]:在确定选a[1]的前提下，前i个数的最大数字和
    LL g[N];	//g[i]:在确定不选a[1]的前提下，前i个数的最大数字和
    
    int main() {
    	scanf("%d", &n);
    	for (int i = 1; i <= n; i ++) {
    		scanf("%d", &a[i]);
    	}
    	
    	for (int i = 3; i <= n - 1; i ++) {
    		f[i] = max(f[i - 2] + a[i], f[i - 1]);
    	}
    	
    	for (int i = 2; i <= n; i ++) {
    		g[i] = max(g[i - 2] + a[i], g[i - 1]);
    	}
    	
    	cout << max(f[n - 1] + a[1], g[n]);
    	
    	return 0;
    }