akhauriyash/Code-Regression huggingface dataset:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13
 
# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''
 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 ############ ---- Input Functions ---- #######End
 # #####   

def pr_list(a):
	print(*a, sep=" ")
def main():
	# tests =  inp()
	tests = 1
	mod = 1000000007
	limit = 10**18
	ans = 0
	start = {}
	for test in range(tests):
		[n,k] = inlt()
		a = inlt()
		dp = [0 for i in range(k+1)]
		for i in range(k+1):
			flag = 0
			for j in a:
				if i-j<0:
					break
				if dp[i-j] == 0:
					flag = 1
					break
			dp[i] = flag
		if dp[k] == 1:
			print("First")
		else :
			print("Second")
				





		
		


if __name__== "__main__":
	main()

Measured memory_bytes: 79104
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np


# なんこか入力
n,m = map(int, input().split())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = []

a= set(a)
b= set(b)
if len(a) != n or len(b) != m:
    print("0")
    exit()
    
t=1
ax = 0
bx = 0

for i in range(n*m,0,-1):

    if i in a and i in b:
        ax += 1
        bx += 1
    elif i in a:
        ax += 1
        t = t * bx % (1000000007)
    elif i in b:
        bx += 1
        t = t * ax % (1000000007)
    else:
        t = t * (ax*bx-n*m+i) % (1000000007)
    
print(t)



Measured memory_bytes: 14500
#include "bits/stdc++.h"
using namespace std;
#define INF 1e9
#define rep(i, n) for(int i=0;i<n;i++)
#define ALL(x) (x).begin(), (x).end()  //昇順
#define RALL(x) (x).rbegin(), (x).rend() // 降順
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
const long long mod = 1e9+7;
typedef priority_queue<int> PQ;
typedef vector<long long> VL;
typedef vector<bool> VB;
typedef vector<int> VI;  // VI a(n);
typedef vector<string> VS;  
typedef vector<char> VC; 
typedef vector<VS> VSS;
typedef vector<VC> VCC;    
typedef vector<VI> VII;   // VII a(n,vector<int>(m)) n * m 
typedef vector<VL> VLL;
typedef pair<int, int> PII;
typedef map<int, int> MP;   //MP a;
typedef vector<pair<int, int> > PS;
typedef long long ll;  //ll とdoubleは違う
template <class T>  // chmax(max, a);
bool chmax(T &a, T b){
    if (a < b){ a = b;return 1;}
    return 0;
}
template <class T> //chmin(min,a)
bool chmin(T &a, T b){
    if (b < a){ a = b; return 1;}
    return 0;
}
template<typename T>   // operator << (cout,a);
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}
   
// g++ -std=c++11 prac.cpp
ll Max=-1e9,Min=1e9+1;

int main(){
    int a,b,d,x,y=0,z,m,k,w,l_sum=0,r_sum=0,ans=0;
    string s,t;
    bool count=true,ok=true;
    cin >> s >> a; 
    rep(i,s.size()){
        if(i%a==0){
            cout << s[i];
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;

int sumdigits(int N){
    int sum = 0;

    while(N > 0){
        sum += N % 10;
        N /= 10;
    }
    return sum;
}

int main() {
    int n; cin >> n;

    if(n % sumdigits(n) == 0)print("Yes");
    else print("No");
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <math.h>
#include <algorithm>
using namespace std;

typedef long long ll;
const int maxn = 200200;

void solve()
{
    int n,k;
    cin >> n >> k;
    int a[n + 1];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a,a + n);
    ll ans = 0;
    for (int i = 0; i < n - k; i++)
        ans += a[i];
    cout << ans << endl;
}



int main()
{
    int t;
    solve();
    return (0);
}





Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	string S;
	int flag = 0;
	cin >> S;
	for (int i = 0; i < ((int)S.length());i++){
		if (i % 2 == 0){//odd number
			if (S[i] == 'L'){
				flag = 1;
				break;
			}
		}
		else{//even number
			if (S[i] == 'R'){
				flag = 1;
				break;
			}
		}
	}
	if (flag == 1)
		cout << "No" << endl;
	else
		cout << " Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int main(){
	int n;
	cin>>n;
	vi a(n);
	rep(i ,n) cin>>a[i], a[i]--;
	ll  sum = 0LL;
	rep(i, n){
		if(a[a[i]] == i) sum++;
	}
	cout<<sum/2<<endl;

}

Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>

static const int MAXN = 2e5 + 4;
static const int ALPHA = 26;

static int n;
static char s[MAXN];
static std::vector<int> occ[ALPHA];
static std::vector<std::pair<int, int>> p;
static int dest[MAXN];

namespace bit {
    int t[MAXN];
    inline void add(int pos) { for (++pos; pos < MAXN; pos += (pos & -pos)) t[pos] += 1; }
    inline int sum(int rg) { int ans = 0; for (++rg; rg; rg -= (rg & -rg)) ans += t[rg]; return ans; }
    inline int sum(int lf, int rg) { return sum(rg) - sum(lf); }
}

int main()
{
    scanf("%s", s);
    n = strlen(s);

    for (int i = 0; i < n; ++i) occ[s[i] - 'a'].push_back(i);

    int odd = -1;
    for (int i = 0; i < ALPHA; ++i) {
        if (occ[i].size() & 1) {
            if (odd == -1) odd = i;
            else {puts("-1"); return 0; }
        }
        for (int j = 0; j < occ[i].size() / 2; ++j)
            p.push_back({ occ[i][j], occ[i][occ[i].size() - 1 - j] });
    }
    std::sort(p.begin(), p.end(), [] (const std::pair<int, int> a, const std::pair<int, int> b) {
        return std::min(a.first, n - 1 - a.second) < std::min(b.first, n - 1 - b.second);
    });

    for (int i = 0; i < n / 2; ++i) {
        dest[p[i].first] = i;
        dest[p[i].second] = n - 1 - i;
    }
    if (odd != -1) dest[occ[odd][occ[odd].size() / 2]] = n / 2;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += bit::sum(dest[i], n);
        bit::add(dest[i]);
    }

    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 4596
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
using namespace std;

long long int a[1000000];
int n;
long long int hoge(int che){
	long long int d[100000];
	for(int i=0;i<n;i++){
		d[i]=a[i]%che;
	}
	sort(d,d+n);
	//	for(long long int i=0;i<n;i++){cout<<d[i]<<endl;}
	int bid=-1;int lid=n;
	long long int b=0;long long int l=0;
	while(bid!=lid-1){
		if(l>=b){bid++;b+=d[bid];}
		else{lid--;l+=(che-d[lid]);}
	}
	return l;
}


int main(){
	long long int sum=0;
	cin>>n;
	long long int k;cin>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	if(n==1){cout<<a[0]<<endl;return 0;}
	long long int div[100000];
	int id=-1;
	for(long long int i=1;i<=sqrt(sum);i++){
		if(sum%i==0){
			id++;
			div[id]=i;
			if(i*i!=sum){id++;div[id]=sum/i;}
		}
	}
	sort(div,div+id+1);

	long long int OK=0;
	for(int i=0;i<=id;i++){
		if(hoge(div[i])<=k){OK=i;}
	}
	cout<<div[OK]<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int a = Integer.parseInt(scan.next());
		int b = Integer.parseInt(scan.next());
		
		if(a * b == 15) {
			System.out.println("*");
		}else {
			if (a + b == 15) {
				System.out.println("+");
			}else {
				System.out.println("x");
			}
		}
		scan.close();
	}
}

Measured memory_bytes: 21716
S = list(input())
T = list(input())
ls = len(S)
lt = len(T)
count = 0
judge = 0

for i in range(ls - lt + 1):
    for j in range(lt):
        if S[i + j] == '?' or S[i + j] == T[j]:
            count += 1

    if count == lt:
        rep = i
        judge = 1
    
    count = 0

if judge == 0:
    print('UNRESTORABLE')
else:
    for i in range(lt):
        S[rep + i] = T[i]
    S = ''.join(S)
    print(S.replace('?','a'))

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)

template<class T> inline bool change_min(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;
int N;
long long W;
long long w[110];
int v[110];
long long dp[110][100100];

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> W;
    REP(i, N) {
        cin >> w[i] >> v[i];
    }

    REP(i, 110) REP(j, 100100) {
        dp[i][j] = INF;
    }

    dp[0][0] = 0;

    REP(i, N) REP(j, 100100) {
        if (j - v[i] >= 0) {
            change_min(dp[i + 1][j], dp[i][j - v[i]] + w[i]);
        }
        change_min(dp[i + 1][j], dp[i][j]);
    }

    int ans = 0;
    REP(j, 100100) {
        if (dp[N][j] <= W) {
            ans = j;
        }
    }

    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 86272
#include<iostream>
using namespace std;

int main(){

	int card[4][13]={0},n,N; //????¬?????????????????????????????????¨?????¨?????§??\??????????????????????????£???????????§???????????????
	char M;
	cin >> n;

	for(int i=0; n>i; i++){ //????????????S?????????????????????H?????????????????????C?????????????????????D???????????¨??????
		cin >> M >> N;
		if(M == 'S')card[0][N-1]=1;
		else if(M == 'H')card[1][N-1]=1;
		else if(M == 'C')card[2][N-1]=1;
		else if(M == 'D')card[3][N-1]=1;
	}

	for(int i=0; 4>i; i++){
		for(int j=0; 13>j; j++){
			if(card[i][j]==0){
				if(i==0)cout << "S" << " " << j+1 << endl;
				else if(i==1)cout << "H" << " " << j+1 << endl;
				else if(i==2)cout << "C" << " " << j+1 << endl;
				else if(i==3)cout << "D" << " " << j+1 << endl;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define inN(A) cin>>n;for(i=0;i<n;++i)cin>>A[i];
#define rep(i,a,b) for(i=a;i<b;++i)
#define repn for(i=0;i<n;++i)
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define sd second
#define ft first
#define vi vector<int>
#define vpii vector<pair<int,int> >
#define TC //int T;cin>>T;while(T--)
#define n_max 100001
#define mod 1000000007

int main() {
    int a,b,n,p,k,i,j,m;
    TC
    {
    	cin>>n;
    	string s;int A[4]={0};
    	repn
    	{
    		cin>>s;
    		if(s[0]=='A')A[0]++;
    		else if(s[0]=='W')A[1]++;
    		else if(s[0]=='T')A[2]++;
    		else A[3]++;
    	}
    	cout<<"AC x "<<A[0]<<"\n";
    	cout<<"WA x "<<A[1]<<"\n";
    	cout<<"TLE x "<<A[2]<<"\n";
    	cout<<"RE x "<<A[3]<<"\n";
    }
}



Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


signed main() {
  int A, B;
  cin >> A >> B;

  REP(i, 100000){
    if(int(i*0.08) == A && int(i*0.1) == B){
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
L = []
for i in range(N):
  if(i != N-1):
    L.append(A[i+1] - A[i])
  else:
    L.append(K - A[i] + A[0])
maxL = max(L)
print(K - maxL)

Measured memory_bytes: 26420
#include <bits/stdc++.h>
#define ls k<<1,l,mid
#define rs k<<1|1,mid+1,r
#define mp(x,y) make_pair(x,y)
#define r(x) read(x)
#define rrr(x,y,z) read(x);read(y);read(z)
#define FOR(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
typedef long long LL;
typedef pair<int,int> pt;
const int N=2e5+5;
const int M=2e3+5;
const int INF=0x7fffffff;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1);
LL n,m;
template<class T>
inline void read(T &x)
{
    char c; x=1;
    while((c=getchar())<'0'||c>'9') if(c=='-') x=-1;
    T res=c-'0';
    while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
    x*=res;
}
LL qpow(LL a,LL p)
{
    LL res=1;
    while(p){
        if(p&1) res=res*a%mod;
        a=a*a%mod;
        p>>=1;
    }
    return res;
}
LL inv(LL x)
{
    return qpow(x,mod-2);
}
LL hhh(LL a,LL b)
{
    a++; b++;
    LL res=1;
    FOR(i,1,a){
        res=res*(a+b-i+1)%mod;
    }
    FOR(i,1,a){
        res=res*inv(i)%mod;
    }
    return (res-1+mod)%mod;
}
int main()
{
    LL r1,r2,c1,c2;
    rrr(r1,c1,r2); r(c2);
    LL a1=hhh(r2,c2);
    LL a2=hhh(r1-1,c1-1);
    LL a3=hhh(r1-1,c2);
    LL a4=hhh(r2,c1-1);
    cout<<(a1+a2-a3-a4+mod+mod)%mod<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int N,K;
    ll R,S,P;
    string T;
    cin >> N >> K;
    cin >> R >> S >> P;
    cin >> T;
    vector<int> hand(T.length());
    ll ans = 0;
    for(int i=0;i<T.length();i++){
        if(i<K){
            if(T[i]=='r'){
                hand[i]=1;
                ans+=P;
            }else if(T[i]=='s'){
                hand[i]=2;
                ans+=R;
            }else if(T[i]=='p'){
                hand[i]=3;
                ans+=S;
            }
        }else{
            if(T[i]=='r'&&hand[i-K]!=1){
                hand[i]=1;
                ans+=P;
            }else if(T[i]=='s'&&hand[i-K]!=2){
                hand[i]=2;
                ans+=R;
            }else if(T[i]=='p'&&hand[i-K]!=3){
                hand[i]=3;
                ans+=S;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 896
#pragma gcc optimize (o3)
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define S second
#define F first
#define ll long long
#define ld long double
#define U unsigned
#define pi acos(-1)

using namespace std;

const ll N = 3e3+5;

ll dp[N][N], n, m;
char s[N], t[N];

void solveI()
{
    for(int i = n-1 ; i >= 0 ; i--)
    {
        for(int j = m-1 ; j >= 0 ; j--)
        {
            if(s[i] == t[j]) dp[i][j] = dp[i+1][j+1] + 1;
            else dp[i][j] = max(dp[i+1][j], dp[i][j+1]);
        }
    }
    int i = 0, j = 0;
    while(i<n and j<m)
    {
        if(s[i] == t[j]) printf("%c", s[i]), i++, j++;
        else if(dp[i][j] == dp[i+1][j]) i++;
        else j++;
    }
}

int main()
{
    scanf("%s %s", s, t);
    n = strlen(s);
    m = strlen(t);
    solveI();
    return 0;
}


Measured memory_bytes: 70656
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    X=I()
    ans=360
    for i in range(1,180):
        t=360*i
        if t%X==0:
            ans=min(ans,t//X)
            
    print(ans)

main()


Measured memory_bytes: 61700
N = gets.to_i
A = gets.split.map(&:to_i)

c = A[0]
t = N
l = 0
r = 1
while true
    if r == N
        break
    end
    if c & A[r] == 0
        t += r - l
        c |= A[r]
        r += 1
    else
        c &= ~A[l]
        l += 1
    end
end

puts t

Measured memory_bytes: 15364
import java.util.*;
import java.io.*;
public class Main
{
  public static void main(String args[])
  {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int m=sc.nextInt();
    long sum=0;
    int[] arr=new int[m];
    for(int i=0;i<m;i++)
      arr[i]=sc.nextInt();

     for(int j=0;j<m;j++)
       sum+=arr[j];
    
    long ans=n-sum;
    if(ans<0)
    System.out.println(-1);
    
    else
      System.out.println(ans);
  }
} 

Measured memory_bytes: 46272
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int partition(vector<int> &A, int n){
    int r = n;
    int x = A[r];
    int i = 0;

    for(int j=1; j<=r-1; j++){
        if(A[j] <= x){
            i++;
            swap(A[i], A[j]);
        }
    } 
    swap(A[i+1], A[r]);

    for(int k=1; k<i+1; k++) cout << A[k] << " ";
    cout << "[" << A[i+1] << "]" << " ";
    for(int k=i+2; k<=n; k++){
        if(k != n){
            cout << A[k] << " ";
        }else{
            cout << A[k] << endl;
        }
    }

    return i+1;
}

int main(){

    int n; cin >> n;
    vector<int> A(n+1);
    for(int i=1; i<=n; i++) cin >> A[i];

    partition(A, n);

    return 0;
}

Measured memory_bytes: 3108
#include <bits/stdc++.h>

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;


int main(){
  int r;
  cin>>r;
  cout << 2*3.14159265*r << endl;
  return 0;
}




Measured memory_bytes: 3784
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long long int uint64;
typedef long long int          int64;
 
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void get_N (int64 *n)
{
  int cnt;
  
  cnt = scanf("%lld", n);

  return;
}

void get_NK (int64 *n, int64 *k)
{
  int cnt;
  
  cnt = scanf("%lld %lld", n, k);

  return;
}

void get_N1234 (int64 *n1, int64 *n2, int64 *n3, int64 *n4)
{
  int cnt;

  if (n2 == NULL) {
    cnt = scanf("%lld", n1);
    return;
  }
  if (n3 == NULL) {
    cnt = scanf("%lld %lld", n1, n2);
    return;
  }
  if (n4 == NULL) {
    cnt = scanf("%lld %lld %lld", n1, n2, n3);
    return;
  }
  cnt = scanf("%lld %lld %lld %lld", n1, n2, n3, n4);
  return;
}

void omit_LF (void)
{
  char c;
  int  cnt;
  
  cnt = scanf("%c", &c);
  return;
}

char *get_S (int64 n)
{
  char *buf;
  int  i;
  int  cnt;

  buf = malloc((size_t)(n * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  cnt = scanf("%s", buf);

  return buf;
}

char *get_SN (int64 max, int64 *size)
{
  char *buf;
  int  i;
  int  n;

  buf = malloc((size_t)(max * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  scanf("%s", buf);

  n = strlen(buf);

  *size = n;
  
  return buf;
}

int64 *get_NSeq (int64 n)
{
  int64 *buf;
  int64 i;

  buf = malloc((size_t)(n * sizeof(int64)));
  for (i=0; i<n; i++) {
    get_N(&buf[i]);
  }

  return buf;
}

typedef struct _tmp_t {
  int64    a;
  int64    b;
} tmp_t;


int compare_a(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->a > y->a) return 1;
  if (x->a < y->a) return -1;

  return 0;
}

int compare_b(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->b > y->b) return 1;
  if (x->b < y->b) return -1;

  return 0;
}

void qsort_a (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_a);
}

void qsort_b (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_b);
}

int64 get_jou(int64 v, int64 i) {
  int64 j;
  int64 r;

  if (i == 0) return 1;
  
  r = 1;
  for (j=1; j<=i; j++) {
    r = r*v;
  }
  return r;
}

int64 check_val (int64 N, int64 K, int64 max) {
  int64 j,v;

  v = 1;
  for (j=1; j<=max; j++) {
    v = v*K;
    if ((N / v) > 0) {
      continue;
    } else {
      return 0;
    }
  }
  return 1;
}

int main()
{
  int64 N;
  int64 *x;
  int64 i;
  int64 min = 101;
  int64 max = 0;
  int64 minHp = 0xFFFFFFFF;
  int64 p,hp;

  get_N(&N);

  x = get_NSeq(N);

  for (i=0; i<N; i++) {
    if (x[i] > max) max = x[i];
    if (x[i] < min) min = x[i];
  }

  for (p=min; p<=max; p++) {
    hp = 0;
    for (i=0; i<N; i++) {
      hp += (x[i] - p) * (x[i] - p);
    }
    if (minHp > hp) {
      minHp = hp;
    }
  }

  printf("%lld", minHp);

  return 0;
}







Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <string.h>

using namespace std;
#define LL long long
using VS = vector<string>;
using VI = vector<int>;
using VL = vector<LL>;
using VVI = vector<VI>;
using VVL = vector<VL>;
#define FOR(i,s,e) for(i = s; i < e; i++)
#define FORR(i,s,e) for(i = e-1; i >= s; i--)
const LL INF = (LL)1e16;
const LL MOD = (LL)1e9 + 7;

#define ma 1000000
LL i,j,s,m,dp[ma],dp_2[ma];

int main(){
  memset(dp,100,sizeof(dp));
  memset(dp_2,100,sizeof(dp_2));
  dp[0] = 0;
  dp_2[0] = 0;
  FOR(i,1,181){
    s = i*(i+1)*(i+2)/6;
    FOR(j,s,ma){
      if (dp[j-s]+1 < dp[j]) dp[j] = dp[j-s]+1;
    }
    if (s%2){
      FOR(j,s,ma){
        if (dp_2[j-s]+1 < dp_2[j]) dp_2[j] = dp_2[j-s]+1;
      }
    }
  }
  while (1){
    cin >> m;
    if (m == 0){
      return 0;
    }
    cout << dp[m] << " " << dp_2[m]<<endl;
  }
  return 0;
}



Measured memory_bytes: 18696
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_N=1e5,MAX_M=1e5;
const ll INF=1e18;
int n,m,a[MAX_N];
typedef pair<ll,ll> P;
int M2;
ll seg[MAX_N<<2],laza[MAX_N<<2];
P lazb[MAX_N<<2];
void lazapro(int k,int a,int b){
	if (laza[k]!=0){
		seg[k]+=laza[k]*(b-a);
		if (b-a>1){
			laza[k*2+1]+=laza[k];
			laza[k*2+2]+=laza[k];
		}
		laza[k]=0;
	}
}
void lazbpro(int k,int a,int b){
	if (lazb[k]!=P(0,0)){
		seg[k]+=(2*lazb[k].first+(b-a-1)*lazb[k].second)*(b-a)/2;
		if (b-a>1){
			lazb[k*2+1].first+=lazb[k].first;
			lazb[k*2+1].second+=lazb[k].second;
			lazb[k*2+2].first+=(b-a)/2*lazb[k].second+lazb[k].first;
			lazb[k*2+2].second+=lazb[k].second;
		}
		lazb[k]=P(0,0);
	}
}
void lazpro(int k,int a,int b){
	lazapro(k,a,b);
	lazbpro(k,a,b);
}
void querya(int l,int r,ll x,int k,int a,int b){
	if (r<=a || b<=l){
		return;
	}
	if (l<=a && b<=r){
		laza[k]+=x;
		return;
	}
	lazpro(k,a,b);
	querya(l,r,x,k*2+1,a,(a+b)/2);
	querya(l,r,x,k*2+2,(a+b)/2,b);
	lazpro(k*2+1,a,(a+b)/2);
	lazpro(k*2+2,(a+b)/2,b);
	seg[k]=seg[k*2+1]+seg[k*2+2];
}
void queryb(int l,int r,ll x,ll y,int k,int a,int b){
	if (r<=a || b<=l){
		return;
	}
	if (l<=a && b<=r){
		lazb[k].first+=x+(a-l)*y;
		lazb[k].second+=y;
		return;
	}
	lazpro(k,a,b);
	queryb(l,r,x,y,k*2+1,a,(a+b)/2);
	queryb(l,r,x,y,k*2+2,(a+b)/2,b);
	lazpro(k*2+1,a,(a+b)/2);
	lazpro(k*2+2,(a+b)/2,b);
	seg[k]=seg[k*2+1]+seg[k*2+2];
}	

int main(){
	cin>>n>>m;
	REP(i,n){
		cin>>a[i];
	}
	M2=1;
	while(M2<m){
		M2<<=1;
	}
	REP(i,n-1){
		int v=(a[i+1]-a[i]+m)%m;
		int u=a[i+1]-v;
		if (u>=0){
			queryb(u,a[i+1],v,-1,0,0,M2);
			if (u>0){
				querya(0,u,v,0,0,M2);
			}
			if (a[i+1]<m){
				querya(a[i+1],m,v,0,0,M2);
			}
		}else{
			queryb(0,a[i+1],a[i+1],-1,0,0,M2);
			queryb(m+u,m,v,-1,0,0,M2);
			querya(a[i+1],m+u,v,0,0,M2);
		}
	}
	{
		int l,d;
		l=0,d=M2;
		REP(i,M2*2-1){
			lazpro(i,l,l+d);
			l+=d;
			if (l==M2){
				d/=2;
				l=0;
			}
		}
	}
	ll ans=INF;
	REP(i,m){
		ans=min(ans,seg[i+M2-1]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 10368
#include <bits/stdc++.h>
#define INF 2147483647
#define INF_LL 9223372036854775807
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main() {
	char X, Y;
	cin >> X >> Y;
	if (X < Y) cout << "<" << endl;
	else if (X > Y)cout << ">" << endl;
	else cout << "=" << endl;
	return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int, input().split()))
x2=0
for i in range(n):
  if i%2==1:
    x2-=a[i]
  else:
    x2+=a[i]
ans=[0]*n
ans[0]=x2//2
for i in range(n-1):
  ans[i+1]=a[i]-ans[i]
for i in range(n):
  ans[i]*=2
print(*ans)
  

Measured memory_bytes: 14032
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int sum=0;
		while(sc.hasNext()){
			sum += sc.nextInt();
		}
		System.out.println(sum/60);
		System.out.println(sum%60);
	}	
}

Measured memory_bytes: 17168
import java.io.PrintWriter

fun main(args: Array<String>) {
    // 入力
    val pw = PrintWriter(System.out)
    //入手
    val (a, b, c, d) = readLine()!!.split(" ")

    var e = d.toInt()
    var f = 0
    for (i in 1..a.toInt()) {
        f++
        e--
        if (e == 0) {
            pw.println(f)
            pw.flush()
            return
        }
    }
    e -= b.toInt()
    if (e <= 0) {
        pw.println(f)
        pw.flush()
        return
    }
    for (i in 1..c.toInt()) {
        f--
        e--
        if (e == 0) {
            pw.println(f)
            pw.flush()
            return
        }
    }
}

Measured memory_bytes: 36236
#include <iostream>
#include <fstream>
#include <string>

using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)

int main() {
	ll N, M; cin >> N >> M;
	ll ans = 0;
	if (N == 1 && M == 1) {
		ans = 1;
	}
	else if (N == 1 || M == 1) {
		ans = (N > M) ? N - 2 : M - 2;
	}
	else {
		ans = (N - 2)* (M - 2);
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int w,h,x,y,r;
	scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
	if(0<=x-r&&0<=y-r&&x+r<=w&&y+r<=h){
					printf("Yes\n");
		}
	else{
			printf("No\n");
		}
	return 0;
}

Measured memory_bytes: 2692
/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define pb emplace_back
#define mp make_pair
#define eps 1e-8
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int maxn = 2e5 + 10;
int n, maxx = 0;
map<string, int>m;
set<string>ss;

int main() {
    cin >> n;
    while (n--) {
        string s; cin >> s;
        m[s]++;
    }
    for (auto i : m) maxx = max(maxx, i.second);
    for (auto i : m)
        if (i.second == maxx) ss.insert(i.first);
    for (auto i : ss) cout << i << endl;
    return 0;
}

Measured memory_bytes: 34688
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

#define SENTINEL 1000000000000000000

void merge(long long A[], long long left, long long mid, long long right){
  long long n1, n2, i, j, k;
  long long *L,*R;
  
  n1 = mid-left;
  n2 = right-mid;
  
  L = (long long*)malloc(sizeof(long long) *(n1 + 1));
  R = (long long*)malloc(sizeof(long long) *(n2 + 1));
  
  for(i = 0; i <= n1 - 1; i++){
    L[i] = A[left + i];
  }
  for(j = 0; j <= n2 - 1; j++){
    R[j] = A[mid + j];
  }
  
  L[n1] = SENTINEL;
  R[n2] = SENTINEL;
  
  i = 0;
  j = 0;
  
  for(k = left; k <= right - 1; k++){
   if(L[i] <= R[j]){
      A[k] = L[i];
      i++;
    }
    else{
      A[k] = R[j];
      j++;
    }
  }
  free(L);
  free(R);
}

void mergeSort(long long A[], long long left, long long right){
  long long mid;
  
  if(left + 1 < right){
    mid=(left + right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

int main(void){

    int N;

    scanf("%d", &N);

    long long A[N];

    for(int i = 0; i < N; i++){
        scanf("%lld", &A[i]);
    }

    mergeSort(A, 0, N);

    int c = 1;
    int ans = 0;

    for(int i = 1; i < N; i++){
        if(A[i] == A[i-1]){
            c++;
        }else{
            if(c % 2 == 1){
                ans++;
            }
            c = 1;
        }
    }
    if(c % 2 == 1){
        ans++;
    }

    printf("%d\n", ans);

    return 0;
}

Measured memory_bytes: 2968
#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
#define llint long long int

using namespace std;

llint Q, H, S, D;
llint N;

typedef pair<double, llint> P;
P cost[4];

int main(void)
{
	cin >> Q >> H >> S >> D >> N;
	N *= 4;
	
	cost[0] = make_pair(Q, 1);
	cost[1] = make_pair(H/2.0, 2);
	cost[2] = make_pair(S/4.0, 4);
	cost[3] = make_pair(D/8.0, 8);
	sort(cost, cost + 4);
	
	llint ans = 0;
	llint price;
	
	for(int i = 0; i < 4; i++){
		if(cost[i].second == 1) price = Q;
		if(cost[i].second == 2) price = H;
		if(cost[i].second == 4) price = S;
		if(cost[i].second == 8) price = D;
		ans += (N / cost[i].second) * price;
		N %= cost[i].second;
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
using System;

public class Hello {
  public static void Main() {
    string s = Console.ReadLine();
    int k = s.Length;
    int win = 0;
    for(int i = 0; i < k; i++) {
      if(s[i] == 'o') {
        win++;
      }
    }
    if (15 - k >= 8 - win) {
      Console.WriteLine("YES");
    } else {
      Console.WriteLine("NO");
    }
  }
}

Measured memory_bytes: 13140
#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int n;
	
	cin>>n;
	if(n%1000 ==0){
	    cout<<0;
	}
	else{
	    int temp=0;
	    temp=(n/1000);
	    temp+=1;
	    cout<<((temp*1000)-n);
	}
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int n;
	cin>>n;
	double p[n];
	for(int i=0;i<n;i++)
	{
	    cin>>p[i];
	}
	double dp[n+1][n+1];
	memset(dp,0.0,sizeof(dp));
	dp[0][0]=1.0;
	for(int i=1;i<=n;i++)
	{
	    for(int j=0;j<=i;j++)
	    {
	       if(j==0) 
	       {
	           dp[i][j]=dp[i-1][j]*(1-p[i-1]);
	       }
	       else dp[i][j]=dp[i-1][j]*(1.0-p[i-1])+dp[i-1][j-1]*p[i-1];
	    }
	}
	double ans=0.0;
	for(int i=(n+1)/2;i<=n;i++)
	{
	    ans+=dp[n][i];
	}
	cout<<setprecision(10)<<ans<<endl;
	return 0;
}


Measured memory_bytes: 70528
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
// const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

signed main() {
    int N;
    cin >> N;
    set<int> s;
    for (int i = 0; i < N; i++) {
        int d;
        cin >> d;
        s.insert(d);
    }

    cout << s.size() << endl;

    return 0;
}

Measured memory_bytes: 256
from sys import stdin
il = lambda func=int: list(map(func, stdin.readline().rstrip().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]

n = int(input())
l = ils(n, "il()")

for i in range(101):
    for j in range(101):
        zero = []
        height = -1
        ok = 1
        for k in range(n):
            if l[k][2] == 0:
                zero.append(k)
                continue
            if height == -1:
                height = abs(i-l[k][0]) + abs(j-l[k][1]) + l[k][2]
            if height != abs(i-l[k][0]) + abs(j-l[k][1]) + l[k][2]:
                ok = 0
                break
        for k in zero:
            if height == -1:
                height = abs(i-l[k][0]) + abs(j-l[k][1]) + l[k][2]
            if height > abs(i-l[k][0]) + abs(j-l[k][1]) + l[k][2]:
                ok = 0
                break
        if ok:
            print(i, j, height)

Measured memory_bytes: 3064
#include<iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
  int a;
  cin >> a;
  int ans = 1;
  while(true) {
    if(a == 4 || a == 2 || a == 1) {
      ans += 3;
      break;
    }
    
    if(a % 2 == 0) {
      a /= 2;
    }
    else {
      a = a * 3 + 1;
    }
    ans++;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import deque
 
N, M = map(int, input().split())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

##### Settings
unit = 1
merge = lambda a, b: a * b % M
adj_bu = lambda a, i: a + 1
adj_td = lambda a, i: a + 1
#####

ME = [unit] * N
XX = [0] * N
TD = [unit] * N
for i in R[1:][::-1]:
    XX[i] = adj_bu(ME[i], i)
    p = P[i]
    ME[p] = merge(ME[p], XX[i])
XX[R[0]] = adj_bu(ME[R[0]], R[0])

for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j])
    ac = unit
    for j in X[i][::-1]:
        TD[j] = adj_td(merge(TD[j], ac), i)
        ac = merge(ac, XX[j])
        XX[j] = adj_bu(merge(ME[j], TD[j]), j)

print(*[x - 1 for x in XX], sep = "\n")

Measured memory_bytes: 80424
#include<iostream>
using namespace std;
int n, u,k[101], v[101][101], out[101];

void hitung(int a, int b){
	int i;
	out[a]=b;
	for(i=1; i<=k[a]; i++){
		if(out[v[a][i]]==-1 || out[v[a][i]]>b+1){
			hitung(v[a][i],	b+1);
		}
	}
}

int main(){
	int i,j;
    cin>>n;
    for(i=1; i<=n; i++){
        cin>>u>>k[i]; //getchar();
		out[i]=-1;
        for(j=1; j<=k[i]; j++){
            cin>>v[i][j];// getchar();
        }
    }
    
    hitung(1,0);
	for(i=1;i<=n;i++){
		cout<<i<<" "<<out[i]<<endl;
	}


    //getchar();
    return 0;
}


Measured memory_bytes: 3096
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]C - /\/\/\/

            //数列の長さ,数列を取得
            int n = int.Parse(Console.ReadLine());
            var v = ReadLine().ToList();

            //数列のインデックスが偶数 or 奇数によって、それぞれのDictionaryに値を格納
            var evenDic = new Dictionary<int, int>();
            var oddDic = new Dictionary<int, int>();

            for (int i = 0; i < n; i++)
            {
                if (i % 2 == 0)
                {
                    AddNumber(evenDic, v[i]);
                }
                else
                {
                    AddNumber(oddDic, v[i]);
                }
            }

            //要素の出てきた回数が多い順にソート(KeyValuePair型)
            var evens = evenDic.OrderByDescending(x => x.Value).ToList();
            var odds = oddDic.OrderByDescending(x => x.Value).ToList();

            int count = 0;
            int evenCount = evens[0].Value;
            int oddCount = odds[0].Value;

            if (evens[0].Key != odds[0].Key)
            {
                //偶数,奇数それぞれ、n/2から書き換えが必要な要素数を取得
                count = n - evenCount - oddCount;
            }
            else
            {
                if (evenCount > oddCount)
                {
                    count = n - evenCount - odds[1].Value;
                }
                else if (evenCount < oddCount)
                {
                    count = n - oddCount - evens[1].Value;
                }
                else
                {
                    //もっとも数の多い要素のキーが偶数,奇数で一致していた場合(キー,要素数とも)
                    if (evens.Count == 1)
                    {
                        count = n / 2;
                    }
                    else
                    {
                        if (evens[1].Value >= odds[1].Value)
                        {
                            count = n - oddCount - evens[1].Value;
                        }
                        else
                        {
                            count = n - evenCount - odds[1].Value;
                        }
                    }
                }
            }

            Console.WriteLine(count);
        }

        static void AddNumber(Dictionary<int, int> dic, int vi)
        {
            if (!dic.ContainsKey(vi))
            {
                dic.Add(vi, 1);
            }
            else
            {
                dic[vi]++;
            }
        }

        static IEnumerable<int> ReadLine()
        {
            var line = Console.ReadLine().TrimEnd();
            var array = line.Split(' ');

            foreach (var s in array)
            {
                yield return int.Parse(s);
            }
        }
    }
}

Measured memory_bytes: 26464
S = input()

count = 0
rain_counter = 0
L = []
for s in S:
    if s == "R":
        rain_counter += 1
    if s == "S":
        L.append(rain_counter)
        rain_counter = 0
    count += 1
    if count == len(S):
        L.append(rain_counter)

print(max(L))


Measured memory_bytes: 9024
using System;
class Program
{
    static int func(string s)
    {
        int l = 0,j;
        for(var i=0; i<s.Length; i++)
        {
            if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T')
            {
                for (j = i + 1; j < s.Length && (s[j] == 'A' || s[j] == 'C' || s[j] == 'G' || s[j] == 'T'); j++);
                if (j - i > l)
                {
                    l = j - i;
                }
                i = j;
            }
        }
        return l;
    }
    static int Main(string[] args)
    {
        Console.WriteLine(func(Console.ReadLine()).ToString("d"));
        return 0;
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int &x : a)
        std::cin >> x;

    sort(a.begin(), a.end());
    int cmax = 0;
    for(int i = 0, s = -1; i < n; i++) {
        if (s == a[i]) continue;
        s = a[i];
        int c = 1;
        for(int j = i + 1; j < n && a[j] <= a[i] + 2; j++) {
            c++;
        }
        cmax = max(cmax, c);
    }
    cout << cmax << endl;

    return 0;
}


Measured memory_bytes: 640
#if 0
2019.07.08

震惊，这题我竟然一遍过。
要求所有边被覆盖，对于这个条件，考虑用容斥处理，
对于每个边集 E ，钦定 E 不被覆盖后其他边随意的方案数为 f(E) ，
则 E 对答案的贡献为 f(E) * -1^|E| 。

钦定一些边不被覆盖相当于把树切成森林，每颗新的树独立。
考虑 DP ，设 f[u][i] 表示 u 的子树中，
去掉 u 在内的 i 个点的新树（这些点相互配对）的方案。
u -> v 转移时即 f[u][i + j] += f[u][i] * f[v][j] 。
特别地，对于 f[u][0] ，枚举 u 所在的新树大小 i ，f[u][0] -= f[u]i] * g[i] ，
其中 g[i] 表示大小为 i 的新树中随意配对的方案数，
为什么是 -= ？，因为要考虑容斥系数。
#endif
#include <cstdio>
#include <vector>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long lolong;
inline int input() { int x; scanf("%d", &x); return x; }

const int maxn = 5005, mod = 1000000007;
lolong f[maxn][maxn], fu[maxn], g[maxn];
int size[maxn];
std::vector<int> G[maxn];

void dp(int u, int fa) {
	size[u] = 1;
	f[u][1] = 1;
	for(int v : G[u])
		if(v != fa) {
			dp(v, u);
			for(int i = 0; i <= size[u]; i ++) {
				fu[i] = f[u][i];
				f[u][i] = 0;
			}
			for(int i = 0; i <= size[u]; i ++)
				for(int j = 0; j <= size[v]; j ++)
					(f[u][i + j] += fu[i] * f[v][j]) %= mod;
			size[u] += size[v];
		}
	if(f[u][0]) puts("FUCK");
	for(int i = 1; i <= size[u]; i ++)
		(f[u][0] -= f[u][i] * g[i]) %= mod;
}

int main() {
	int n = input();
	for(int i = 1; i < n; i ++) {
		int u = input(), v = input();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	g[0] = 1;
	for(int i = 2; i <= n; i ++)
		g[i] = g[i - 2] * (i - 1) % mod;
	dp(1, 0);
	printf("%lld\n", (mod - f[1][0]) % mod);
}


Measured memory_bytes: 195328
#include<bits/stdc++.h>
#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using namespace std;
signed main(){
  vector<char> a(6);
  rep(i,6){
    cin>>a[i];
  }
  bool answer = false ;
  if(a[2]==a[3]){
    if(a[4]==a[5]){
      answer =true;
    }
  }
  if(answer){
    cout<<"Yes"<<endl;
  }
  else if(!answer){
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int i,j,k,l;
    i=j=k=l=0;
    long long ans=0;
    for(i=1;i<=n;i++){
    	for(j=1;j<=n;j++){
    		for(k=1;k<=n;k++){
    			int maxi=1;
    			for(l=2;l<=min(min(i,j),k);l++){
    				if(i%l==0&&j%l==0&k%l==0&&l>maxi)maxi=l;
				}
    			ans+=maxi;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

template<typename T>
constexpr T inf = static_cast<T>(pow(10, static_cast<int>(log10(numeric_limits<T>::max())))) + 7;
constexpr llong mod = 1e9+7;

int main() {
  llong N, M, X;
  vector<llong> C;
  vector<vector<llong>> A;

  cin >> N >> M >> X;
  C.resize(N);
  A.resize(N, vector<llong>(M));
  for (int i = 0; i < N; ++i) {
    cin >> C[i];
    for (int j = 0; j < M; ++j) {
      cin >> A[i][j];
    }
  }

  llong ans = inf<llong>;
  for (llong i = 0; i < (1ll<<N); ++i) {
    llong res = 0;
    vector<llong> check(M, 0);
    for (int j = 0; j < N; ++j) {
      if ((i>>j)&1) {
        res += C[j];
        for (int k = 0; k < M; ++k) {
          check[k] += A[j][k];
        }
      }
    }

    bool ok = true;
    for (int j = 0; j < M; ++j) {
      ok &= check[j] >= X;
    }

    if (ok) {
      ans = min(ans, res);
    }
  }

  cout << (ans == inf<llong> ? -1: ans) << endl;

  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;

int main( void ) {
    
    int n;
    cin >> n;
    
    long long ans = 0;
    for( int i = 1, aux = 1; i <= n; i ++ ) {
        int x;
        cin >> x;
        
        if( aux == 1 ) {
            ans += x - 1;
            aux ++;
        }
        else
        if( x == aux )
            aux ++;
        else
            ans += ( x - 1 ) / aux;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
from itertools import *
def f(s):
 for a,b,c,d in permutations(s):
  for x,y,z in product('+-*',repeat=3):
   for t in[f"({a} {x} {b}) {y} ({c} {z} {d})",f"({a} {x} ({b} {y} {c})) {z} {d}"]:
    if eval(t)==10:return'('+t+')'
 else:return 0
for e in iter(input,'0 0 0 0'):print(f(list(map(int,e.split()))))


Measured memory_bytes: 5660
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define ct(string) cout << string << endl

int main() {
    ios::sync_with_stdio(false);
    vector<vector<int> > map(10, vector<int>(10, 0));
    rep(i,50) {
        int x, y, s;
        string raw;
        cin >> raw;
        if (raw=="") break;
        x = raw.at(0) - '0';
        y = raw.at(2) - '0';
        s = raw.at(4) - '0';
        map.at(x).at(y)++;
        if (x+1<10) map.at(x+1).at(y)++;
        if (y+1<10) map.at(x).at(y+1)++;
        if (x-1>(-1)) map.at(x-1).at(y)++;
        if (y-1>(-1)) map.at(x).at(y-1)++;
        if (s > 1) {
            if (x+1<10&&y+1<10) map.at(x+1).at(y+1)++;
            if (x+1<10&&y-1>(-1)) map.at(x+1).at(y-1)++;
            if (x-1>(-1)&&y-1>(-1)) map.at(x-1).at(y-1)++;
            if (x-1>(-1)&&y+1<10) map.at(x-1).at(y+1)++;
        } 
        if (s > 2) {
            if (x+2<10) map.at(x+2).at(y)++;
            if (x-2>(-1)) map.at(x-2).at(y)++;
            if (y+2<10) map.at(x).at(y+2)++;
            if (y-2>(-1)) map.at(x).at(y-2)++;
        }
    }
    int count=0,ma=0;
    rep(i,10) rep(j,10) {
        if (map.at(i).at(j) == 0) count++;
        ma = max(ma, map.at(i).at(j));
    }
    ct(count << endl << ma);
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) (a).begin(),(a).end()

int main(void){
    int n;
    cin >> n;
    vector<int> d(n);
    rep(i,n){
        cin >> d[i];
    }
    sort(all(d));
    cout << d[n/2] - d[n/2-1] << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define cout16 cout << setprecision(16) 
#define rep(i,n) for(int i=0;i<n;i++ )
#define rep2(i,f,n) for(int i=f;i<n;i++ )
#define MAX(A) *max_element(A.begin(),A.end())
#define MIN(A) *min_element(A.begin(),A.end())
#define SORT(A) sort(A.begin(),A.end())
#define REV(A) reverse(A.begin(),A.end())
typedef long long int ll;
using vi = std::vector<int>;
using vvi = std::vector<std::vector<int>>;
using vll = std::vector<ll>;
using vvll = std::vector<std::vector<ll>>;
using P = std::pair<int,int>;
using vp = std::vector<P>;
using namespace std;
#define INF 1001001001
#define LL_INF 1001001001001001001
#define fi first
#define se second

int main(void) {
	int n,d; cin >> n >> d;
	d = 2*d+1;
	int ans = (n+d-1)/d;
	cout << ans << endl;
}




Measured memory_bytes: 256
# Author: cr4zjh0bp
# Created: Thu Mar 12 07:49:01 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

A, B, X = na()

if A > X:
    print("NO")
elif A + B >= X:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3064
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    AB = []
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        AB.append((a, b))
    AB.sort(key=lambda x: x[0])

    cnt = 0
    end = INF
    for a, b in AB:
        if a >= end:
            cnt += 1
            end = b
        else:
            end = min(b, end)

    cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()


Measured memory_bytes: 18204
using System;
using System.Collections.Generic;
using System.Linq;

namespace ziyuutyou
{
    class Program
    {
        static void Main(string[] args)
        {
            var str = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            var N = str[0];
            var M = str[1];
            var X = str[2];
            var Y = str[3];

            int x = Console.ReadLine().Split().Select(int.Parse).ToArray().Max();
            int y = Console.ReadLine().Split().Select(int.Parse).ToArray().Min();

            for (int i =0; i< 100; i++)
            {
                if (X < i && i <= Y && x < i && i <= y)
                {
                    Console.WriteLine("No War");
                    return;
                }
                
            }
            Console.WriteLine("War");
        }
    }
}


Measured memory_bytes: 13396