akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define fi first
#define se second
#define pb push_back
#define forn(i,n) for(int i=0;i<(n);i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forr(i,n) for(int i=n;i>=0;i--)
#define all(x) x.begin(), x.end()
const int MAXN = 1e5 +5;

void fio(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}

int main(){
  fio();
  string s; cin>>s;
  if(s[0]>='a' && s[0]<='z'){
  	cout<<"a"<<endl;
  }
  else cout<<"A"<<endl;
  return 0;
}

Measured memory_bytes: 3636
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for x,y,z in src:
    x,y = x-1,y-1
    uf.unite(x,y)
print(N - uf.count)

Measured memory_bytes: 22144
#include <bits/stdc++.h>
#define debug(x) cout << #x << " -> " << x << endl
#define booga cout << "booga" << endl
#define ll long long int
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;


void testcase(){
	ll n,a = 0,w = 0,t = 0,e = 0;
	cin >> n;
	while(n--){
		string s;
		cin >> s;
		if(s == "AC"){
			a++;
		}
		if(s == "WA"){
			w++;
		}
		if(s == "TLE"){
			t++;
		}
		if(s == "RE"){
			e++;
		}
	}
	cout << "AC x " << a << "\n";
	cout << "WA x " << w << "\n";
	cout << "TLE x " << t << "\n";
	cout << "RE x " << e << "\n";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while(t--){
		testcase();
	}
	return 0;
}


Measured memory_bytes: 3660
N = int(input())
students = list(map(int, input().split()))
seat_num = {}
for i,student in enumerate(students ,1):
    seat_num[i] = student
seat_num_sort = sorted(seat_num.items(), key =lambda x: x[1])
seat_result = [s[0] for s in seat_num_sort]
print(' '.join(map(str, seat_result)))

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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    UnionFind(int N) : par(N),siz(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++){
             par[i] = i;
             siz[i] = 1;
        }
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        // merge technique（小を大にくっつける）
        if (siz[rx] < siz[ry]) swap(rx, ry);
        siz[rx] += siz[ry];
        par[ry] = rx;
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    ll size(ll x){
        return siz[root(x)];
    }
};

signed main()
{   
    gearup;
    ll n,m; cin >> n >> m;
    vl a(m),b(m);
    rep(i,m) cin >> a[i] >> b[i];
    UnionFind uf(n);
    ll cnt = (n*(n-1))/2;
    vl res(m);
    //辺を追加して考えるので配列の後ろから探索
    rep(i,m){
        res[i]=cnt;
        int x = --a[m-1-i];
        int y = --b[m-1-i];
        if(uf.root(x)==uf.root(y))continue;
        cnt -= uf.size(x)*uf.size(y);
        uf.unite(x,y);
    }
    reverse(all(res));
    rep(i,m){
        cout << res[i] << endl;
    }
}


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

bool comp(const pair<string,int> a, const pair<string,int> b) {
  if (a.first != b.first)
    return a.first < b.first; // 高い順に並べたいので演算子を逆に
  else{
      return a.second > b.second;
  }
}

priority_queue<long long int,vector<long long int>, greater<long long int>> PQ;
priority_queue<long long int> PQ1;

int main(){
  int N;
  cin >>N;
  vector<string> list;
  for(int i  = 0;i<N;i++){
      string s;
      cin >>s;
      list.push_back(s);

  }

  char befor = list[0][list[0].length()-1];

  for(int i  = 1;i<N;i++){
      bool flg = false;

    

      for(int j = 0;j<i;j++){
          if(list[i] == list[j])flg = true;
          
      }
      if(flg || befor != list[i][0]){
          cout <<"No"<<endl;
          return 0;
      }
      befor = list[i][list[i].length()-1];
  }

  cout <<"Yes"<<endl;

  

  return 0;
}

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

#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++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    int N; cin >> N;
    int a = 0;
    int w= 0;
    int t=0;
    int r =0;
    REP(i,N){

        
        string S; cin >> S;
        if(S[0] == 'A'){
            a++;
        }else if(S[0] == 'W'){
            w++;
        }else if(S[0] == 'T'){
            t++;
        }else if(S[0] == 'R'){
            r++;
        }
    }
    cout << "AC x " << a << endl;
    cout << "WA x " << w << endl;
    cout << "TLE x " << t << endl;
    cout << "RE x " << r << endl;
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
int main(){
  ll q;cin>>q;
  rep(i,q){
    ll x,y;
    cin>>x>>y;
    if(x>y)swap(x,y);
    ll ans=x-1;
    long double k=sqrt(x*y-0.75)-x+0.5;
    ll lk=k;
    ans+=k+(x*y-1)/(x+k);
    if(x==y)cout<<ans<<endl;
    else cout<<ans-1<<endl;
  }
}


Measured memory_bytes: 3564
#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int a[262144],rev[262144],lw[262144],hi[262144],val[262144];
struct pr{
	int x,y;
	pr(int a=0,int b=0){x=a;y=b;}
};
bool operator<(pr a,pr b){return a.x==b.x?a.y>b.y:a.x>b.x;}
priority_queue<pr>q;
vector<pr>e[262144];
int main(){
	int n,N,i,j;
	scanf("%d",&n);
	N=1<<n;
	for(i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(n-1));
	for(i=0;i<N;i++){
		scanf("%d",a+i);
		a[i]--;
	}
	for(i=N-1;i>=0;i--){
		hi[i]=~a[i]?a[i]:N-1;
		for(j=0;j<n;j++){
			if(~i>>j&1)hi[i]=min(hi[i],hi[i|(1<<j)]);
		}
	}
	for(i=0;i<N;i++){
		lw[i]=~a[i]?a[i]:0;
		for(j=0;j<n;j++){
			if(i>>j&1)lw[i]=max(lw[i],lw[i^(1<<j)]);
		}
	}
	for(i=0;i<N;i++){
		if(lw[i]>hi[i]){
			puts("NO");
			return 0;
		}
		e[lw[i]].push_back(pr(hi[i],i));
	}
	for(i=0;i<N;i++){
		for(pr t:e[i])q.push(t);
		if(q.empty()||q.top().x<i){
			puts("NO");
			return 0;
		}
		val[q.top().y]=i;
		q.pop();
	}
	puts("YES");
	for(i=0;i<N;i++)printf("%d ",val[rev[i]]+1);
}

Measured memory_bytes: 21248
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

H, W = map(int, input().split())
S = [input() for _ in range(H)]

g = [[0] * (H * W) for _ in range(H * W)]
for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        if y - 1 >= 0 and S[y - 1][x] != '#':
            g[y * W + x][(y - 1) * W + x] = 1
        if y + 1 < H and S[y + 1][x] != '#':
            g[y * W + x][(y + 1) * W + x] = 1
        if x - 1 >= 0 and S[y][x - 1] != '#':
            g[y * W + x][y * W + x - 1] = 1
        if x + 1 < W and S[y][x + 1] != '#':
            g[y * W + x][y * W + x + 1] = 1
g = floyd_warshall(csgraph_from_dense(g))

result = 0
for i in range(H * W):
    for j in range(H * W):
        if g[i][j] == float('inf'):
            continue
        result = max(result, g[i][j])
print(int(result))


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

int bubblesort(char C[][2],int N){
    for (int i=0; i<N; i++){
        for (int j=N-1; j>i; j--){
            if (C[j][1] < C[j-1][1]){
                char v1 = C[j][0];
                int v2 = (int)C[j][1];
                C[j][0] = C[j-1][0];
                C[j-1][0] = v1;
                C[j][1] = C[j-1][1];
                C[j-1][1] = v2;
            }
        }
    }
}


int selectionsort(char C[][2], int N){
    for (int i=0; i<N; i++){
        int minj = i;
        for (int j=i; j<N; j++){
            if(C[j][1] < C[minj][1]) minj = j;
        }
        if (i!=minj){
            char v1 = C[i][0];
            int v2 = C[i][1];
            C[i][0] = C[minj][0];
            C[minj][0] = v1; 
            C[i][1] = C[minj][1];
            C[minj][1] = v2;
        }
    }
}


int main(){
    int N;
    cin >> N;
    char C1[N][2],C2[N][2];
    string str;
    for (int i=0; i<N; i++){
        cin >> str;
        C1[i][0] = (char)str[0];
        C1[i][1] = (char)str[1];
        C2[i][0] = (char)str[0];
        C2[i][1] = (char)str[1];
    }
    
    bubblesort(C1,N);
    for (int j=0; j<N; j++){
        if (j==N-1) cout << C1[j][0] << C1[j][1] << "\n";
        else cout << C1[j][0] << C1[j][1] << " ";
        }
    cout << "Stable" << "\n";
    
    

    
    selectionsort(C2,N);
    for (int k=0; k<N; k++){
        if (k==N-1) cout << C2[k][0] << C2[k][1] << "\n";
        else cout << C2[k][0] << C2[k][1] << " ";
    }
    int check = 1;
    for (int m=0; m<N; m++){
        if (C1[m][0] != C2[m][0]) check = 0;
    }
    
    if (check) cout << "Stable" << "\n";
    else cout << "Not stable" << "\n";
    
    return 0;
    
    
}



Measured memory_bytes: 3160
import std.stdio, std.string, std.conv, std.algorithm, std.array;

void main(){
	while(1){
		auto ffffffffff = readln.chomp.to!(int);
		if(ffffffffff==0) break; 
		int a = 1000 - ffffffffff;
	int ans;
	if(a>=500){
		ans++;
		a-=500;
	}
	if(a>=100){
		ans += a/100;
		a -= a/100*100;
	}
	if(a>=50){
		ans ++;
		a -= 50;
	}
	if(a>=10){
		ans += a/10;
		a -= a/10*10;
	}
	if(a>=5){
		ans++;
		a -= 5;
	}
	ans += a;
	writeln(ans);
}
}

Measured memory_bytes: 2472
#include<bits/stdc++.h>
#define ll long long
#define PLI pair<ll,int>
using namespace std;

int main()
{
//	freopen("UVA1636_input.txt","r",stdin); 
//	 freopen("UVA1636_out.txt","w",stdout);	
	ll k,x;
	cin>>k>>x;
	for(ll i=(x-k+1);i<=(x+k-1);i++)
	{
		cout<<i<<" ";
	}
	return 0;
}

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

int main() {
  int N, k;
  cin >> N;
  cin >> k;
  int i, j;
  j = 1;
  for (i = 0; i < N; i++){
    int a, b;
    a = j * 2;
    b = j + k;
    if (a <= b)
      j = a;
    else
      j = b;
  }	//forの最後
  cout << j << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<queue>
#include<set>
#include<stack>
#include<map>

using namespace std;

int main(){
    int N,Z,W;
    cin>>N>>Z>>W;
    int A[2000];
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    //A[N-1]で色々な要素を調整
    W=abs(W-A[N-1]);
    for(int i=0;i<N-1;i++){
        A[i]=abs(A[i]-A[N-1]);
    }
    A[N-1]=0;
    if(N==1){
        cout<<W<<endl;
        return 0;
    }
    //N>=2と仮定する
    int dpF[2000]={};//YがA[i]を取った時の最終結果
    int dpG[2000]={};//XがA[i]を取った時の最終結果
    dpF[N-2]=A[N-2]; dpG[N-2]=A[N-2];
    for(int i=N-3;i>=0;i--){
        //dpF[i]とdpG[i]を求めたい
        dpF[i]=A[i];
        for(int j=i+1;j<N-1;j++){
            dpF[i]=max(dpF[i],dpG[j]);
        }
        dpG[i]=A[i];
        for(int j=i+1;j<N-1;j++){
            dpG[i]=min(dpG[i],dpF[j]);
        }
    }
    int ans=W;
    for(int i=0;i<N-1;i++){
        ans=max(ans,dpG[i]);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
e1,e2,e3,e4 = map(int,input().split())
if e1 == e2 and e3 == e4:
    print('yes')
elif e1 == e3 and e2 == e4:
    print('yes')
elif e1 == e4 and e2 == e3:
    print('yes')
else:
    print('no')


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

using ll = long long int;
using ullong = unsigned long long;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b)  for(int i = (a); i < (b) ; i++)
#define pb push_back
#define SORT(v,n) sort(v, v+n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define elif else if
#define int ll
const int INF = (1LL << 32);
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };


int N[10];
string s;
int ans = 0;

void bfs(int i,string n){
    if(i == s.size() - 1){        
        int sum = 0;
        int j = 0;
        string tmp = "";
        for(int j = 0; j <= n.size(); j++){
            if(isdigit(n[j])){
                tmp += n[j];
            }else if(!(isdigit(n[j]))){                
                sum += strtol(tmp.c_str(),nullptr,10);
                tmp.clear();
            }else if(j == n.size() -1){
                tmp += n[j];
                sum += strtol(tmp.c_str(),nullptr,10);
            }
        }
                
        ans += sum;
        return;
    }
    bfs(i+1,n + s[i+1]);
    bfs(i+1,n + "+" + s[i+1]);
}

signed main(){


cin >> s;
string a = to_string((int)(s[0] - '0'));
bfs(0,a);
cout << ans << endl;
return 0;
}


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

main(){
  int N,a,b,c,d;
  cin>>N;
  a=(N-N%1000)/1000;
  b=(N%1000-N%100)/100;
  c=(N%100-N%10)/10;
  d=N%10;
  
  if(a==b&&b==c||b==c&&b==d){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	sc := NewScanner()

	A, B := sc.NextInt(), sc.NextInt()
	switch {
	case A == B:
		fmt.Println("Draw")
	case A == 1:
		fmt.Println("Alice")
	case B == 1:
		fmt.Println("Bob")
	case A > B:
		fmt.Println("Alice")
	case B > A:
		fmt.Println("Bob")
	}

}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 640
from collections import deque
import sys
input = sys.stdin.readline


N = int(input())
G = [[] for _ in range(N)]
for _ in range(N):
    ls = list(map(int, input().split()))
    u = ls[0] - 1
    for v in ls[2:]:
        G[u].append(v - 1)

dist = [-1] * N
que = deque([0])
dist[0] = 0

while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

for v in range(N):
    print("{} {}".format(v + 1, dist[v]))


Measured memory_bytes: 6008
main :: IO ()
main = getLine >>= print . head . foldl calc [] . words

calc :: [Int] -> String -> [Int]
calc [] y = [read y]
calc xs@(_:[]) y = read y : xs
calc xa@(x1:x2:xs) y
  | y == "+" = x2 + x1 : xs
  | y == "-" = x2 - x1 : xs
  | y == "*" = x2 * x1 : xs
  | otherwise = read y : xa



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

int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	int a,ans=0;
	for (int i = 0; i < n; ++i)
	{
		cin>>a;
		while (a%2==0)
		{
			a/=2;
			++ans;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney, tree, chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun

#define REP(i,a,b) for(int i = a; i < b; ++i)
#define PRI(s) cout << s << endl
#define PRIY PRI("Yes")
#define PRIN PRI("No")

ll MOD = 1000000007;
ll mod(ll x) { return (x%MOD + MOD) % MOD; }

long long inverse(long long mod, long long val) {
	long long x[2] = { mod, val };
	long long a[2] = { 1, 0 };
	long long i;
	for (i = 0; x[!i]; i ^= 1) {
		a[!i] -= x[i] / x[!i] * a[i];
		x[i] = x[i] % x[!i];
	}
	if (!i) a[!i] += mod;
	return a[!i];
}

ll frac[510000];

ll com(ll a,ll b){
	if (a < b) return 0;
	return (((frac[a] * inverse(MOD, frac[b])) % MOD) * inverse(MOD, frac[a - b])) % MOD;
}

ll p(ll a, ll b) {
	if (a < b) return 0;
	return (frac[a] * inverse(MOD, frac[a - b])) % MOD;
}

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

	ll x = 1;
	frac[0] = 1;
	for (int i = 1; i < 510000; ++i) {
		x *= i;
		x %= MOD;
		frac[i] = x;
	}

	ll ret = 0;
	for (int i = 0; i <= n; ++i) {
		ll a = com(n, i) * p(m - i, n - i) * (i % 2 == 0 ? 1 : -1);
		a = mod(a);
		ret += a;
		ret = mod(ret);
	}
	ret *= p(m, n);
	ret = mod(ret);
	PRI(ret);
	return 0;
}




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

#define rep(i,n) for(int i=0;i<(n);++i)
#define int long long
#define pb push_back
#define m_p make_pair
#define m_t meke_tuple
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define debg(a) cout<<#a<<" "<<a<<endl;
#define call(a) for(auto i:a)cout<<i<<" ";cout<<endl
#define out(a) cout<<(a)<<endl
typedef long long ll;
typedef string str;
typedef vector<int> V;
typedef pair<int,int> P;
typedef vector<P> VP;
const int INF = 1LL<<60;
const int MOD = 1e9+7;
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void Yes(){cout<<"Yes"<<endl;}
void No(){cout<<"No"<<endl;}
void YN(bool b){cout<<(b?"Yes":"No")<<endl;}

int n,m;
V a;
vector<str>dp;
void chmax(str&a,str b){
  if(a=="!")a=b;
  else if(a.size()<b.size())a=b;
  else if(a.size()==b.size()){
    if(a<b)a=b;
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  cin>>n>>m;
  a=V(m);
  rep(i,m)cin>>a[i];
  dp=vector<str>(n+10,"!");
  V match={0,2,5,5,4,5,6,3,7,6};
  dp[0]="";
  
  rep(i,n+1){
    if(dp[i]=="!")continue;
    for(auto A:a)
      chmax(dp[i+match[A]],dp[i]+(char)('0'+A));
  }
  cout<<dp[n]<<endl;
  
  
  return 0;
}



Measured memory_bytes: 43776
import java.util.*;


public class Main{
	public static void main( String args[] ) {

		int N,A,B;
		int l,s;
		int max,min;
		
		Scanner scan = new Scanner( System.in );
		N = scan.nextInt();
		A = scan.nextInt();
		B = scan.nextInt();
		
		if( A > B ) {
			l = A;
			s = B;
		}
		else {
			l = B;
			s = A;
		}
		
	
		max = s;
		min = -1;
		
		min = (N - l - s ) * min;
		
		if(min < 0 ) {
			min = 0;
		}
		
		System.out.println( max + " " + min  );
		
		scan.close();
		
	}
}

Measured memory_bytes: 22228
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
S = input()
a = S.count('a')
b = S.count('b')
c = S.count('c')
if abs(a-b) <= 1 and abs(b-c) <= 1 and abs(a-c) <= 1:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 39280
N = int(input())
S = input()
sList = list(S)
s1 = ""
s2 = ""
halfN = int(N / 2)
if N % 2 == 0:
    for i in range(halfN):
        s1 = s1 + sList[i]
        s2 = s2 + sList[halfN + i]
    if s1 == s2:
        print('Yes')
    else:
        print('No')
else:
    print('No')


Measured memory_bytes: 3060
n,a=map(int,input().split())
ans=10**18
for k in range(41):
  l=0
  r=n
  while r-l!=1:
    m=(r+l)//2
    if m**(k+1)>=n:
      r=m
    else:
      l=m
  for m in range(k+2):
    if (l**m)*(r**((k+1)-m))>=n:
      ans=min(ans,k*a+l*m+r*((k+1)-m))
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    int d,g,p[10],c[10];
    cin>>d>>g;
    rep(i,d) cin>>p[i]>>c[i];
    int ans=1e9;
    rep(i,pow(2,d)){
        int q=i,m=0,z=0,A=0;
        rep(j,d){
            if(q%2) z+=p[j]*(j+1)*100+c[j],A+=p[j];
            else m=max(m,j+1);
            q=q/2;
        }
        if(z>=g) ans=min(ans,A);
        else{
            if((g-z)/(100*m)<=p[m-1]) A+=(g-z+100*m-1)/(100*m),ans=min(ans,A);
        }
    }
    cout<<ans;
}

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

const ll mod = 1000000007;


int main() {
	int n; cin >> n;
	vector<int> res(n);
	rep(i, n) cin >> res.at(i);
	sort(res.begin(), res.end());
	int ans = 100100100;
	for(int i = res.at(0); i <= res.at(n - 1); i++){
		int tmp = 0;
		for(int j = 0; j < n; j++){
			tmp += (res.at(j) - i)*(res.at(j) - i);
		}
		ans = min(ans, tmp);
	}
	cout << ans << endl;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define V vector<int>
using namespace std;
using ll = long long;

    
map<string,int> m;

int main(){
    int n; cin>>n;
    V a(n);
    set<ll> se;
    rep(i,0,n){
        cin>>a[i];
        se.insert(a[i]);
    }
    if(n==se.size()) cout<<"YES"<<"\n";
    else cout<<"NO"<<"\n";
}

Measured memory_bytes: 10368
N, A, B = map(int, input().split())
S = input()

X, Y = 0, 0
for s in S:
    if s == 'c':
        print('No')

    if s == 'a':
        if X + Y < A + B:
            print('Yes')
            X += 1
        else:
            print('No')

    if s == 'b':
        if X + Y < A + B and Y < B:
            print('Yes')
            Y += 1
        else:
            print('No')


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

int main()
{
    cin >> X;
    if (X >= 30)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}


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

#define range(i, l, r) for (int i = (int)l; i < (int)(r); ++(i))
#define rrange(i, l, r) for (int i = ((int)(r) - 1); i >= (int)l; --(i))

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define rwhole(f,x,...) ([&](decltype((x)) whole) { return (f)(rbegin(whole), rend(whole), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using int32 = int;
using int64 = long long;

const int mod     = 1e9 + 7;
const int32 inf   = 1001001001;
const int64 infll = 1001001001001001001ll;

const int dx[] = {0, -1, 1, 0, -1, 1, -1, 1}, dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const string YES = "YES", NO = "NO", Yes = "Yes", No = "No", yes = "yes", no = "no";

struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(16); cerr << fixed << setprecision(16); } } iosetup;

template <typename T = int64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } 
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.fs << " " << p.sc; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.fs >> p.sc; return is; }

template <typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

void solver() {
  int N = input();
  vector< int > H(N);
  cin >> H;

  bool ans = true;
  H[0]--;

  range(i, 1, N - 1) {
    if (H[i] - 1 >= H[i - 1]) H[i]--;
    if (H[i] > H[i + 1]) ans = false;
  }

  cout << (ans ? "Yes" : "No") << endl;
}

signed main(int argc, char *argv[]) {
  solver();
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;  
typedef long long ll;
typedef vector<ll> vint;
int main() {
  ll N;
  cin >> N;
  vint t(5);
  for (ll i=0;i<5;i++) cin >> t.at(i);
  
  for (ll i=0;i<4;i++) {
    if (t.at(i+1)-t.at(i)>=0) {
      t.at(i+1) = t.at(i);
    }
  }
  
  ll ans,x=t.at(4);
  if (N%x==0) {
    ans = 4+N/x;
  }
  else {
    ans = 4+N/x+1;
  }
  
  cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define endl "\n"
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
using namespace std;

void solve(){
	ll n,d;
	cin>>n>>d;
	ll x,y;
	ll sum = 0;
	for (int i = 0; i < n; ++i)
	{
		cin>>x>>y;
		if (x*x + y*y<=d*d)
		{
			sum++;
		}
	}
	cout<<sum<<endl;
}
  
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	ll t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 3648
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
    int N, i, ans, all;
    int A[100010];

    scanf("%d", &N);

    A[0] = 0;

    for (i = 1; i < N + 1; i++)
        scanf(" %d", &A[i]);

    A[N + 1] = 0;

    all = 0;

    for (i = 0; i < N + 1; i++)
    {
        all += fabs(A[i] - A[i + 1]);
    }

    for (i = 1; i < N + 1; i++)
    {
        ans = all;

        ans += fabs(A[i - 1] - A[i + 1]) - (fabs(A[i - 1] - A[i]) + fabs(A[i] - A[i + 1]));

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

    return 0;
}

Measured memory_bytes: 1536
l = int(input())-1
mount =list(map(int, input().split()))
downable = [0] * (l+1)
      
for i in range(l):
    if mount[i] >=mount[i+1]:
        downable[i] =1
        

i = l-1
while i >= 0:
    if  downable[i+1] != 0 and downable[i] != 0 :
        downable[i] = downable[i] + downable[i+1]
    i = i-1
        
print(max(downable))

Measured memory_bytes: 14252
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
using namespace std;

struct Node
{
    int key;
    Node *right, *left, *parent;
};

Node *root, *NIL;

void insert(int k)
{
    Node *y = NIL;
    Node *x = root;
    Node *z;

    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while (x != NIL)
    {
        y = x;
        if (z->key < x->key)
        {
            x = x->left;
        }
        else
        {
            x = x->right;
        }
    }
    z->parent = y;
    if (y == NIL)
    {
        root = z;
    }
    else
    {
        if (z->key < y->key)
        {
            y->left = z;
        }
        else
        {
            y->right = z;
        }
    }
}

void inorder(Node *u)
{
    if (u == NIL)
        return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}

void preorder(Node *u)
{
    if (u == NIL)
        return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

int main()
{
    int n, i, x;
    string com;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        cin >> com;
        if (com == "insert")
        {
            scanf("%d", &x);
            insert(x);
        }
        else if (com == "print")
        {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}


Measured memory_bytes: 26700
from collections import deque, Counter
N, M = map(int, input().split())
X = deque(maxlen=2 * M)
for _ in range(M):
    a, b = input().split()
    X.append(a)
    X.append(b)
c = Counter(X)
for i in range(1, N+1):
    i = str(i)
    print(c[i])

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> P;
int INF = -1000000;

int main() {
    int H,W;cin >> H >> W;
    char s[H][W] = {};
    for (int i = 0;i < H;i++){
        for (int j = 0;j < W;j++){
            cin >> s[i][j];
        }
    }
    int sx,sy;
    queue<P> que;
    int d[H][W] = {};
    int dx[4] = {1,0,-1,0};int dy[4] = {0,1,0,-1};
    int res = 0;
    for (int i = 0;i < H;i++){
        for (int j = 0;j < W;j++){
            
            if (s[i][j] == '#') continue;
            
            for (int k = 0;k < H;k++) {
                for (int l = 0; l < W; l++) {
                    d[k][l] = INF;
                }
            }

            sy = i;sx = j;
            que.push(P(sy,sx));
            d[sy][sx] = 0;

            while (que.size()){
                P p = que.front();que.pop();
                for (int i = 0;i < 4;i++){
                    int ny = p.first + dy[i];int nx = p.second + dx[i];
                    if (nx >= 0 && nx < W && ny >= 0 && ny < H && s[ny][nx] != '#' && d[ny][nx] == INF){
                        d[ny][nx] = d[p.first][p.second] + 1;
                        que.push(P(ny,nx));
                    }
                }
            }

            for (int k = 0;k < H;k++) {
                for (int l = 0; l < W; l++) {
                    res = max(res,d[k][l]);
                }
            }
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
const int MAX = 1e5 + 10;
const double exps = 1e-8;

inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a > b ? b : a; }
int l;
int main() {
    cin >> l;
    double ll = l;
    double ans = (ll / 3) * (ll / 3) * (ll / 3);
    printf("%.10f",ans);
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main () {
    long long int a,b;
    cin>>a>>b;
    if (a==1) {
        if (b==1) cout<<"1000000";
        if (b==2) cout<<"500000";
        if (b==3) cout<<"400000";
        if (b>3) cout<<"300000";
    }
    if (a==2) {
        if (b==1) cout<<"500000";
        if (b==2) cout<<"400000";
        if (b==3) cout<<"300000";
        if (b>3) cout<<"200000";
    } 
    if (a==3) {
        if (b==1) cout<<"400000";
        if (b==2) cout<<"300000";
        if (b==3) cout<<"200000";
        if (b>3) cout<<"100000";
    }
    if (a>3) {
      if (b==1) cout<<"300000";
        if (b==2) cout<<"200000";
        if (b==3) cout<<"100000";
        if (b>3) cout<<"0";
    }
    
}

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

int main(void)
{
  int a, b;
  int flag;
  int flag2=0;
  
  while(1)
    {
      cin >> a >> b;
      if(a == 0 && b == 0) break;
      flag = 0;
      if(flag2 != 0)cout << endl;

      for(int i = a ; i <= b ; i++)
	{
	  if(i % 4 == 0 && i % 100 != 0 || i % 400 == 0) 
	    {
	      cout << i << endl;
	      flag = 1;
	    }
	}
      if(flag == 0) cout << "NA" << endl;
      flag2 = 1;
    }
  return 0;
}

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	int n, x, t;	cin >> n >> x >> t;
	int ctr = ceil( 1.0*n / x);
	cout << ctr * t << '\n';
	return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	cout << (n - 1) * (m - 1) << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

import static java.lang.Integer.parseInt;

/**
 * Hamming Distance
 */
public class Main {

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

		int N, D;
		char[] X;

		N = parseInt(br.readLine());
		X = br.readLine().toCharArray();
		D = parseInt(br.readLine());

		char[] ans = Arrays.copyOf(X, N);

		for (int i = 0; i < N; i++) {
			if (D == 0) break;
			if (D > 0 && X[i] == '0') {
				ans[i] = '1';
				D--;
			}
		}

		for (int i = N - 1; i >= 0; i--) {
			if (D == 0) break;
			if (D > 0 && X[i] == '1') {
				ans[i] = '0';
				D--;
			}
		}

		System.out.println(String.valueOf(ans));

	} //end main
}

Measured memory_bytes: 24412
N = int(input())
h = list(map(int, input().split()))

MAX = pow(10, 4) * N
costs = [MAX for _ in range(N)]
costs[0] = 0

for h_i in range(N):
    if h_i < N-1:
        costs[h_i + 1] = min(abs(h[h_i + 1] - h[h_i]) + costs[h_i], costs[h_i + 1])

    if h_i < N-2:
        costs[h_i + 2] = min(abs(h[h_i + 2] - h[h_i]) + costs[h_i], costs[h_i + 2])


print(costs[N - 1])


Measured memory_bytes: 13928
function main(input) {
  var N = input[0].split(" ")[0]-0;
  var list = input[1].split(" ").map(v=>v-0);
  var a = {};
  var b = {};
  list.forEach((v,i)=>{
    if(i%2==0){
      a[v] = (a[v]||0)+1;
    }else{
      b[v] = (b[v]||0)+1;
    }
  });
  var alist = Object.keys(a).sort((aa,bb)=>a[bb]-a[aa]);  // 出現の多い順
  var blist = Object.keys(b).sort((aa,bb)=>b[bb]-b[aa]);
  var ans = 0;
  var abase,bbase = 0;
  if(alist[0] == blist[0]){
    if(a[alist[1]] < b[blist[1]]){
      abase = 0, bbase = 1;
    }else {
      abase = 1, bbase = 0;
    }
  }else{
    abase = 0, bbase=0;
  }
  alist.filter((v,i)=>i!=abase).forEach(v=>ans+=a[v]);
  blist.filter((v,i)=>i!=bbase).forEach(v=>ans+=b[v]);
  console.log(ans);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"))


Measured memory_bytes: 37164
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (n);i++)
using ll = long long;
const ll MOD=1000000007;
const double pi=acos(-1);

void make(vector<vector<int>> &A,int N,int M,vector<int> a)
{
  if(a.size()==N) {A.push_back(a); return;}
  if(a.size()==0)
  {
    rep(i,M)
    {
      make(A,N,M,{i+1});
    }
    return;
  }
  int l=a.at(a.size()-1);
  for(int i=l;i<=M;i++)
  {
    auto b=a;
    b.push_back(i);
    make(A,N,M,b);
  }
}  



int main() 
{
  int N,M,Q; cin>>N>>M>>Q;
  vector<vector<int>> A(0);
  make(A,N,M,{});
  /*
  for(auto a:A)
  {
    for(auto w:a)
    {
      cout<<w<<" ";
    }
    cout<<endl;
  }
  */
  
  vector<int> a(Q);
  vector<int> b(Q);
  vector<int> c(Q);
  vector<int> d(Q);
  rep(i,Q)
  {
    cin>>a.at(i)>>b.at(i)>>c.at(i)>>d.at(i);
    a.at(i)--;
    b.at(i)--;
  }
  
  int ans=0;
  for(auto hoge:A)
  {
    int sum=0;
    rep(i,Q)
    {
      if(hoge.at(b.at(i))-hoge.at(a.at(i))==c.at(i))
      {
        sum+=d.at(i);
      }
    }
    ans=max(sum,ans);
  }
  
  cout<<ans<<endl;
  
  return 0;
}



Measured memory_bytes: 13504
#include <stdio.h>

int main(void) {
	static char isPrime[1000001];
	static int caveInfo[3000][3000];
	static int pcNum[3000][3000];
	static int lastPc[3000][3000];
	int i,j;
	int m,n;
	/* eratosutenesu no furui */
	for(i=2;i<=1000000;i++)isPrime[i]=1;
	for(i=2;i<=1000000;i++) {
		if(isPrime[i]) {
			for(j=i+i;j<=1000000;j+=i)isPrime[j]=0;
		}
	}
	while(scanf("%d%d",&m,&n)==2 && (m|n)!=0) {
		int x=1500,y=1500;
		int minx=3000,miny=3000,maxx=0,maxy=0;
		int sx,sy;
		int cnt=1,nowNum=1;
		int res=1,res_pc=0;
		while(nowNum<=m) {
			for(i=0;i<cnt;i++) {
				if(nowNum==n){sx=x;sy=y;}
				if(x<minx)minx=x;
				if(y<miny)miny=y;
				if(maxx<x)maxx=x;
				if(maxy<y)maxy=y;
				caveInfo[y][x]=nowNum;
				pcNum[y][x]=lastPc[y][x]=0;
				nowNum++;
				x++;
			}
			for(i=0;i<cnt;i++) {
				if(nowNum==n){sx=x;sy=y;}
				if(x<minx)minx=x;
				if(y<miny)miny=y;
				if(maxx<x)maxx=x;
				if(maxy<y)maxy=y;
				caveInfo[y][x]=nowNum;
				pcNum[y][x]=lastPc[y][x]=0;
				nowNum++;
				y--;
			}
			cnt++;
			for(i=0;i<cnt;i++) {
				if(nowNum==n){sx=x;sy=y;}
				if(x<minx)minx=x;
				if(y<miny)miny=y;
				if(maxx<x)maxx=x;
				if(maxy<y)maxy=y;
				caveInfo[y][x]=nowNum;
				pcNum[y][x]=lastPc[y][x]=0;
				nowNum++;
				x--;
			}
			for(i=0;i<cnt;i++) {
				if(nowNum==n){sx=x;sy=y;}
				if(x<minx)minx=x;
				if(y<miny)miny=y;
				if(maxx<x)maxx=x;
				if(maxy<y)maxy=y;
				caveInfo[y][x]=nowNum;
				pcNum[y][x]=lastPc[y][x]=0;
				nowNum++;
				y++;
			}
			cnt++;
		}
		/* do search */
		if(isPrime[caveInfo[sy][sx]]) {
			res=pcNum[sy][sx]=2;
			res_pc=lastPc[sy][sx]=caveInfo[sy][sx];
		} else {
			pcNum[sy][sx]=1;
		}
		for(y=sy+1;y<=maxy;y++) {
			for(x=minx;x<=maxx;x++) {
				int best=0;
				int bestPc=0;
				if(caveInfo[y][x]>0 && caveInfo[y][x]<=m) {
					/* get data */
					if(minx<x && caveInfo[y-1][x-1]>0 && caveInfo[y-1][x-1]<=m) {
						if(pcNum[y-1][x-1]>best ||
						(pcNum[y-1][x-1]==best && lastPc[y-1][x-1]>bestPc)) {
							best=pcNum[y-1][x-1];
							bestPc=lastPc[y-1][x-1];
						}
					}
					if(caveInfo[y-1][x]>0 && caveInfo[y-1][x]<=m) {
						if(pcNum[y-1][x]>best ||
						(pcNum[y-1][x]==best && lastPc[y-1][x]>bestPc)) {
							best=pcNum[y-1][x];
							bestPc=lastPc[y-1][x];
						}
					}
					if(x<maxx && caveInfo[y-1][x+1]>0 && caveInfo[y-1][x+1]<=m) {
						if(pcNum[y-1][x+1]>best ||
						(pcNum[y-1][x+1]==best && lastPc[y-1][x+1]>bestPc)) {
							best=pcNum[y-1][x+1];
							bestPc=lastPc[y-1][x+1];
						}
					}
					/* is this cave prime? */
					if(best>0 && isPrime[caveInfo[y][x]]) {
						best++;
						bestPc=caveInfo[y][x];
					}
				}
				/* save the result */
				pcNum[y][x]=best;
				lastPc[y][x]=bestPc;
				/* update global result */
				if(best>0 && (best>res || (best==res && bestPc>res_pc))) {
					res=best;
					res_pc=bestPc;
				}
			}
		}
		printf("%d %d\n",res-1,res_pc);
	}
	return 0;
}

Measured memory_bytes: 42536
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
)

func main() {
	A := oneInt()
	for index := 0; index < A; index++ {
		val := oneInt()
		if val%2 == 0 {
			if val%3 == 0 || val%5 == 0 {

			} else {
				fmt.Print("DENIED")
				return
			}
		}
	}
	fmt.Print("APPROVED")
}

func exp(val int) float64 {
	var temp float64
	for index := 1; index <= val; index++ {
		temp += float64(index)
	}
	return temp / float64(val)
}

func searchAbove(slice []int, target int, index int) int {
	for i := index + 1; i < len(slice); i++ {
		v := slice[i]
		if v >= target {
			return i
		}
	}
	return -1
}

var sc = bufio.NewScanner(os.Stdin)

func oneInt() int {
	var a int
	fmt.Scan(&a)
	return a
}
func oneStr() string {
	var a string
	fmt.Scan(&a)
	return a
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func scanNums() (nums []int) {
	s := nextLine()
	numStr := strings.Split(s, " ")

	for _, n := range numStr {
		i, _ := strconv.Atoi(n)
		nums = append(nums, i)
	}
	return nums
}

func scanStrings() (strs []string) {
	s := nextLine()
	list := strings.Split(s, " ")
	strs = append(strs, list...)
	return strs
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func sortAsc(a []int) []int {
	sort.Ints(a)
	return a
}

func sortDesc(a []int) []int {
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	return a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	if a == 0 && b == 0 {
		return 0
	}
	return a * b / gcd(a, b)
}


Measured memory_bytes: 640
N, K = map(int, input().split())
p = list(map(int, input().split()))

a = 0
for i in range(N - K + 1):
  if i == 0:
    b = sum(p[0:K])
  else:
    b = b - p[i-1] + p[i + K - 1]
  
  if b > a:
    a = b
    f = i

ans = 0
for j in range(K):
  ans += (p[f + j] + 1) / 2

print(ans)

Measured memory_bytes: 25060
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define INIT    \
    cin.tie(0); \
    ios::sync_with_stdio(false);

template <class T>
inline bool chmax(T& a, T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline bool chmin(T& a, T b) {
    return a = (a > b) ? b : a;
}

ll const INF = 1LL << 60;
ll const MOD = 1000000007;

int main() {
    INIT;
    ll N, K;
    cin >> N >> K;

    ll a = N / K;
    ll b = (N + K / 2) / K;

    if (K % 2 == 0) {
        cout << a * a * a + b * b * b << endl;
    } else {
        cout << a * a * a << endl;
    }

    return 0;
}

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

typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)

const ll mod = 998244353;

//a^bにおいて、numがa、mulがbである
ll func(ll num, ll mul){
    ll val = 1;
    rep(i, mul){
        val = (val * num) % mod;
    }
    return val;
}

int main(){
    ll N;
    cin >> N;
    vector<ll> d(N);
    vector<ll> dist(N, 0);
    rep(i, N) cin >> d[i];
    ll mx = 0;
    ll ans = 1;
    
    //d[0] != 0であるときは、終了
    if(d[0] != 0){
        cout << 0 << endl;
        return 0;
    }
    //頂点1からの距離をインデックスの値にした配列
    //頂点からの距離がiの頂点が何個あるのかを格納
    rep(i, N) dist[d[i]]++;
    //距離0の頂点がただ1つだけであることを確かめる
    if(dist[0] != 1){
        cout << 0 << endl;
        return 0;
    }
    for(int i = 0; i < N-1; i++){
        if(dist[i] == 0 && dist[i+1] != 0) ans = 0;
        ans = (ans * func(dist[i], dist[i+1])) % mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4852
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;
typedef pair<P,ll> P2;
typedef pair<ll,P> PP;
int p[100001],r[100001];
void init(){rep(i,100001)p[i]=i,r[i]=0;}
int find(int x){return (p[x]==x)?x:(p[x]=find(p[x]));}
void unite(int x,int y) {
  x=find(x),y=find(y);
  if(x==y)return;
  if(r[x]<r[y])p[x]=y;
  else{p[y]=x;if(r[x]==r[y])r[x]++;}
}
bool same(int x,int y){return find(x)==find(y);}

void Main() {
  init();
  ll n;
  R n;
  vector<P> b(n);
  rep(i,n) cin >> b[i].F >> b[i].S;
  sort(all(b));
  b.erase(unique(all(b)),b.end());
  n=b.size();
  vector<P2> a(n);
  rep(i,n) a[i]=P2(b[i],i);
  sort(all(a));
  ll ans=0;
  priority_queue<PP,vector<PP>,greater<PP> > que;
  rep(k,2) {
    rep(i,n-1) que.push(PP(abs(a[i].F.F-a[i+1].F.F),P(a[i].S,a[i+1].S)));
    rep(i,n) swap(a[i].F.F,a[i].F.S);
    sort(all(a));
  }
  while(!que.empty()) {
    PP p=que.top();que.pop();
    int x=p.S.F,y=p.S.S;
    if(same(x,y)) continue;
    unite(x,y);
    ans+=p.F;
  }
  pr(ans);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 13168
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define rrep(i,n) for(int i=(n-1); i>=0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using ll = long long;
using namespace std;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
string S,T;
int main(){
    cin >> S >> T;
    bool flag = true;
    map<char,char> box; 
    rep(i,sz(T)){
        if(box[T[i]] == 0) box[T[i]] = S[i];
        else if(box[T[i]] != S[i]) flag = false;
    }
    
    set<char> cnt1,cnt2;
    rep(i,sz(S)) cnt1.insert(S[i]), cnt2.insert(T[i]);
    if(sz(cnt1) != sz(cnt2)) flag = false;
    
    if(flag) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}

Measured memory_bytes: 916