akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<string> vstring;
typedef vector<pint> vpint;

struct Edge{int to,from,cost;};

#ifdef DEBUGLOCAL
#define debug cout
#else
stringstream __ss__;
#define debug __ss__
#endif

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) debug << *i << " "; debug << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

#define rep(i,n) for(int i=0;i<(n);++i)
#define repd(i,n) for(int i=(n)-1;i>=0;i--)
#define repn(i,m,n) for(int i=(m);i<=(n);++i)
#define repnd(i,m,n) for(int i=(n)-1;i>=(m);i--)
#define rep0(i,n) for(i=0;i<(n);++i)
#define all(n) n.begin(),n.end()
#define sz(n) ((int)(n).size())
#define IL for(;;)
#define MP make_pair
#define PB push_back
#define SS stringstream
#define X second
#define Y first
#define PUTLINE debug<<"LINE:"<<__LINE__<<endl;

const int INF = 2147483647/3;
const double EPS = 1e-10;
const double PI = acos(-1.0);

const int dx[]={1,-1,0,0,1,-1,1,-1,0};
const int dy[]={0,0,1,-1,1,-1,-1,1,0};

int parent[1111];
int rank[1111];
map<string, int> name;

int main() {
	int n,m;
	IL{
		cin>>n>>m;
		if(n==0&&m==0)break;
		name.clear();
		string nm;
		getline(cin,nm);
		rep(i,n){
			getline(cin,nm);
			rep(j,sz(nm)){
				if(nm[j]!=' '){
					rank[i]=j;
					break;
				}
			}
			nm=nm.substr(rank[i],sz(nm)-rank[i]);
			if(rank[i]==0)parent[i]=-1;
			else{
				repd(j,i){
					if(rank[j]==rank[i]-1){
						parent[i]=j;
						break;
					}
				}
			}
			name[nm]=i;
		}
		rep(i,m){
			bool res=false;
			string aa,b,c,d,e,ff;
			cin>>aa>>b>>c>>d>>e>>ff;
			ff=ff.substr(0,sz(ff)-1);
			int a=name[aa],f=name[ff];
			if(d=="child"){
				res=parent[a]==f;
			}
			if(d=="parent"){
				res=parent[f]==a;
			}
			if(d=="sibling"){
				res=parent[a]==parent[f];
			}
			if(d=="descendant"){
				while(parent[a]>-1){
					a=parent[a];
					if(a==f)res=true;
				}
			}
			if(d=="ancestor"){
				while(parent[f]>-1){
					f=parent[f];
					if(a==f)res=true;
				}
			}
			cout<<(res?"True":"False")<<endl;
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 996
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <memory>
#include <stack>
#include <set>
#include <map>

#define MAX_SIZE 100000000
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

  string s; cin>>s;
  reverse(s.begin(), s.end());
  vector<string> words{"dream", "dreamer", "erase", "eraser"};
  for(auto& w : words) {
    reverse(w.begin(),w.end());
  }

  for(int i = 0; i < (int)s.size();) {
    bool flg = false;
    for(auto w : words) {
      string sub = s.substr(i, w.size());
      int pos = sub.find(w);
      if(pos != (int)string::npos) {
        i += w.size();
        flg = true;
        break;
      }
    }

    if(!flg) {
      cout << "NO" << endl;
      exit(0);
    }
  }

  cout << "YES" << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector< vector<int> > VVI;
typedef pair<int,int> PII;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()

int main(){
  int N,A;
  cin>>N>>A;
  VI X(N);
  rep(i,N) cin>>X[i];
  ll dp[N+1][N+1][2501]={};
  dp[0][0][0]=1;
  rep(i,N){
    rep(j,2501){
      rep(k,i+1){
        if(dp[i][k][j]){
          dp[i+1][k+1][j+X[i]]+=dp[i][k][j];
          dp[i+1][k][j]+=dp[i][k][j];
        }
      }
    }
  }
  ll ans=0;
  rep(i,N) ans+=dp[N][i+1][(i+1)*A];
  cout<<ans<<endl;
}

Measured memory_bytes: 51072
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=105;
int r[maxn];
int main()
{
    int  a,b,a1,b1;
    int k,i,j;
    while(cin>>a>>b)
    {
        memset(r,0,sizeof(r));
        a1=a;
        b1=b;
        cin>>k;
        if((2*k)>(b-a))
        {
            for(i=a;i<=b;i++)
            cout<<i<<endl;
            continue;
        }
        for(i=0;i<k;i++)
        {
            r[i]=a1;
            a1=a1+1;
        }
        for(j=k-1;j>=0;j--)
        {
            b1=b-j;
            r[i]=b1;
            i++;
        }
        for(i=0;i<(2*k);i++)
        {
            if(r[i]!=r[i+1])
                cout<<r[i]<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int K;
    cin >> K;
    if (K % 2 == 0) {
        cout << K / 2 * K / 2 << endl;
    } else {
        cout << (K + 1) / 2 * (K - 1) / 2 << endl;
    }
    return 0;
}

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


int main(){
  int n;
  cin >> n;
  vector<int>vec(n);
  for (int i = 0; i < n; i++){
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  int s = 0;
  for (int j = 0; j< n-1;j++){
    s += vec.at(j);
  }
  s += vec.at(n-1)/2;
  cout << s << endl;
}
    
      
    


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

int main() {
  int n; cin >> n;
  vector<int> problem(n);
  for (int i = 0; i < n; i++) cin >> problem[i];
  
  int total = accumulate(problem.begin(), problem.end(), 0);
  
  int m; cin >> m;
  for (int i = 0; i < m; i++) {
    int p, x; cin >> p >> x;
    int ans = total - problem[p - 1] + x;
    cout << ans << endl;
  }
}

Measured memory_bytes: 256
from itertools import permutations


def main():
    N, M, R = map(int, input().split())
    r = list(map(lambda x: int(x) - 1, input().split()))
    dist = [[1001001001 for _ in range(N)] for _ in range(N)]

    for _ in range(M):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        dist[a][b] = c
        dist[b][a] = c
    for i in range(N):
        dist[i][i] = 0

    # warshall-floyd
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = 1001001001
    for way in permutations(r):
        ans_now = 0
        for i in range(R - 1):
            ans_now += dist[way[i]][way[i + 1]]
        if ans > ans_now: ans = ans_now
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 47448
s = input().rstrip().split()
N = int(s[0])
Y = int(s[1])
ans_x = -1
ans_y = -1
ans_z = -1
for x in range(N+1):
    for y in range(N-x+1):
        total = 10000*x + 5000*y + 1000*(N-x-y)
        if total == Y:
            ans_x = x
            ans_y = y
            ans_z = N-x-y
            break
print(str(ans_x)+' '+str(ans_y)+' '+str(ans_z))

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

void solve(long long N, long long K, vector<long long> a){
	vector<long long> b(N + 1);
	for(int i = 0; i < N; ++i) {
		b[i + 1] = b[i] + a[i];
	}
	vector<long long> c;
	for(int i = 0; i < N; ++i) for(int j = i + 1; j <= N; ++j) {
		c.push_back(b[j] - b[i]);
	}
	long long res = 0;
	for(int i = 62; i >= 0; --i) {
		long long t = 1LL << i;
		int cnt = 0;
		for(auto p: c) {
			if(p & t) ++cnt;
		}
		if(cnt < K) continue;
		vector<long long> d;
		res |= t;
		for(auto p: c) {
			if(p & t) {
				d.push_back(p);
			}
		}
		c = d;
	}
	cout << res << endl;
}

int main(){	
	long long N;
	long long K;
	scanf("%lld",&N);
	vector<long long> a(N-1+1);
	scanf("%lld",&K);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&a[i]);
	}
	solve(N, K, a);
	return 0;
}



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

using namespace std;

int main(){
    long long int N,M,ans=0;
    priority_queue<long long int> Q;
    cin >> N >> M;
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        Q.push(a);
    }

    for(int i=0;i<M;i++){
        long long int b = Q.top();
        Q.pop();
        b /= 2;
        Q.push(b);
    }

    for(int i=0;i<N;i++){
        ans += Q.top();
        Q.pop();
    }

    cout << ans << endl;
}

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

using pii = pair<int, int>;

vector<pii> v;
vector<int> stk;
int r, c, n;

static bool on_border(int x, int y) {
	return (x == 0 || x == r) || (y == 0 || y == c); }

static int border_idx(int x, int y) {
	if (y == 0)
		return x;
	if (x == r)
		return x + y;
	if (y == c)
		return c + r + r - x;
	return c + c + r + r - y; }

int main() {
#ifdef HOME
	freopen("arc76c.in", "r", stdin);
	freopen("arc76c.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> r >> c >> n;
	v.reserve(2 * n);
	for (int x1, x2, y1, y2, i = 1; i <= n; ++i) {
		cin >> x1 >> y1 >> x2 >> y2;
		if (!on_border(x1, y1) || !on_border(x2, y2))
			continue;
		v.emplace_back(border_idx(x1, y1), i);
		v.emplace_back(border_idx(x2, y2), i); }

	sort(begin(v), end(v));
	for (auto i: v) {
		if (!stk.empty() && stk.back() == i.second)
			stk.pop_back();
		else
			stk.push_back(i.second); }

	cout << (stk.empty() ? "YES\n" : "NO\n");


	return 0; }



Measured memory_bytes: 2428
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>
#include <set>

using ll = long long;
using namespace std;
typedef unsigned long long ull;

const ll MOD = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()

struct edge { ll to, cost, rosen; };
using P = pair<ll, pair<ll, ll>>;
map<ll,vector<edge>>v[100010];
vector<map<ll, ll>>d(100010);

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		ll p, q, c;
		cin >> p >> q >> c;
		v[p][c].push_back(edge{ q,0,c });
		v[q][c].push_back(edge{ p,0,c });
		v[p][c].push_back(edge{ p,1,0 });
		v[q][c].push_back(edge{ q,1,0 });
		v[p][0].push_back(edge{ p,1,c });
		v[q][0].push_back(edge{ q,1,c });
		d[p][c] = INF;
		d[q][c] = INF;
		d[p][0] = INF;
		d[q][0] = INF;
	}
	d[1][0] = 0, d[n][0] = INF;
	priority_queue<P, std::vector<P>, std::greater<P>>pq;
	pq.push(P(d[1][0], make_pair(1, 0)));
	while (!pq.empty()) {
		P a = pq.top();
		pq.pop();
		int i = a.second.first;
		int j = a.second.second;
		if (d[i][j] < a.first)continue;
		for (int k = 0;k < v[i][j].size();k++) {
			edge e = v[i][j][k];
			if (j != 0) {
				if (d[e.to][e.rosen] <= d[i][j] + e.cost)continue;
				d[e.to][e.rosen] = d[i][j] + e.cost;
				pq.push(P(d[e.to][e.rosen], make_pair(e.to, e.rosen)));
			}
			else {
				if (d[e.to][e.rosen] <= d[i][j])continue;
				d[e.to][e.rosen] = d[i][j];
				pq.push(P(d[e.to][e.rosen], make_pair(e.to, e.rosen)));
			}
		}
	}
	if (d[n][0] == INF)cout << -1 << endl;
	else cout << d[n][0] << endl;
}

Measured memory_bytes: 123056
import sys

while True:
    lst = list(map(int, input().split()))
    total = lst[0] + lst[1]

    ans = ''
    if sum(lst) == -3:
        sys.exit(0)
    if lst[0] == -1 or lst[1] == -1:
        print('F')
        continue

    if total >= 80:
        ans = 'A'
    elif 65 <= total < 80:
        ans = 'B'
    elif 50 <= total < 65:
        ans = 'C'
    elif 30 <= total < 50:
        if lst[2] >= 50:
            ans = 'C'
        else:
            ans = 'D'
    elif 0 <= total <= 30:
        ans = 'F'
    else:
        pass
    
    print(ans)


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

int main(){
    int a, b;
    double h, m;

    cin>> a >> b >> h >> m;
    double theata;
    theata = min(abs(30*h+0.5*m - 6*m), 360 - abs(30*h+0.5*m - 6*m));
    //cout<< fixed<<setprecision(9) << theata <<endl;
    theata /= 180;
    //cout<< fixed<<setprecision(9) << theata <<endl;
    //cout<< fixed<<setprecision(9) << cos(M_PI*theata) <<endl;    

    cout<< fixed<<setprecision(9) << sqrt(a*a + b*b - 2*a*b*cos(M_PI*theata)) <<endl;  

    return 0;
}

Measured memory_bytes: 4116
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	void run(){
		String s=sc.next();
		for(char c : s.toCharArray()){
			int k='Z'-'A'+1;
			print(""+(char)((c-'A'-3+k)%k+'A'));
		}
		println("");
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

Measured memory_bytes: 12000
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
p=i2()

import sys
sys.setrecursionlimit(10000)

par=[i for i in range(n)]
rank=[0 for i in range(n)]

def rt(x):
 if par[x]==x:
    return x
 else:
    par[x]=rt(par[x])
    return par[x]

def un(x,y):
    x=rt(x)
    y=rt(y)
    if x==y:
       return
    else:
       if rank[x]<rank[y]:
          par[x]=y
       else:
          par[y]=x
          if rank[x]==rank[y]:
             rank[x]+=1
def find(x,y):
    return  rt(x)==rt(y)
       
for i in range(m):
 [x,y]=i2()
 un(x-1,y-1)

s=0
for i in range(n):
 if find(i,p[i]-1):
   s+=1
print(s)
   


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

int main() {
    string S,T,U; cin>>S>>T;
    int A,B; cin>>A>>B>>U;
    if(U == S){
        cout<<A-1<<" "<<B<<endl;
    }else{
        cout<<A<<" "<<B-1<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    using ll = long long;
  ll n;
    cin >> n;
    vector<ll> c(26, 1);
    for(ll i = 0; i < n; i++)
    {
        char a;
        cin >> a;
        c[a - 'a']++;
    }

    ll ans = 1L;
    int mod = 1e9 + 7;
  for(ll i = 0; i < 26; i++)
    {
        ans = ans * c[i] % mod;
    }
    cout << (ans + mod - 1) % mod << endl;
}


Measured memory_bytes: 256
T = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

if A[0] > B[0]:
  A, B = B, A

if A[1] < B[1]:
  print(0)
  exit()

d = (B[0] - A[0]) * T[0]
k = (A[1] - B[1]) * T[1] - d

if k < 0:
  print(0)
  exit()

if k == 0:
  print("infinity")
  exit()

ans = 1 + (d // k) * 2
if d // k == d / k:
  ans -= 1

print(ans)

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

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    long long h,n;
    cin>>h>>n;
    long long s=0;
    string ans="Yes";

    for(int i=0 ; i<n ; i++){
        long long a=0;
        cin>>a;
        s+=a;
    }
    if(s<h)ans="No";
    cout<<ans;
    return 0;
}


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

int main() {
  ll N, M;
  cin >> N >> M;
  
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  sort(A.begin(), A.end());
  
  // M番目の Ax + Ay の値を求める
  ll low = 0;
  ll high = 1e10;
  while (high - low > 1) {
    ll mid = (low + high) / 2;
    ll num = 0;
    for (int i = 0; i < N; i++) {
      num += A.end() - lower_bound(A.begin(), A.end(), mid - A.at(i));
    }
    if (num >= M) {
      low = mid;
    } else {
      high = mid;
    }
  }
  
  // 累積和の計算
  vector<ll> s(N + 1, 0);
  for (int i = N - 1; i >= 0; i--) {
    s.at(i) = s.at(i + 1) + A.at(i);
  }
  
  ll ans = 0;
  ll cnt = 0;
  for (int i = 0; i < N; i++) {
    int x = upper_bound(A.begin(), A.end(), low - A.at(i)) - A.begin(); // 合計が low になるものは別で計算
    ans += (N - x) * A.at(i) + s.at(x);
    cnt += N - x;
  }
  ans += low * (M - cnt); // 合計が low になるものを加算
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 1408
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Maximum Sum
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		int n, k, sum, max;
		int[] list;

		while (!(line = br.readLine()).equals("0 0")) {
			n = Integer.parseInt(line.substring(0, line.indexOf(' ')));
			k = Integer.parseInt(line.substring(line.indexOf(' ') + 1));
			list = new int[n];
			for (int i = 0; i < n; i++) {
				list[i] = Integer.parseInt(br.readLine());
			}
			max = 0;
			for (int i = 0; i < k; i++) {
				max += list[i];
			}
			sum = max;
			for (int i = k; i < n; i++) {
				sum = sum - list[i - k] + list[i];
				if (sum > max)
					max = sum;
			}
			System.out.println(max);
		}
	}
}

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

#define ll long long int
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vi vector<ll>
#define pb push_back
#define pii pair<ll,ll>
#define mp make_pair

int main()
{
    ll n,k;
    cin>>n>>k;
    ll h[n+1];
    for(ll i=1;i<=n;cin>>h[i++]);

    ll c[n+1];
    c[1] = 0;
    c[2] = abs(h[2]-h[1]);

    for(ll i=2;i<=n;i++)
    {
        c[i] = c[i-1] + abs(h[i]-h[i-1]);
        if(i<=k)
        {
            for(ll j=1;j<i;j++)
            c[i] = min( c[i], c[j] + abs(h[i]-h[j]) ); 
        }
        else
        {
            for(ll j = i-k;j<i;j++)
            c[i] = min( c[i], c[j] + abs(h[i]-h[j]) );
        }
        
    }

    cout<<c[n];
    
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi >
#define vvvi vector<vvi >
#define pii pair<int,int>
#define INF (int)1e9
#define MOD (int)1e9+7
typedef long long llong;
using namespace std;

int main(){
	int n;
	cin>>n;
	
	vi p(n);
	REP(i,n) cin>>p[i];
	
	int cnt=0;
	for(int i=1;i<n-1;++i){
		if((p[i-1]<p[i]&&p[i]<p[i+1])||(p[i-1]>p[i]&&p[i]>p[i+1])) cnt++;
	}

	cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;

#define LL long long
#define debug(x) cerr<<#x<<": "<<x<<endl;
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int INF = 2147483600;
const int MAXN = 100010;
const int Mod = 924844033LL;

int N,K; 
int f[2010][2010][2][2];
LL g[2010]; LL fac[2010];
//做到了i个，选了j个，这个有没有添，下面一行i+1有没有 
inline bool Pre(int T,int d){
	for(int i=1;i<=(int)(N/K)+1;i++)
       	for(int j=0;j<=i;j++)
            for(int k=0;k<=1;k++)
                for(int p=0;p<=1;p++) f[i][j][k][p]=0;
	int nw=(!d?K:d);
	if(nw>N) return false;
	f[1][0][0][1]=1;
	if(!d||d>(K/2)) f[1][1][1][1]=1;
    for(int i=1;i<=(int)(N/K)+T;i++){
       	for(int j=0;j<=i;j++){
            for(int k=0;k<=1;k++){
                for(int p=0;p<=1;p++){
                    LL now=f[i][j][k][p];
                    if(!now) continue;
                    if(i<(int)(N/K)+T){
                    	if(p) (f[i+1][j+1][1][1]+=now)%=Mod;
                    	(f[i+1][j][0][1]+=now)%=Mod;
                	}
                    if(!k&&p&&(nw+(K/2)<=N)) (f[i][j+1][1][(i==(N/K)+T?1:0)]+=now)%=Mod;
                }
            }
        } nw+=K;
    }
    return true;
}

int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    N=read(),K=read()*2; g[0]=1; fac[0]=1;
    for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%Mod;
    for(int i=0;i<K;i++){
        int T=((N%K)>(i-1+K)%K);
        bool x=Pre(T,i);
        if(!x) continue;
		for(int j=N;j>=0;j--){
            if(g[j]){
                int d=g[j]; g[j]=0;
                for(int k=0;k<=T+(int)(N/K);k++)
                    (g[j+k]+=(1LL*d*(f[(N/K)+T][k][0][1]+f[(N/K)+T][k][1][1])%Mod)%Mod)%=Mod;
            }
        }
    } LL ans=0;
    for(int i=0;i<=N;i++){
        (ans+=(i&1)?Mod-g[i]*fac[N-i]%Mod:g[i]*fac[N-i]%Mod)%=Mod;
    } printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 31232
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N,K = inputlist()
mod = 10**9+7
li = [int(i) for i in range(N+1)]
suma = [0]*(N+1)
for i in range(1,N+1):
    suma[i] = suma[i-1]+li[i]
ans = 0
for i in range(K,N+1):
    m = suma[i-1]
    M = suma[-1] - suma[-(i+1)]
    ans += M-m+1
    ans %= mod
ans +=1
ans %= mod
print(ans)


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

int main(){
  int r,c,i,j;
  int table[101][101] = {0};

  cin >> r >> c;
  for(i = 0; i < r; i++){
    for(j = 0; j < c; j++){
      cin >> table[i][j];
    }
  }
  for(i = 0; i < r; i++){
    for(j = 0; j < c; j++){
      table[i][c] += table[i][j];
      table[r][j] += table[i][j];
    }
  }
  for(i = 0; i < r; i++){
      table[r][c] += table[i][c];
  }
  for(i = 0; i <= r; i++){
    for(j = 0; j < c; j++){
      cout << table[i][j] << " ";
    }
    cout << table[i][c] << endl;
  }
  return 0;
}

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

int main(){
  long long N;
  cin >> N;
  int M = 0;
  vector<int>A(40,0);
  for (int i = 2; i <= 1000000; i++) {
    if (N % i == 0){
      for (int j = 0; j < 40; j++) {
        if (N % i == 0){
          A.at(M)++;
          N /= i;
        }
        else {
          M++;
          break;
        }
      }
    }
  }

  int count = 0;
  for (int i = 0; i < 40; i++) {
    if (A.at(i) >= 36){
      count += 8;
    }
    else if (A.at(i) >= 28){
      count += 7;
    }
    else if (A.at(i) >= 21){
      count += 6;
    }
    else if (A.at(i) >= 15){
      count += 5;
    }
    else if (A.at(i) >= 10){
      count += 4;
    }
    else if (A.at(i) >= 6){
      count += 3;
    }
    else if (A.at(i) >= 3){
      count += 2;
    }
    else if (A.at(i) >= 1){
      count += 1;
    }
  }
  
  if (N > 1000000){
    cout << count + 1 << endl;
  }
  else {
    cout << count << endl;
  }
}
        




Measured memory_bytes: 3620
#include <bits/stdc++.h>
#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 FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const double PI=3.14159265358979323846;
using namespace std;
vector<int> dx={1,0,-1,0};
vector<int> dy={0,1,0,-1};
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

ll gcd (ll x,ll y) {
    if (x < y) swap(x, y);
    if (y == 0) return x;
    return gcd(x % y, y);
}

int main() {
    int t;
    cin>>t;
    while(t--) {
        ll a,b,c,d;
        cin>>a>>b>>c>>d;
        if(a<b || d<b) {
            cout<<"No"<<endl;
            continue;
        }
        if(c>=b) {
            cout<<"Yes"<<endl;
            continue;
        }
        
        ll g=gcd(b,d);
        if((((b-a%g)+g-1)/g)*g+a%g-g > c) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}


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



int main() {
    string s;
    cin >> s;
    
    int cnt = 0, le = (int)s.size();
    rep(i,le/2) {
        if(s[i] != s[le-i-1])
            cnt++;
    }
    
    cout << cnt << endl;
    
    
    
    return 0;
}


Measured memory_bytes: 3628
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cmath>
#include<deque>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<tuple>
#include<utility>
#include<vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<int>> vvi;

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define REP(i, n)  for(int i=0; i<(int)(n); i++)
#define REPS(i, n)  for(int i=1; i<=(int)(n); i++)
#define PER(i, n) for(int i=(int)(n)-1; i>= 0; i--)
#define PERS(i, n)  for(int i=(int)(n); i>0; i--)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i!=(c).end(); i++)
#define RFOR(i, c)  for(__typeof((c).rbegin()) i=(c).rbegin(); i!=(c).end(); i++)
#define ALL(container)  (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) (container).size()
#define FILL0(n)  setfill('0') << right << setw(n)
#define mp(a, b)  make_pair(a, b)
#define toLower(c)  c+0x20
#define toUpper(c)  c-0x20
#define pb  push_back
#define eb  emplace_back

const int INF = 1e9;
const long long LLINF = 1e18;
const int MOD = 1000000007;

int main(){
  int N;  cin >> N;
  map<string, ll> mp;
  REP(i, N){
    string s; cin >> s;
    sort(ALL(s));
    mp[s]++;
  }
  ll ans = 0;
  for(auto it=mp.cbegin(); it!=mp.cend(); it++){
    ans += it->second * (it->second - 1) / 2;
  }
  cout << ans << endl;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

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

  bool ans = false;
  rep(i, n/4 + 1) {
    rep(j, n/7 + 1) {
      if (4*i+7*j == n) {
        ans = true;
        break;
      }
    }
  }

  if (ans) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
#include <bitset>
#include <numeric>
#include <queue>
#include <map>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long ll;
typedef pair<int, int> P;
const vector<int> di = {-1, 0, 1, 0};
const vector<int> dj = { 0, 1, 0, -1 };

int main() {

	int n;
	cin >> n;
	vector<ll> t(n);
	vector<ll> a(n);
	rep(i, n) cin >> t.at(i) >> a.at(i);

	ll ans = 0;
	rep(i, n) {
		if (i == 0) {
			ans = t.at(0) + a.at(0);
			continue;
		}
		if (t.at(i) >= t.at(i - 1) && a.at(i) >= a.at(i - 1)) {
			ans = t.at(i) + a.at(i);
			continue;
		}
		else {
			ll num = max(t.at(i - 1) / t.at(i), a.at(i - 1) / a.at(i));
			t.at(i) = t.at(i) * num;
			a.at(i) = a.at(i) * num;
			if (t.at(i) >= t.at(i - 1) && a.at(i) >= a.at(i - 1)) {
				ans = t.at(i) + a.at(i);
			}
			else {
				t.at(i) += t.at(i) / num;
				a.at(i) += a.at(i) / num;
				ans = t.at(i) + a.at(i);
			}
		}
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll a[200100];
ll sum[200100];
ll sum1[200100];
int main()
{
	ll n;
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	ll dap = n;
	for (int i = 1; i <= n; i++)
	{
		sum[i] = a[i] + sum[i - 1];
		sum1[i] = (a[i] ^ sum1[i - 1]);
	}
	ll lo = 1;
	ll hi = 1;
	while (1)
	{
		if (hi == n + 1) {
			dap = dap + ((hi - lo)*(hi - lo - 1) / 2);
			break;
		}
		if ((sum[hi] - sum[lo - 1]) == (sum1[hi] ^ sum1[lo - 1])) {
			hi++;
		}
		else
		{
			dap = dap + ((hi - lo )*(hi - lo-1) / 2);
			while ((sum[hi] - sum[lo - 1]) != (sum1[hi] ^ sum1[lo - 1])) {
				lo++; 
			}
			dap=dap- ((hi - lo)*(hi - lo - 1) / 2);
		}
	}
	printf("%lld", dap);
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;


class SCC {
public:
    const int n;
    VV G;
    VV rG;
    V vs;
    vector<bool> used;
    V cmp;
    SCC(int _n) : n(_n), G(_n), rG(_n), used(_n), cmp(_n) {}
    void addEdge(int from, int to) {
        G[from].emplace_back(to);
        rG[to].emplace_back(from);
    }
    void dfs(int v) {
        used[v] = true;
        rep(i, G[v].size()) {
            if (!used[G[v][i]]) dfs(G[v][i]);
        }
        vs.emplace_back(v);
    }
    void rdfs(int v, int k) {
        used[v] = true;
        cmp[v] = k;
        rep(i, rG[v].size()) {
            if (!used[rG[v][i]]) rdfs(rG[v][i], k);
        }
        vs.emplace_back(v);
    }
    int scc() {
        // memset(used, 0, sizeof(used));
        // vs.clear();
        rep(v, n) {
            if (!used[v]) dfs(v);
        }
        used.assign(n, false);
        // memset(used, 0, sizeof(used));
        int k = 0;
        for (int i = vs.size() - 1; i >= 0; i--) {
            if (!used[vs[i]]) rdfs(vs[i], k++);
        }
        return k;
    }
};


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int N, M;
    cin >> N >> M;
    SCC scc(N);
    rep(i, M) {
        int s, t;
        cin >> s >> t;
        scc.addEdge(s, t);
    }

    scc.scc();

    int Q;
    cin >> Q;
    rep(i, Q) {
        int u, v;
        cin >> u >> v;
        cout << (scc.cmp[u] == scc.cmp[v]) << endl;
    }

}

Measured memory_bytes: 4644
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    string s;
    cin >> s;

    for (int i=0; i<s.length(); i++) {
        if (s[i] == '9') {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
S = input()
Q = int(input())

heads_min_idx = 0
heads_max_idx = 0
tails_min_idx = 0
tails_max_idx = 0
heads = {}
tails = {}
rev_flag = 1  # 1 or -
for q in range(Q):
    tmp_q = input()
    if tmp_q == '1':
        rev_flag *= -1
    else:
        _, f, c = tmp_q.split()
        if rev_flag == 1:
            if f == '1':
                heads[heads_min_idx - 1] = c
                heads_min_idx -= 1
            else:
                tails[tails_max_idx + 1] = c
                tails_max_idx += 1
        else:
            if f == '1':
                tails[tails_max_idx + 1] = c
                tails_max_idx += 1
            else:
                heads[heads_min_idx - 1] = c
                heads_min_idx -= 1

if rev_flag == 1:
    head_str = ''.join([s for _, s in sorted(heads.items(), key=lambda x: x[0])])
    tail_str = ''.join([s for _, s in sorted(tails.items(), key=lambda x: x[0])])
    print(head_str + S + tail_str)
else:
    head_str = ''.join([s for _, s in sorted(tails.items(), key=lambda x: x[0], reverse=True)])
    tail_str = ''.join([s for _, s in sorted(heads.items(), key=lambda x: x[0], reverse=True)])
    print(head_str + S[::-1] + tail_str)


Measured memory_bytes: 101336
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet};
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::str::*;

#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let cin = stdin();
    let cin = cin.lock();
    let s: String = cin
        .bytes() // Bytes
        .map(|c| c.expect("failed reading char") as char)
        .skip_while(|c| c.is_whitespace()) // c が whitespace である限り skip
        .take_while(|c| !c.is_whitespace()) // c が whitespace でない限り要素を返す
        .collect();
    s.parse().ok().expect("failed parsing")
}

#[allow(non_snake_case)]
fn main() {
    input! {X:u128}
    let mut x: u128 = 100;
    let mut i = 1;
    loop {
        x = x * 101 / 100;
        if x >= X {
            break;
        }
        i += 1;
    }
    println!("{}", i);
}


Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SORT(i) sort((i).begin(),(i).end())
constexpr int INF = 2000000000;
constexpr int mod = 1000000007;

int main() {
	int a, b;
	cin >> a >> b;
	if (a > 8 || b > 8)puts(":(");
	else puts("Yay!");

	return 0;
}

Measured memory_bytes: 256
local s = io.read("l")
local a, b, c, d = string.byte(s, 1, 4)
if ((a == b) and (c == d)) or
   ((a == c) and (b == d)) or
   ((a == d) and (b == c)) then
   if (a == b) and (a == c) then
       print("No")
   else
       print("Yes")
   end
else
   print("No")
end


Measured memory_bytes: 760
A,B=map(int,input().split())
if A==B:
    print("Draw")
elif (A>=2 and B>=2 and A>B) or (A==1 and B!=1):
    print("Alice")
elif (A>=2 and B>=2 and B>A) or (B==1 and A!=1):
    print("Bob")


Measured memory_bytes: 2940
import itertools

n,m,q = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(q)]

numbers = [i for i in range(1, m+1)]

numbers = list(itertools.combinations_with_replacement(numbers, n))


ans = 0
tmp = 0

for i in range(len(numbers)):
    s = numbers[i]
    tmp = 0
    
    for j in range(q):
        if s[li[j][1]-1] - s[li[j][0]-1] == li[j][2]:
            tmp += li[j][3]
    ans = max(ans, tmp)

print(ans)

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

#define ALL(v) v.begin(), v.end()
#define REP(i, a, b) for (int i = a; i < (int)b; i++)
#define REPD(i, a, b) for (int i = a; i > b; i--)
#define REPLL(i, a, b) for (ll i = a; i < b; i++)
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define FORLL(i, a, b) for (ll i = a; i <= b; i++)

using namespace std;

typedef long long ll;
typedef long double ld;

typedef vector<int>::iterator vit;
typedef set<int>::iterator sit;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef pair<ld, ld> pld;

#define remax(a, b) a = max(a, b)
#define remin(a, b) a = min(a, b)

#define popcount __builtin_popcount
#define pb push_back
#define mp make_pair
#define st first
#define y first
#define nd second
#define x second

#define eps 1e-9
#define pi acos(-1.0)

const int N = 2123;
const int inf = (1<<30);

int n, m, q;
string a, b;
int nxt[N], prv[N], ones[N];

int dist(int a, int b) {
  if(a < b) return b-a;
  return 1 + n-1-a + b;
}

int sum(int a, int b) {
  if(a <= b) return ones[b] - (a ? ones[a-1] : 0);
  return sum(0, b) + sum(a, n-1);
}

int work(vector<pii> &xy) {
  if(!xy.size()) {
    return 0;
  }
  xy.pb({0, 0});
  sort(ALL(xy));
  reverse(ALL(xy));
  int mx = 0;
  int ans = inf;
  for(auto kv : xy) {
    ans = min(ans, kv.first + mx);
    mx = max(mx, kv.nd);
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(0);

  cin >> a >> b;
  n = a.size();

  bool isazero = true;
  bool isbzero = true;
  for(char c : a) isazero &= c == '0';
  for(char c : b) isbzero &= c == '0';
  if(isbzero) {
    cout << (isazero ? 0 : -1) << endl;
    return 0;
  }
  int last = -1, first = -1;
  REP(i, 0, n) {
    if(i) ones[i] += ones[i-1];
    ones[i] += b[i] == '1';
  }
  REP(i, 0, n) {
    if(first == -1 && b[i] == '1') first = i;
    if(b[i] == '1') last = i;
  }
  REP(i, 0, n) {
    if(b[i] == '1') last = i;
    prv[i] = last;
  }
  FORD(i, n-1, 0) {
    if(b[i] == '1') first = i;
    nxt[i] = first;
  }
  int ans = inf;
  REP(d, -n+1, n) {
    vector<pii> xy;
    int flips = 0;
    REP(i, 0, n) {
      int j = (i+d+n)%n;
      if(d < 0 && a[i] != b[j]) {
        flips++;
        if(sum(j, i) == 0) xy.pb({dist(prv[j], j), dist(i, nxt[i])});
      }
      if(d >= 0 && a[i] != b[j]) {
        flips++;
        if(sum(i, j) == 0) xy.pb({dist(prv[i], i), dist(j, nxt[j])});
      }
    }
    remin(ans, abs(d) + flips + 2*work(xy));
  }

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

Measured memory_bytes: 384
n=int(input())
h=list(map(int,input().split()))
dp=[0]*n
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
    dp[i]=min(dp[i-2]+abs(h[i-2]-h[i]),dp[i-1]+abs(h[i-1]-h[i]))
print(dp[-1])


Measured memory_bytes: 20488
#include <bits/stdc++.h>
#define rep(i,x) for(int i=0; i<(int) (x); i++)
#define PI 3.14159265359
using namespace std;

int main()
{
	string s;
	cin >> s;
	reverse(s.begin(), s.end());
	if(s[0]=='3') cout<<"bon";
	else if(s[0]=='0' || s[0]=='1'|| s[0]=='6' || s[0]=='8') cout<<"pon";
	else cout<<"hon";
	//////////////////////////////////
	//--------end--------
	//
	return 0;
}


Measured memory_bytes: 3624
#include <stdio.h>
#include <iostream>
using namespace std;	
 int star_vowels(char s[]) {

    int j = 0;

    while (s[j] != '\0'){
        if (s[j] == ',' ) {
            putchar(' ');
        } else {
            putchar(s[j]);
        }
        j++;
    }
    return 0;
}
int main(){
	char s[19];
	cin>>s;
	star_vowels(s);
}

Measured memory_bytes: 256
require 'prime'
include Math
def max(a,b);                    a > b ? a : b                            end
def min(a,b);                    a < b ?  a : b                           end
def swap(a,b);                   a, b = b, a                              end
def gif;                         gets.to_i                                end
def gsf;                         gets.chomp                               end
def gi;                          gets.split.map(&:to_i)                   end
def gs;                          gets.chomp.split.map(&:to_s)             end
def gc;                          gets.chomp.split('')                     end
def pr(num);                     num.prime_division                       end
def putall(obj);                 obj.each{|o| puts(o)}                    end
def array(size,init=nil);        Array.new(size){init}                    end
def darray(size1,size2,init=nil);Array.new(size1){Array.new(size2){init}} end
def rep(num);                    num.times {|i|yield(i)}                  end
def repl(st,en);                 st.upto(en) {|i|yield(i)}                end


a,b,c = gi

puts b-a == c-b ? 'YES' : 'NO'

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

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

  vector<int> x(N), y(N);
  rep(i, N) cin >> x[i] >> y[i];

  vector<double> d;

  int cnt = 0;
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      int dx = x[i] - x[j];
      int dy = y[i] - y[j];
      d.push_back(sqrt(dx * dx + dy * dy));
      cnt++;
    }
  }

  double sum = 0;
  rep(i, d.size()) sum += d[i] * 2 * cnt;
  printf("%.9f\n", sum / 2 / cnt / (N / double(2)));
}

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

int main() {
 int a,b;
 cin >> a >> b;
 int c = min(a,b);
 int d = max(a,b);
 for(int i = 0;i<d;i++){
     cout << c;
 }
 cout <<  endl;

}

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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl;

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

    vector<int> A(N), B(N);

    rep(i, N)
    {
        cin >> A[i];
        B[i] = A[i];
    }

    sort(ALL(A), greater<int>());
    int max_first = A[0], max_second = A[1];

    rep(i, N)
    {
        if (B[i] < max_first)
            OP(max_first)
        else
            OP(max_second)
    }

    return 0;
}

Measured memory_bytes: 3200
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>
#define maxn 405
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int h,w;
char s[maxn][maxn];
bool vis[maxn][maxn];
const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
int numb = 0,numw = 0;
void dfs(int x,int y){
	vis[x][y] = true;
	if(s[x][y] == '#') numb++;
	else numw++;
	for(int d = 0;d < 4;d++){
		int cx = x + dx[d], cy = y + dy[d];
		if(cx >= 1 && cx <= h && cy >= 1 && cy <= w && !vis[cx][cy] && s[cx][cy] != s[x][y]){
			dfs(cx,cy);
		}
	}
}
int main(){
	scanf("%d%d",&h,&w);
	for(int i=1;i<=h;i++){
		scanf("%s",s[i] + 1);
	}
	ll ans = 0;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(!vis[i][j]){
				numb = numw = 0;
				dfs(i,j);
				ans += (ll)numb * numw;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 8064
from collections import Counter

n = int(input())
a_list = list(map(int, input().split()))
q = int(input())
bc_list = []
for _ in range(q):
    bc_list.append(list(map(int, input().split())))

sum_num = sum(a_list)
counter = Counter(a_list)

for i, (b, c) in enumerate(bc_list):
    sum_num = sum_num + ((c - b) * counter[b])
    counter[c] = counter[c] + counter[b]
    counter[b] = 0
    print(sum_num)


Measured memory_bytes: 40344
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream &operator << (ostream& out,const pair<S,T>& o){
    out << "(" << o.first << "," << o.second << ")"; return out;
}

/*
<url:https://arc077.contest.atcoder.jp/tasks/arc077_b>
問題文============================================================
 1,…,n の n 個の整数からなる長さ n+1 の数列 a1,a2,…,an+1 が与えられます。
 この数列には 1,…,n のどの整数もかならず 1 回以上出現することが分かっています。
 
 k=1,…,n+1 のそれぞれについて、与えられた数列の長さ k の（連続とは限らない）部分列の個数を求め、
 109+7 で割ったあまりを出力して下さい。
 
 2 つの部分列が数列として同じであれば、元の数列での位置が異なっていたとしても、1 通りと数えます。
 
 数列 a の長さ k の部分列とは、a の要素のうち k 個を選んで、
 それらを順番を変えずに取り出して並べた数列のことを指します。
 例えば、数列 1,2,3,4,5 の長さ 3 の部分列には、
 1,3,5 や 1,2,3 などがあります。 一方で、3,1,2 や 1,10,100 はこの数列の部分列ではありません。
 
 1≤n≤10^5
 1≤ai≤n
 1,…,n のどの整数も必ず数列に出現する。
 n,ai は整数である。
=================================================================

解説=============================================================

 [ ~ ]x[ ~ ]x[ ~ ]
================================================================
*/

const ll MAX_N = 2e5 + 10;
const ll MOD = 1e9+7;
ll Inv[MAX_N];
ll fact[MAX_N];
ll factInv[MAX_N];
void Inv_init(){
    Inv[1] = 1;
    for(int i = 2; i < MAX_N; i++) {
        Inv[i] = Inv[MOD%i] * (MOD - MOD/i) % MOD;
    }
}
void fact_init(){
    fact[0] = fact[1] = factInv[0] = factInv[1] = 1;
    for(int i = 2; i < MAX_N; i++){
        fact[i] = (fact[i-1] * i) % MOD;
        factInv[i] = (factInv[i-1] * Inv[i])%MOD;
    }
}

// a^b % MOD;
ll powmod(ll a,ll b) {ll res=1;a%=MOD; for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
// 逆元 1/a % MOD
ll inversemod(ll a) { return powmod(a,MOD - 2);}
ll nCr(int n,int r) {
    if(n < r) return 0;
    return (fact[n] * (factInv[r] * factInv[n-r] % MOD)) % MOD;
}

void init(){
    Inv_init();
    fact_init();
}

void solve(){
    ll n; cin >> n;
    vector<ll> a(n+1); for(auto &in:a){ cin >> in; in--; }
    vector<ll> idx(n,-1);
    ll lx = -1,rx = -1;
    for(int i = 0; i <= n;i++){
        if(idx[a[i]] == -1) idx[a[i]] = i;
        else{ lx = idx[a[i]]; rx = idx[a[i]] = i;}
    }
    ll lnum = lx, mnum = rx - lx - 1, rnum = (n+1) - rx - 1;

    // output
    for(ll i = 1; i <= n+1; i++){
        if(i <= lnum + rnum + 1){
            cout << (nCr(n+1,i) - nCr(lnum+rnum,i-1) + MOD)%MOD << endl;
        }else{
            cout << nCr(n+1,i) << endl;
        }
    }
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    init();
    solve();
	return 0;
}


Measured memory_bytes: 7424
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};
int dx9[9]={0,1,0,-1,1,-1,1,0,-1};
int dy9[9]={0,1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;
// << fixed << setprecision
// --------------------------------------
int n;
#include <cassert>
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

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

  cin >> n;
  vector<ll> c(n);
  REP(i, n) cin >> c[i];
  sort(c.begin(), c.end());
  vector<mint> two(n + 1);
  two[0] = 1;
  REP(i, n) two[i + 1] = two[i] * 2;

  mint ans = 0;

  REP(i, n) {
    int l = i, r = n - i - 1;

    mint now = two[r];
    if(r) now += two[r - 1] * r;
    now *= two[l];
    now *= c[i];
    ans += now;
  }

  ans *= two[n];

  cout << ans.x << endl;
}


Measured memory_bytes: 6344