akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> tiii;

constexpr int INF = 1e9;

int main() 
{
    int N, M, P; cin >> N >> M >> P;
    vector<vector<int>> G(N+1);
    vector<vector<int>> invG(N+1);
    vector<tiii> edge(M);
    for (int i = 0; i < M; i++)
    {
        int A, B, C; cin >> A >> B >> C;
        G[A].push_back(B);
        invG[B].push_back(A);
        edge[i] = tiii(A, B, C-P);
    }

    vector<bool> visited(N+1, false);
    visited[1] = true; queue<int> q;
    q.push(1);
    while (!q.empty())
    {
        int t = q.front(); q.pop();
        for (int x : G[t])
        {
            if (!visited[x])
            {
                visited[x] = true;
                q.push(x);
            }
        }
    }

    vector<bool> invvisited(N+1, false);
    invvisited[N] = true;
    q.push(N);
    while (!q.empty())
    {
        int t = q.front(); q.pop();
        for (int x : invG[t])
        {
            if (!invvisited[x])
            {
                invvisited[x] = true;
                q.push(x);
            }
        }
    }
    vector<bool> ok(N+1);
    for (int i = 1; i <= N; i++)
    {
        ok[i] = visited[i] && invvisited[i];
    }

    vector<int> cost(N+1, -INF);
    cost[1] = 0;
    bool changed;
    for (int i = 0; i <= N; i++)
    {
        changed = false;
        for (int j = 0; j < M; j++)
        {
            int a, b, c;
            tie(a, b, c) = edge[j];
            if (cost[a] != -INF && cost[b] < cost[a] + c)
            {
                if (ok[b]) changed = true;
                cost[b] = cost[a] + c;
            }
        }
    }
    // for (int i = 1; i <= N; i++) cout << ok[i] << ' ';
    // cout << endl;
    if (changed) cout << -1 << endl;
    else cout << max(0, cost[N]) << endl;
}

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

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;

#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
constexpr auto INF = 5000000000000000;
constexpr auto MOD = 1000000007;

int main() {

	string s;
	cin >> s;

	if (s[0] == 'S')cout << "Cloudy" << endl;
	if (s[0] == 'C')cout << "Rainy" << endl;
	if (s[0] == 'R')cout << "Sunny" << endl;

	
}

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

long long func(long long x){
	if(x<=0)return 0;
	long long a = 2;
	long long ans = 0;
	if(x%2==1){
		if(x%4==1)return 1;
		else return 0;
	}
	if(x%4==2)ans++;
	x/=2;
	while(x!=0){
		if(x%2==1){
			ans=(long long)ans+a;
		}
		x/=2;
		a=(long long)a*2;
	}	
	return ans;
}



int main(){
	long long A,B;
	cin>>A>>B;
	/*
	if(A==B){
		cout<<A<<endl;
		return 0;
	}*/
	
	long long ans = 0;
	A=func(A-1);
	B=func(B);
	long long a = 1;
	while(A!=0||B!=0){
		if(A%2!=B%2){
			ans+=(long long)a;
		}
		a=(long long)a*2;
		A/=2;
		B/=2;
	}
	cout<<ans<<endl;
	
			
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>

using namespace std;

int main(void){
  int W,n,v[1000],w[1000],dp[1001][1001],t=1;

  while(cin >> W,W){
    cin >> n;

    for(int i=0;i<n;i++)
    scanf("%d,%d",&v[i],&w[i]);

    for(int i=0;i<1000;i++)
      for(int j=0;j<1000;j++)
	dp[i][j]=-1;
    
    for(int i=0;i<1000;i++){
      dp[0][i] = 0;
    }
    
    for(int i=0;i<n;i++)
      for(int j=0;j<=W;j++)
	if(j<w[i])dp[i+1][j]=dp[i][j];
	else dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);

    cout << "Case " << t << ":" << endl;
    
    for(int i=W;i>=0;i--){
      if(dp[n][i] != dp[n][W]){
	cout << dp[n][W] << endl << i+1 << endl;
	break;
      }
    }
      t++;
  }

  return 0;
}

Measured memory_bytes: 0
def dv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.remove(1)
    return divisors


n=int(input())
x=dv(n)
#print(x)
y=[]
for i in x:
    if n//(i-1)==n%(i-1):
        y.append(i-1)
#print(y)
print(sum(y))

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

// #define fi first
// #define se second
#define rep(i, n) for (ll i=0;i<(n); i++)
#define ALL(v) (v).begin(), (v).end()
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)
#define WHITE 0  // 未訪問
#define BLACK 1  // 訪問ずみ

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;

const ll M=1000000007ll;
const ll MOD=1000000007ll;
const ll MAX=100000001ll;
const int N=100000;
//const ll M = 1000000000+7;


struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n, -1){}
  int root(int x) {
    if(d[x]<0) return x;
    return d[x] = root(d[x]);
  }
  bool unite(int x, int y){
    x = root(x); y=root(y);
    if(x==y) return false;
    if (d[x]>d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) {return root(x)==root(y);}
  int size(int x) {return -d[root(x)];}
  int factor_size() {
    int ans=0;
    rep(i,d.size()){
      if (d[i]<0) {ans++;}
    }
    return ans;
  }
  
};

bool inc(char c){
  string AGCT = "AGCT";
  bool ans = false;
  rep(i, 4) if(c==AGCT[i]) ans = true;
  return ans;
}

int main(){ 
  string S;

  cin>>S;

  int cnt = 0;
  int ans = 0;
  rep(i, S.size()){
    if(inc(S[i])) cnt++;
    else {
      ans = max(ans, cnt);
      cnt=0;
    }
  }
  ans = max(ans, cnt);

  cout << ans <<endl;
}



Measured memory_bytes: 256
#include<stdio.h>
int main(void){
        int a,b;
        scanf("%d %d",&a,&b);
        if(a<b){
                printf("a < b\n");
        }else if(a>b){
                printf("a > b\n");
        }else if(a == b){
                printf("a == b\n");
        }
        return 0;
}

Measured memory_bytes: 580
#include<algorithm>
#include<iostream>
#include<climits>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define ll long long
using namespace std;
//{{{ read()
inline int read(){
	register int x=0,f=1;
	register char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')	x=x*10+(ch^48),ch=getchar();
	return x*f;
}
//}}}
const int N=1005;
char s[N][N];
int n,m,a[N][N];
struct P{
	int x,y,z;
	P (int xx=0,int yy=0,int zz=0){
		x=xx,y=yy,z=zz;
	}
	bool operator < (const P k) const{
		return z>k.z;
	}
};
priority_queue<P> que;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)	scanf("%s",s[i]+1);
	memset(a,27,sizeof(a));
	a[1][1]=(s[1][1]=='#');
	que.push(P(1,1,a[1][1]));
	while(!que.empty()){
		P k=que.top();	que.pop();
		int x=k.x,y=k.y,z=k.z;
		if(z!=a[x][y])	continue;
		if(x<n){
			int k=z+(s[x+1][y]=='#'&&s[x][y]=='.');
			if(k<a[x+1][y])	a[x+1][y]=k,que.push(P(x+1,y,k));
		}
		if(y<m){
			int k=z+(s[x][y+1]=='#'&&s[x][y]=='.');
			if(k<a[x][y+1])	a[x][y+1]=k,que.push(P(x,y+1,k));
		}
	}
	cout<<a[n][m]<<endl;
	return 0;
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(){
    ll a, b, c, d;
    cin>>a>>b>>c>>d;
    int cnt = 0;
    while(1){
        if(cnt%2==0)  c-=b;
        if(c<=0){
            cout<<"Yes"<<endl;
            break;
        }
        if(cnt&1) a-=d;
        if(a<=0){
            cout<<"No"<<endl;
            break;
        }
        cnt++;
    }
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main() {

	int n;
	cin >> n;
	vector<long long int> s(n);
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}

	set<long long int> st;
	st.insert(0);

	for (int i = 0; i < n; i++) {
		set<long long int> st2 = st;
		for (set<long long int>::iterator ite = st.begin(); ite != st.end(); ite++) {
			st2.insert((*ite) + s[i]);
		}
		st = st2;
	}

	long long int ans = 0;

	for (set<long long int>::iterator ite = st.begin(); ite != st.end(); ite++) {
		if ((*ite) % 10 != 0) {
			ans = (*ite);
		}
	}

	cout << ans << endl;

	return 0;
}

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

int main () {
  
  int N, K, X, Y;  
  int sum;
  cin >> N >> K >> X >> Y;
  
  if (N <= K) {
    sum = N * X;
  }
  else {
    sum = K * X + (N - K) * Y;
  }
    
  cout << sum << endl; 
  
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
string s;
int main(){
  cin >> s;
  int m = (s[5] - '0') * 10 + (s[6] - '0');
  int d = (s[8] - '0') * 10 + (s[9] - '0');
  if (m <= 4 && d <= 30) cout << "Heisei" << endl;
  else cout << "TBD" << endl;
  return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
from math import factorial
N = int(input())
dic = defaultdict(int)

for i in range(N):
    sort_str = "".join(sorted(input()))
    dic[sort_str] += 1

count = 0
for key, val in dic.items():
    if val >= 2:
        count += factorial(val) // (factorial(2) * factorial(val - 2))
print(count)


Measured memory_bytes: 18228
n, k = map(int, input().split())
a = list(map(int, input().split()))

if k == 0:
    print(max(a))
    exit()

l = 0
u = max(a)

while u > l+1:
#    print(l,u)
    c = (l + u) // 2
    cnt = 0
    for i in a:
        cnt = cnt + ((i-1)//c)
    if cnt <= k:
        u = c
    else:
        l = c

print(u)

Measured memory_bytes: 30828
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc =new Scanner(System.in);
    int X =sc.nextInt();int Y =sc.nextInt();
    if(Y%2==1){System.out.println("No");}
    else{ int y =Y/2;
         if(y-X<0){System.out.println("No");}
         else if(y-2*X>0){System.out.println("No");}
         else{System.out.println("Yes");}
        }
  }
}

Measured memory_bytes: 35824
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <regex>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
using ll = long long;
using VL=vector<ll>;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
const long long INF =  99999999999;
pair <ll,ll> r[100100];

ll N;

int main(){
  cin>>N;
  if(N==1){
    cout<<1<<endl;
    return 0;
  }

  REP(i,N){
    ll s,t;
    cin>>s>>t;
    r[i].second=s-t;
    r[i].first=s+t-1;
  }

  
  
  sort(r,r+N);
  ll cnt=0,t=-INF;
  for(int i=0;i<N;i++){
    if(t<r[i].second){
      cnt++;
      t=r[i].first;
    }
  }

  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define MAXN 100005
int numlist[MAXN];
int main () {
    int n;
    cin >> n;
    memset(numlist, 0, sizeof(numlist));
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        numlist[x]++;
    }
    int kind = 0;
    int dup = 0;
    for (int i = 1; i <= 100000; i++) {
        if (numlist[i]) {
            kind++;
            dup+=(numlist[i] - 1);
        }
    }
    if (dup % 2 == 1) {
        kind--;
    }
    cout << kind << endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  int goal = 2;

  vector<int> a(N);

  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }

  int now_button = 1;
  int count = 0;
  bool done = false;

  while (count++ < N) {
    now_button = a.at(now_button - 1);

    if (now_button == goal) {
      done = true;
      break;
    }
  }

  if (done) {
    cout << count << endl;
  } else {
    cout << -1 << endl;
  }
  
}

Measured memory_bytes: 3772
N = int(input())
wlst = [input() for i in range(N)]
wset = set(wlst)
if len(wset) != N:
    print('No')
    exit()

tmp = wlst[0][-1]
for i in range(1, N):
    if tmp != wlst[i][0]:
        print('No')
        exit()
    tmp = wlst[i][-1]

print('Yes')

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

class DisjointSet {
  public:
    vector<int> rank, p;

    DisjointSet () {}
    DisjointSet (int size) {
      p.resize(size);
      rank.resize(size);

      for (int i = 0; i < size; i++)
        makeSet(i);
    }

    // 创建仅包含元素 x 的新集合
    void makeSet (int x) {
      p[x] = x;
      rank[x] = 0;
    }

    bool same (int x, int y) {
      return findSet(x) == findSet(y);
    }

    // 合并指定的元素 x，y
    void unite (int x, int y) {
      link(findSet(x), findSet(y));
    }

    void link (int x, int y) {
      if (rank[x] > rank[y]) {
        p[y] = x;
      } else {
        p[x] = y;
        if (rank[x] == rank[y])
          rank[y]++;
      }
    }

    // 求包含元素 x 的集合的“代表”元素
    int findSet (int x) {
      stack<int> S;
      int root;

      S.push(x);

      while (S.top() != p[S.top()]) {
        S.push(p[S.top()]);
      }

      root = S.top(); S.pop();

      while (S.size()) {
        p[S.top()] = root;
        S.pop();
      }

      return root;

      // if (x != p[x])
      //   p[x] = findSet(p[x]); // 路径压缩
      // return p[x];
    }
};

int main () {
  int n, q, com, x, y;

  cin >> n >> q;

  DisjointSet ds = DisjointSet(n);

  for (int i = 0; i < q; i++) {
    cin >> com >> x >> y;

    if (com) {
      cout << ds.same(x, y) << endl;
    } else {
      ds.unite(x, y);
    }
  }

  return 0;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
int INF = 1e9;
int main(){
    long long N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        A[i] *= -1;
    }
    std::vector<int> dp(N, INF);
    int l = INF;
    for(int i = 0; i < N; i++){
        int index = upper_bound(dp.begin(), dp.end(), A[i]) - dp.begin();
        dp[index] = A[i];
    }
    int ans = 0;
    for(int i = 0 ; i < N; i++){
        if(dp[i] != INF) ans++;
        else break;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
	int n,pos,t;
	cin>>n;
	std::vector<int> c(n+1);
	std::vector<int> s(n+1);
	std::vector<int> f(n+1);
	std::vector<int> ans(n+1);
	for (int i = 0; i < n-1; i++)
		cin>>c[i]>>s[i]>>f[i];
	for (int i = 0; i < n-1; i++)
	{
		pos=i;
		t=s[i]+c[i];
		pos++;
		while(pos!=n-1)
		{
			//t+=c[pos];
			//pos++;
			while((t-s[pos])%f[pos]!=0 || t<s[pos])
				t++;
			t+=c[pos];
			pos++;

		}
		ans[i]=t;
	}
	for (int i = 0; i < n; i++)
		cout<<ans[i]<<endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC057_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var number = long.Parse(Console.ReadLine());
            var square = Math.Sqrt(number);
            var func = new List<double>();
            for (int a = 1; a <= square; a++)
            {
                if (number % a == 0)
                {
                    double b = number / a;
                    double max = Math.Max(a, (long)b);
                    func.Add(Math.Log10(max) + 1);
                }
            }
            func.Sort();
            Console.WriteLine((int)func[0]);
        }
    }
}


Measured memory_bytes: 13396
/*----------------by syr----------------*/
/*

         iii                  ii
     rBQBBBBBBE       BBR iBBBBQBBL     XBBBBBBQBBBBB
   iBBQJ    7BBB      BBsSBBr   BBQ      i      cBBB
  rBBU       iBBw     BBBQi     HBBi           KBBi
  BBH         BB5    iBBB       isL          wBB5
 GBB         iBBi    6BB                   iBBB
 BBQ         BQB     BBD                  QBBi
 BBB        BQB     iQBi                1BBv
 sBBg     wBBB      QBB               iBBB
  7BBBBBBBBBi       BBR              wBBBBBBBBBBBBB
     irvi           ii               ii    i i iii
                i5U
               BBB
               BB7
              1BB
      iPBBBBBKBBR    JBR1       rQBO   BR  UBQP  iBBQi
    7BBBGs7sXBBBi     QBBr     gBBE   rBB BB2BB7HBZQBB
   QBBi      sBQ       BBB   iBBB     SQBBR  BBBB  cBQ
  gBQ        BBg        BBB KBBi      MBBH   BBB   BBs
 iBBv       iBBi         QBBBL        BBR   pBB   iBB
 pBB        BBB         iBBBB        iBB    BBL   KBB
 MBB       BBBR        BBB JBBi      DBR   iBQ    BBL
 GBB     7BBBB2      PBBH   BBBi     BQr   DBB   iBB
  BQBXwgBBP BB7    1BBB      BBQ7   1BB    BBc   BBB
   2BBBBw   BB    EBBS        QBBi  HBa   iBB    BB7
*/
#include<bits/stdc++.h>

using namespace std;

#define PH push
#define MP make_pair
#define PB push_back
#define fst first
#define snd second
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define x0 x0123456789
#define y0 y0123456789
#define x1 x1234567890
#define y1 y1234567890
#define x2 x2345678901
#define y2 y2345678901
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 7;
const int maxn = 25e6 + 5000 + 5;

int n;
int x[3], y[3];
ll ans = 0;
ll f[maxn], g[maxn];

int main(){
	scanf("%d", &n);
	scanf("%d%d%d", x + 0, x + 1, x + 2);
	scanf("%d%d%d", y + 0, y + 1, y + 2);
	f[0] = 0;
	FOR(i, 0, maxn){
		f[i] = i;
		if(i >= x[0])
			f[i] = max(f[i], f[i - x[0]] + y[0]);
		if(i >= x[1])
			f[i] = max(f[i], f[i - x[1]] + y[1]);
		if(i >= x[2])
			f[i] = max(f[i], f[i - x[2]] + y[2]);
	}
	g[0] = 0;
	FOR(i, 0, maxn){
		g[i] = i;
 		if(i >= y[0])
			g[i] = max(g[i], g[i - y[0]] + x[0]);
		if(i >= y[1])
			g[i] = max(g[i], g[i - y[1]] + x[1]);
		if(i >= y[2])
			g[i] = max(g[i], g[i - y[2]] + x[2]);
	}
	REP(i, 0, n){
		//printf("i = %d f[i] = %d %d\n", i, f[i], n - i + f[i]);
		ans = max(ans, g[n - i + f[i]]);
	}
	printf("%lld\n", ans);
	return 0;
}



Measured memory_bytes: 391040
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<climits>
#include<cmath>
#include<sstream>
#include<iomanip>
#include <map>
#include <stack>
 
const int64_t cc = pow( 10, 9 );
//std::cout<< std::fixed << std::setprecision(10) << ( double )( max ) / 2;
bool sort_pair( std::pair< std::string, int64_t > origin, std::pair< std::string, int64_t > another )
{
    return origin.second  > another.second;
}
 
int main()
{
    std::string word = "aa";
    int64_t a,b,c,d,e;
    std::cin>> a;
    std::cin>> b;
    c = 0;
    
    for( int i = 0; i < b; i++ )
    {
        std::cin>> d;
        c += d;
    }

    if( c < a )
    {
        std::cout<< "No\n";
    }
    else
    {
        std::cout<< "Yes\n";
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define iinf 2000000000
#define linf 1000000000000000000LL
#define ulinf 10000000000000000000ull
#define MOD1 1000000007LL
#define mpr make_pair
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned long UL;
typedef unsigned short US;
typedef pair < int , int > pii;
clock_t __stt;
inline void TStart(){__stt=clock();}
inline void TReport(){printf("\nTaken Time : %.3lf sec\n",(double)(clock()-__stt)/CLOCKS_PER_SEC);}
template < typename T > T MIN(T a,T b){return a<b?a:b;}
template < typename T > T MAX(T a,T b){return a>b?a:b;}
template < typename T > T ABS(T a){return a>0?a:(-a);}
template < typename T > void UMIN(T &a,T b){if(b<a) a=b;}
template < typename T > void UMAX(T &a,T b){if(b>a) a=b;}
const int L=524288;
int n,sz[200005],cnt[L],fac[200005],rfac[L];
vector < int > adj[200005];
const LL MOD=924844033ll,G=5ll;
int powM(int V,int T=MOD-2ll){
	int R=1;
	while(T){
		if(T&1) R=(LL)R*(LL)V%MOD;
		T>>=1;
		V=(LL)V*(LL)V%MOD;
	}
	return R;
}
void ntt(int *a,int l,bool r){
    int i,j=l/2,k;
    for(i=1;i<l;++i){
        if(i<j) swap(a[i],a[j]);
        for(k=l/2;j&k;k>>=1) j^=k;
        j^=k;
    }
    for(i=1;(1<<i)<=l;++i){
        int cl=(1<<i);
        int w=powM(G,(MOD-1)/cl);
        if(r) w=powM(w,MOD-2);
        for(j=0;j*cl<l;++j){
            int cur=1;
            for(k=0;k<(cl>>1);k++){
                int v1=a[j*cl+k],v2=((LL)a[j*cl+k+(cl>>1)]*(LL)cur)%MOD;
                a[j*cl+k]=(v1+v2)%MOD;
                a[j*cl+k+(cl>>1)]=(v1-v2+MOD)%MOD;
                cur=((LL)cur*(LL)w)%(LL)MOD;
            }
        }
    }
}
void dfs(int v,int f){
	int i;
	sz[v]=1;
	++cnt[n];
	for(i=0;i<(int)adj[v].size();++i){
		int u=adj[v][i];
		if(u!=f){
			dfs(u,v);
			sz[v]+=sz[u];
			--cnt[sz[u]];
		}
	}
	--cnt[n-sz[v]];
}
void precal(){
	int i,j,k;
	fac[0]=1;
	for(i=1;i<=n;++i){
		fac[i]=(LL)fac[i-1]*(LL)i%MOD;
	}
	rfac[n]=powM(fac[n]);
	for(i=n-1;i>=0;--i){
		rfac[i]=(LL)rfac[i+1]*(LL)(i+1)%MOD;
	}
}
int main(){
    // inputting start
    // 数据结构记得初始化！ n，m别写反！
    int i,j,k;
	scanf("%d",&n);
	for(i=0;i<n-1;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		--u;--v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
    #ifdef LOCAL
        TStart();
    #endif
    // calculation start
    // 数据结构记得初始化！ n，m别写反！
    dfs(0,-1);
	precal();
	for(i=0;i<=n;++i){
		cnt[i]=(LL)cnt[i]*(LL)fac[i]%MOD;
	}
	ntt(cnt,L,0);
	reverse(rfac,rfac+n+1);
	ntt(rfac,L,0);
	for(i=0;i<L;++i){
		cnt[i]=(LL)cnt[i]*(LL)rfac[i]%MOD;
	}
	ntt(cnt,L,1);
	LL D=powM(L);
	precal();
	for(i=n+1;i<=n*2;++i){
		printf("%lld\n",D*(LL)cnt[i]%MOD*(LL)rfac[i-n]%MOD);
	}
    #ifdef LOCAL
        TReport();
    #endif
    return 0;
}

Measured memory_bytes: 32000
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()


ll gcd(ll a, ll b)
{
	if (a < b) {
		a ^= b;
		b ^= a;
		a ^= b;
	}

	return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}

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

	vector<ll> A(N);
	rep(i, N)
	{
		cin >> A[i];
	}

	//すべてのAの最小公倍数を求める。
	//オーバーフロー対策で、先に0で割る。
	int count = 0;
	ll tmp = A[0];
	while (tmp % 2 == 0)
	{
		tmp /= 2;
		count++;
	}

	//すべてのAが同じ回数2で割れない場合、条件を満たすXは存在しない。
	ll m = 1;
	ll exp = (ll)1 << count;

	M /= (exp / 2);

	rep(i, N)
	{
		if (A[i] % exp != 0 || A[i] % (2 * exp) == 0)
		{
			cout << 0 << endl;
			return 0;
		}

		A[i] /= exp;

		m = lcm(m, A[i]);

		if (m > M)
		{
			cout << 0 << endl;
			return 0;
		}
	}

	ll c1 = M / m;
	ll c2 = M / (2 * m);

	cout << c1 - c2 << endl;

	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    string S;
    cin >> S;
    int m = 0, cnt = 0;
    for(int i = 0; i < S.size(); i++){
        if(S.at(i) == 'A' || S.at(i) == 'T' || S.at(i) == 'G' || S.at(i) == 'C'){
            cnt++;
            m = max(m, cnt);
        }
        else{
            cnt = 0;
        }
    }
    cout << m << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define prt(v) cout<<v<<"\n";
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
#define endl "\n"
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;

vector<vector<ll>> G(100007, vector<ll>(0));

void dfs(ll x,vl &d,ll dist){
    d[x]=dist;
    for(auto p: G[x]){
        if(d[p]==INF)dfs(p,d,dist+1);
    }
}

signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll u;
    cin >> u;u--;
    ll v;
    cin >> v;v--;
    vector<ll> A(N-1,0);
    vector<ll> B(N-1,0);
    for(ll i=0;i<N-1;++i){
        cin>>A[i]>>B[i];
        A[i]--;B[i]--;
        G[A[i]].emplace_back(B[i]);
        G[B[i]].emplace_back(A[i]);
    }
    vector<ll> du(N,INF);
    vector<ll> dv(N,INF);
    dfs(u,du,0);
    dfs(v,dv,0);
    ll mark;
    ll ou=-INF;
    for(ll i=0;i<N;++i){
        if(du[i]<dv[i]&&chmax(ou,dv[i]))mark=i;
    }
    ll nige=du[mark];
    ll ans=nige;
    ll S=ou-nige;//Sは1以上
    if(S==1)ans+=0;
    else if(S==2)ans++;
    else {
        ans+=((S-2)/2)*2;
        S-=((S-2)/2)*2;
        if(S==3)ans+=2;
        else ans++;
    }
    prt(ans)



    return 0;
}


Measured memory_bytes: 12928
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
int main(){
    int N,K;
    cin>>N>>K;
    vector<ll>V(N);
    rep(i,N){
        cin>>V.at(i);
    }
    ll M=0;
    int limit=min(N,K);
    rep(i,limit+1){
        rep(j,limit+1-i){
            vector<ll>get;
            ll sum=0;
            rep(k,i){
                get.push_back(V.at(k));
                sum=sum+V.at(k);
            }
            rep(s,j){
                get.push_back(V.at(N-1-s));
                sum=sum+V.at(N-1-s);
            }
            sort(get.begin(),get.end());
            int l=get.size();
            rep(t,min(l,K-(i+j))){
                if(get.at(t)<0){
                    sum=sum-get.at(t);
                }
            }
            M=max(M,sum);
        }
    }//全探索
    cout<<M<<endl;
}

Measured memory_bytes: 256
import java.util.*;

// ABC 18-C
// http://abc018.contest.atcoder.jp/tasks/abc018_3
 
public class Main {

	public static void main (String[] args) throws java.lang.Exception {
		Scanner in = new Scanner(System.in);
		
		int h = in.nextInt();
		int w = in.nextInt();
		
		String[] map = new String[h];
		
		for (int i = 0; i < h; i++) {
			map[i] = in.next();
		}
		
		for (int i = 0; i < w + 2; i++) {
			System.out.printf("#");
		}
		System.out.println();

		for (int i = 0; i < h; i++) {
			System.out.printf("#%s#\n", map[i]);
		}
		
		for (int i = 0; i < w + 2; i++) {
			System.out.printf("#");
		}
		System.out.println();

	}
}

Measured memory_bytes: 22484
n,s=map(int,input().split())
l=[abs(int(i)-s) for i in input().split()]
ans=l[0]
def gc(a,d):
  ai=a;bi=d
  a,d=min(ai,bi),max(ai,bi)
  if a==0:return d
  else:return gc(d%a,a)
  
  
for i in l:
  ans=gc(ans,i)
print(ans)


Measured memory_bytes: 14220
//
//  main.cpp
//  Atcoder1
//
//  Created by Hamske on 2020/09/17.
//  Copyright © 2020 Author. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

//#define pb push_back
//#define mp make_pair
//
//#define F first
//#define S second

typedef long long ll;

#define rept(_i,iv,n,type) for(type _i=(type)(iv);_i<(type)(n);++_i)
//#define repi(_i,iv,n) rept(_i,iv,n,int)
//#define repl(_i,iv,n) rept(_i,iv,n,ll)

#define rept0(_i,n,type) rept(_i,0,n,type)
#define repi0(_i,n) rept(_i,0,n,int)
#define repl0(_i,n) rept(_i,0,n,ll)

//#define repst(_i,iv,n,type) for(type _i=iv;_i<=(type)(n);++_i)
//#define repsi1(_i,n) repst(_i,1,n,int)

#define REPT(_i,iv,_l,n,type) for(type _i=(type)(iv),_l=(type)(n);_i<_l;++_i)
//#define REPI(_i,iv,_l,n) REPT(_i,iv,_l,n,int)
//#define REPL(_i,iv,_l,n) REPT(_i,iv,_l,n,ll)
//
#define REPT0(_i,_l,n,type) REPT(_i,0,_l,n,type)
#define REPI0(_i,_l,n) REPT(_i,0,_l,n,int)
#define REPL0(_i,_l,n) REPT(_i,0,_l,n,ll)


//#define rrept(_i,x,e,type) for(type _i=((type)(x)-1);_i>=e;--_i)
//
//#define rrept0(_i,x,type) rrept(_i,x,0,type)
//
//#define RREPT(_i,x,_e,e,type) for(type _i=((type)(x)-1),_e=(type)(e);_i>=_e;--_i)
//
//#define RREPT0(_i,x,_e,type) RREPT(_i,x,_e,0,type)
//
//#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

//#define all(x) (x).begin(),(x).end()
#define REPV(v,_itr,_end) for(auto _itr=(v).begin(),_end=(v).end();_itr!=_end;++_itr)
#define REPVC(v,_itr,_end) for(auto _itr=(v).cbegin(),_end=(v).cend();_itr!=_end;++_itr)

#define td typedef
//#define tds(stl,type,name) typedef stl<type > name;
#define tdv(type,name) typedef vector<type > name;


//typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<vb > vvb;
typedef vector<int> vi;
typedef vector<vi > vvi;
//typedef vector<ll> vll;
//typedef vector<vll > vvll;

#define MOD7 1'000'000'007
#define MOD9 1'000'000'009

int main(int argc, const char * argv[]) {
    string N;
    cin>>N;
    int sum=0;
    
    REPI0(i, len, N.length()){
        int num=(N[i]-'0');
        sum+=num;
    }
    cout<<((sum%9==0)?"Yes":"No")<<endl;
    return 0;
}


Measured memory_bytes: 3312
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
    static class TaskC {
        static long modpow(long a , int b){
            a%=1000000007;
            long ans = 1;
            while (b>0){
                if ((b&1)>0) ans=ans*a%1000000007;
                b>>=1;
                a=a*a%1000000007;
            }
            return ans;
        }
        public void solve(int testNumber, InputReader in, PrintWriter out){
            int n = in.nextInt();
            int k = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i <n ; i++) {
             arr[i]=in.nextInt();
            }
            Arrays.sort(arr);
            long ans = 0;
            for (int i = 0; i <n-k; i++) {
                ans+=arr[i];
            }
            System.out.println(ans);








        }




    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt(){return  Integer.parseInt(next());}
        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}

Measured memory_bytes: 52640
#include <string>
#include <set>
#include <iostream>
using namespace std;

int main() {
    int k;
    string s;
    cin >> s >> k;
    int n = s.size();
    set<string> se;
    for(int l=1; l<=5; l++){
        for(int i=0; i<=n-l; i++){
            se.insert(s.substr(i, l));
        }
    }
    
    for(auto c: se){
        k--;
        if(k==0) cout << c << endl;
    }
    return 0;
}

Measured memory_bytes: 1664
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn main() {
    let n : i64 = read();
    match n {
        0 =>{
            println!("2");
        },
        1 => {
            println!("1");
        }
        _ => {
            let ans = calc(n);
            println!("{}",ans);
        }
    }

}       
fn calc(n: i64) -> i64 {
    let mut f1 = 2;
    let mut f2 = 1;
    let mut tmp = 0;
    for _ in 0..n - 1 {
        tmp = f1 + f2;
        f1 = f2;
        f2 = tmp;
    }
    tmp
}

Measured memory_bytes: 4352
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int main() {
	int H, W;
	while (cin >> H >> W && (H || W)) {
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	}
}

Measured memory_bytes: 3088
#include "bits/stdc++.h"
using namespace std;

int main()
{
	int h, w;
	cin >> h >> w;
	string init = "";
	for (int i = 0; i < w + 2; i++) init += "#";
	vector<string> v(h+2, init);
	for (int i = 0; i < h; i++) {
		string ai;
		cin >> ai;
		ai = "#" + ai + "#";
		v.at(i+1) = ai;
	}

	for (int i = 0; i < h+2; i++) {
		cout << v.at(i) << endl;
	}


    return 0;
}

Measured memory_bytes: 256
/* 	* In the name of GOD 
 * Thanks God */
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define int long long

void solve() {
	int x, k, d;
	cin >> x >> k >> d;
	x = abs(x);
	if (x / d >= k) {
		cout << x - (d * k);
		return;
	}
	if (k % 2 == 0 && (x / d % 2)) {	
		if (k >= (x / d - 1) && k >= (x / d + 1))
			cout << min(abs(x - ((x / d - 1) * d)), abs(x - (x / d + 1) * d));
		else if(k >= (x / d - 1)) 
			cout << abs(x - ((x / d - 1) * d));
		return;
	}
	if (k % 2 == 0 && (x / d % 2 == 0)) {	
		if (k >= (x / d) && k >= (x / d + 2))
			cout << min(abs(x - ((x / d) * d)), abs(x - (x / d + 2) * d));
		else if(k >= (x / d)) 
			cout << abs(x - ((x / d) * d));
		return;
	}
	if (k % 2 && (x / d % 2 == 0)) {	
		if (k >= (x / d - 1) && k >= (x / d + 1))
			cout << min(abs(x - ((x / d - 1) * d)), abs(x - (x / d + 1) * d));
		else if(k >= (x / d - 1)) 
			cout << abs(x - ((x / d - 1) * d));
		return;
	}
	if (k % 2 && (x / d % 2)) {	
		if (k >= (x / d) && k >= (x / d + 2))
			cout << min(abs(x - ((x / d) * d)), abs(x - (x / d + 2) * d));
		else if(k >= (x / d)) 
			cout << abs(x - ((x / d) * d));
		return;
	}
}

int32_t main() {
	int t = 1;
	//	cin >> t;
	while (t--) {
		solve();
	}
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> prime;
bool isPrime[55556];
int main() {
  fill(isPrime, isPrime + 55556, true);
  isPrime[0] = isPrime[1] = false;
  for (int i = 2; i < 55556; i++) {
    if (isPrime[i]) {
      prime.push_back(i);
      for (int j = i * 2; j < 55556; j += i) {
        isPrime[j] = false;
      }
    }
  }
  int n;
  scanf("%d", &n);
  int x = 0;
  for (int i = 0; i < prime.size(); i++) {
    if (prime[i] % 5 == 1) {
      printf("%d", prime[i]);
      x++;
    }
    if (x == n)
      break;
    printf(" ");
  }
  puts("");
}


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

void islandExplore( char m[14][14], int i, int j )
{
    m[i][j] = '2';                       //島探検済み

    if( m[i-1][j] != '1' && m[i+1][j] != '1' && m[i][j-1] != '1' && m[i][j+1] != '1' )      //未探索の島が無い場合終了
        return;

    if( m[i-1][j] == '1' )              //左の領域を探索
        islandExplore( m, i - 1, j );
    if( m[i+1][j] == '1' )              //右の領域を探索
        islandExplore( m, i + 1, j );
    if( m[i][j+1] == '1' )              //下の領域を探索
        islandExplore( m, i, j + 1 );
    if( m[i][j-1] == '1' )              //上の領域を探索
        islandExplore( m, i, j - 1 );
}

int main()
{   
    char map[14][14];
    for( int i = 0; i < 14; i++ )
        for( int j = 0; j < 14; j++ )
            map[i][j] = '0';

    string str;
    int s = 1;
    while( cin >> str )
    {
        int cnt = 0;                            //初期化
        for( int i = 0; i < str.size(); i++ )   //1行ずつ入力
            map[i+1][s] = str[i];

        if( s == 12 )
        {
            for( int i = 1; i <= 12; i++ )          //マスを一つずつ探索
                for( int j = 1; j <= 12; j++ )
                {
                    if( map[i][j] == '1' )
                    {
                        cnt++;
                        islandExplore( map, i, j ); //島をすみずみ探検して、繋がりを把握
                    }
                }
            cout << cnt << endl;
            s = 0;
        }
        s++;
    }
    return 0;
}


Measured memory_bytes: 3048
main = getLine >>= print . compute . read

base = 10^9+7

compute :: Int -> Int
compute n = loop n 10 9 8 1 1 1

loop 0 _ _ _ acc10 acc9 acc8 = (acc10 + acc8 - 2 * acc9) `mod` base
loop n pow10 pow9 pow8 acc10 acc9 acc8
  | odd n = loop1 (m acc10 pow10) (m acc9 pow9) (m acc8 pow8)
  | True  = loop1    acc10           acc9          acc8
  where
    loop1 = loop (n `div` 2) (p pow10) (p pow9) (p pow8)

p x = m x x
m x y = x*y `mod` base
{-
0から9任意 = 10^n : A
0から8任意 = 9^n : B   A-B = 9が1つはある
1から9任意 = 9^n : C   A-C = 0が1つはある
1から8任意 = 8^n : D   A-(B+C-D) = 求めるもの
-}

Measured memory_bytes: 3828
//不能简单的判断原串相等，后面也得子串和子串
//旋转必定在最后
//abaaabaa与baaabaaa
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.nextLine();
		String T = sc.nextLine();
		int k = 0;
		int j = 0;
		if(S.equals(T)) {
			System.out.println("Yes");
		}else {
			for (int i = 0; i <= S.length(); i++) {
				String a = S.substring(0, i);
				if(!T.contains(a)) {
					j = i - 1;
					k = T.lastIndexOf(a.substring(0,i-1));
					break;
				}
			}
			if(k==0||k==-1) {
				System.out.println("No");
			}else {
				//System.out.println(T.substring(0,k));
				//System.out.println(S.substring(j,S.length()-1));
				if(T.substring(0,k).equals(S.substring(j,S.length()))) {
					System.out.println("Yes");
				}else {
					System.out.println("No");
				}
			}
		}
		
		
		
	}

}


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

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define ldb long double 
#define db double
#define str string

#define fr first
#define se second
#define lb lower_bound 
#define ub upper_bound 
#define pb push_back
#define mp make_pair

#define pi pair<int,int>
#define pll pair<ll,ll>
#define pdb pair<db,db>
#define pldb pair<ldb,ldb>

#define vi vector<int>
#define vll vector<ll>
#define vdb vector<db>
#define vldb vector<ldb>
#define vpi vector< pi >
#define vpll vector< pll >

#define mi map<int,int>
#define mll map<ll,ll>
#define mdb map<db,db>
#define mldb map<ldb,ldb>


#define forr(a,b) for (int i = (a); i < (b); ++i)
#define rrof(a,b) for (int i = (b)-1; i >= (a); --i)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int md = 1e9+7;
const int MX = 2e5+5;
const ll INF = 1e18; 
const ldb PI = 4*atan((ldb)1);

ll power(ll a,ll n)
{
 ll res=1;
 while(n)
{
 if(n%2)
  res=res%md*a%md;
  a=a%md*a%md;
  n/=2;
}
res%=md;
return res;
}

ll abst(ll a)
{
 return ((a<0)?(-1*a):(a));
}

ll fact[200001];
int main()
{
    fast;
    fact[0]=fact[1]=1;
    for(int i=2;i<=200000;i++)
    {
        fact[i]=(fact[i-1]%md*i)%md;
    }
    ll n,k;
    cin>>n>>k;
    ll arr[n];
    for(int i=0;i<n;i++)
     cin>>arr[i];
    sort(arr,arr+n);
    ll maxc=0,minc=0;
    for(int i=k-1;i<n;i++)
    {
        ll p=i;
        maxc=(maxc%md+((fact[p]%md*(power(fact[k-1],md-2)%md*power(fact[p-(k-1)],md-2)%md)%md)%md*arr[i]%md))%md;
    }
    for(int i=(n-k);i>=0;i--)
    {
        ll p=n-i-1;
        minc=(minc%md+((fact[p]%md*(power(fact[k-1],md-2)%md*power(fact[p-(k-1)],md-2)%md)%md)%md*arr[i]%md))%md;
    }
    ll res=(maxc-minc+md)%md;
    cout<<res<<"\n";
    return 0;
}

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

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

  vector<string> data(N);
  for(int i=0; i<N; i++){
    cin >> data.at(i);
  }

  int NfootA= 0;
  int NheadB= 0;
  int Nchimera= 0;
  int cnt_intra= 0;
  for(auto word:data){
    if(word.back()=='A' && word.at(0)=='B'){
      Nchimera++;
    }
    else if(word.back()=='A'){
      NfootA++;
    }
    else if(word.at(0)=='B'){
      NheadB++;
    }

    for(size_t i=0; i< word.size()- 2; i++){
      if(word.substr(i,2)=="AB"){
        cnt_intra++;
      }
    }
  }

  int cnt_inter= 0;
  if(Nchimera > 0){
    cnt_inter+= Nchimera- 1;
    if(NfootA > 0){
      cnt_inter++;
      NfootA--;
    }
    if(NheadB > 0){
      cnt_inter++;
      NheadB--;
    }
  }
  
  cnt_inter+= min(NfootA, NheadB);

  int ans= cnt_intra+ cnt_inter;

  cout << ans << endl;
}

Measured memory_bytes: 3580
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    h,w = LI()
    a = [[c for c in S()] for _ in range(h)]
    s = None
    lc = 0
    for i in range(h):
        for j in range(w):
            c = a[i][j]
            if c == '.':
                continue
            if c == 'o':
                lc += 1
                continue
            s = (i,j,c)

    def f(i,j,c,d):
        if d == lc:
            return (True, '')
        a[i][j] = '.'
        if c != 'U':
            for k in range(i+1,h):
                if a[k][j] == 'o':
                    rf,rs = f(k,j,'D',d+1)
                    if rf:
                        return (True, 'D' + rs)
                    break
        if c != 'D':
            for k in range(i-1,-1,-1):
                if a[k][j] == 'o':
                    rf,rs = f(k,j,'U',d+1)
                    if rf:
                        return (True, 'U' + rs)
                    break
        if c != 'L':
            for k in range(j+1,w):
                if a[i][k] == 'o':
                    rf,rs = f(i,k,'R',d+1)
                    if rf:
                        return (True, 'R' + rs)
                    break
        if c != 'R':
            for k in range(j-1,-1,-1):
                if a[i][k] == 'o':
                    rf,rs = f(i,k,'L',d+1)
                    if rf:
                        return (True, 'L' + rs)
                    break

        a[i][j] = 'o'
        return (False, None)

    rf,rs = f(s[0],s[1],s[2],0)
    return rs


print(main())



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

long gcd(long a, long b){
   if (a%b == 0){
       return(b);
   } else {
       return(gcd(b, a%b));
   }
}

int main(){
  int N; cin >> N;
  vector<long> v(N);
  for(int i = 0; i < N ; i++){
   cin >> v.at(i);
  }
  
  // left[i]: v[0:i]の最大公約数
  // right[i]:v[i-N-1]の最大公約数
  
  vector<long> left(N);
  vector<long> right(N);

  long tmp = v.at(0);  
  for(int i = 0; i < N; i++){
    tmp = gcd(tmp, v.at(i));
    left.at(i) = tmp;
  }
  
  tmp = v.at(N-1);
  for(int i = N-1; i >= 0; i--){
    tmp = gcd(tmp, v.at(i));
    right.at(i) = tmp;
  }
  
  // left[i-1] とright[i+1]の最大公約数の最大値
  
  long ans = 1;
  for(int i = 0; i < N; i++){
    if(i == 0){
      ans = max(ans, right[i+1]);
    } else if(i == N-1){
      ans = max(ans, left[i-1]);
    } else {
      ans = max(ans, gcd(left[i-1], right[i+1]));
    }
    
    //cerr << "i: " << i << " left: " << left[i] << " right: " << right[i] << endl;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 2560
#include<iostream>
#include<cstdio>
#include<math.h>
#define rep(i,a) for(int i = 0; i < a; i++)
using namespace std;

int main(){
	int m, f, r;
	while(1){
		cin >> m >> f >> r;
		if(m == -1 && f == -1 && r == -1) break; //入力終了

		if(m == -1 || f == -1)	cout << "F" << endl; //一つでも受けない
		else{										
				if(m + f >= 80) cout << "A" << endl;
				else if(m + f >= 65) cout << "B" << endl;
				else if(m + f >= 50) cout << "C" << endl;
				else if(m + f >= 30){
					if(r >= 50){
						cout << "C" << endl;
					}else{
						cout << "D" << endl;
					}
				}
				else cout << "F" << endl;
		}
	}
}

Measured memory_bytes: 1152
N = int(input())
A = list(map(int, input().split()))

l = []
for i in range(1, N + 1):
  l.append([A[i - 1], i])
l.sort()

for i in range(N):
  print(l[i][1], end = "")
  if i == N - 1:
    print()
  else:
    print(" ", end = "")

Measured memory_bytes: 21524
/*
	Name:
	Author: xiaruize
	Date:
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define ll long long
#define form(i,j,n) for(int i=int(j);i<=int(n);i++)
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define pis pair<int,string>
#define sec second
#define sz(a) int((a).size())

inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}

int a[200005];
int cnt[200005];

int main()
{
 	ios::sync_with_stdio(false);
	cin.tie(0);
 	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	while(k--)
	{
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)
		{
			cnt[max(i-a[i],0)]++;
			cnt[min(i+a[i]+1,200001)]--;
		}
		int num=cnt[0];
		for(int i=1;i<=n;i++)
		{
			num+=cnt[i];
			a[i]=num;
		}
		bool flag=true;
		for(int i=1;i<=n;i++)
		{
			if(a[i]!=n)
			{
				flag=false;
				break;
			}
		}
		if(flag)
		{
			break;
		}
	}	
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<' ';
	}
	return 0;
}


Measured memory_bytes: 5216
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt,ans,a[ohara],b[ohara],c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>n>>k;
    rep(i,n)cin>>a[i]>>b[i];
    c=k;
    while(1){
        c/=2;
        d++;
        if(c==0)break;
    }
    //cout<<"\n";
    tmp=0;
    rrrep(i,d,0){
        if((k&(1LL<<i))!=0){
            tmpp=0;
            if(tmp<k){
            rrep(j,0,i){
            tmpp=(tmpp|(1LL<<j));
            }
            }
            if((tmp|tmpp)<=k){
            pos=(tmp|tmpp);
            }
            else{
                pos=tmp;
            }
            if(i==0)pos=k;
            rep(j,n){
                if((pos|a[j])==pos)cnt+=b[j];
            }
            //cout<<i<<" "<<pos<<"\n";
            ans=max(ans,cnt);
            //Cout(cnt);
            tmp=(tmp|(k&(1LL<<i)));
            cnt=0;
        }
    }
    rep(i,n){
        if((k|a[i])==k)cnt+=b[i];
    }
    Cout(max(ans,cnt));
    return 0;
}


Measured memory_bytes: 5120
#include<iostream>
using namespace std;
int main()
{
	int x1,x2,y1,y2,x3,y3,x4,y4;
	cin>>x1>>y1>>x2>>y2;
	int vx=x2-x1;
	int vy=y2-y1;
	int vvx=-vy;
	int vvy=vx;
	x3=x2+vvx;
	y3=y2+vvy;
	x4=x3-vx;
	y4=y3-vy;
	cout<<x3<<" "<<y3<<" "<<x4<<" "<<y4<<endl;
	return 0;
}

Measured memory_bytes: 888