akhauriyash/Code-Regression huggingface dataset:
n,k=map(int,input().split())
x=n%k
while x>=0:
    x-=k
if x<0:
    x*=-1
y=x-k
if y <0:
    y*=-1
if x<y:
    print(x)
if x>y:
    print(y)
if x==y:
    print(x)

Measured memory_bytes: 3060
from collections import deque

def bfs(start, line):
    quene = deque([start])
    d = [None] * len(line) # reset distance from start
    d[start] = 0
    ans = [None] * len(line)
    while quene:
        v = quene.popleft()
        for i in line[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                ans[i] = v
                quene.append(i)
    return ans


def main():
    n,w = map(int,input().split()) #n:頂点数　w:辺の数
    checker = [0]
    line = [[] for _ in range(n)]
    for i in range(w):
        x,y= map(int,input().split()) 
        x -= 1
        y -= 1
        line[x].append(y)
        line[y].append(x)
    print("Yes")
    ans = bfs(0,line)
    for i in ans[1:]:
        print(i+1)

 
 
if __name__ == '__main__':
  main()

Measured memory_bytes: 34776
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


yn = 'YNeos'
ynflg = False
cnt = 0
ans = None

def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas



S = input()

# 出力
print('x'*len(S))




Measured memory_bytes: 5688
n=int(input())
a=input()
max=0

for i in range(1,n):
  count=0
  #print(a[:i],a[i:])
  l=set(a[:i])
  g=set(a[i:])
  #print(l,g)
  for j in l:
    if j in g: count+=1
  if max < count: max=count
print(max)
        

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

int main() {
  int64_t A, B, N; cin >> A >> B >> N;
  int r = N / B;
  
  int64_t x_1 = B * r - 1;
  int64_t a_1 = (A * x_1) / B;
  int64_t b_1 = x_1 / B;
  int64_t ans_1 = a_1 - A * b_1;
  
  int64_t x_2 = N;
  int64_t a_2 = (A * x_2) / B;
  int64_t b_2 = x_2 / B;
  int64_t ans_2 = a_2 - A * b_2;
  
  
  cout << max(ans_1, ans_2) << endl;
}

Measured memory_bytes: 3516
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define N 100
int main() {
    int a, b; cin >> a >> b;
    a--, b--;
    char g[N][N];
    rep(i, N/2) {
        rep(j, N) g[i][j] = '#';
    }
    rep(i, N/2) {
        rep(j, N) g[N/2+i][j] = '.';
    }
    //::::::::::::::::::::::::::::
    int cnt = 0;
    for(int i=0; i<N/2; i+=2) {
        int j = (i%2==0)?0:1;
        while(cnt < a) {
            g[i][j] = '.';
            j += 2;
            cnt++;
            if(j>=N) break;
        }
        if(cnt == a) break;
    }
    //::::::::::::::::::::::::::::
    cnt = 0;
    for(int i=N-1; i>=N/2; i-=2) {
        int j = (i%2==0)?1:0;
        while(cnt < b) {
            g[i][j] = '#';
            j += 2;
            cnt++;
            if(j>=N) break;
        }
        if(cnt == b) break;
    }
    //::::::::::::::::::::::::::::
    printf("%d %d\n",N,N);
    rep(i, N) {
        rep(j, N) {
            cout << g[i][j];
        }puts("");
    }
}


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

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#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, a, b) for(int i = a;i < b;++i)
#define ALL(x) (x).begin(),(x).end()
#define INF 999999999

#define lint long long

vector<int> to[200005];
int ans[200005];

void dfs(int v, int p = -1){
  for(int u: to[v]){
    if(u == p) continue;
    ans[u] += ans[v];
    dfs(u,v);
  }
}

int main()
{
  string s, t; cin >> s >> t;
  int count = 0;
  REP(i,3){
    if(s.at(i) == t.at(i)){
      	++count;
    }
  }
  cout << count << "\n";
  return 0;
}




Measured memory_bytes: 4992
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>

#define rep(i, a) REP(i, 0, a)
#define REP(i, a, b) for(int i = a; i < b; ++i)

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> P;
typedef std::pair<P, int> PP;
const double PI = 3.14159265358979323846;
const double esp = 1e-9;
const int infi = (int)1e+9 + 10;
const ll infll = (ll)1e+17 + 10;

int main(){
	int n;
	while (std::cin >> n, n){
		double s[1001];
		double m, a = 0;
		rep(i, n)std::cin >> s[i];
		m = std::accumulate(s, s + n, 0.0) / n;
		rep(i, n)a += (s[i] - m) * (s[i] - m);
		a /= n;
		a = sqrt(a);
		printf("%.10lf\n", a);
	}
	return 0;
}

Measured memory_bytes: 1244
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) (a<b?b:a)
#define F(i,L,R) for (int i = L; i < R; i++)
#define FE(i,L,R) for (int i = L; i <= R; i++)
#define RF(i,L,R) for (int i = L; i > R; i--)
#define RFE(i,L,R) for (int i = L; i >= R; i--)
#define getI(a) scanf("%d", &a)
#define getII(a,b) scanf("%d%d", &a, &b)
#define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define VgetI(n) int (n); scanf("%d",&(n))
#define VgetII(n,m) int (n),(m); scanf("%d %d",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k))
#define ll long long
#define INF 2000000000
#define nINF -2000000000
#define MOD 1e9+7
#define PI 3.1415926535897932384626
int mabs(int x){
	if(x<0) return (-x);
	return x;
}
int main(){
	int n,k;
	while(~getII(n,k)){
		int h[n],dp[n];
		F(i,0,n) getI(h[i]);
		dp[0]=0;
		F(i,1,n){
			int minV=INF;
			for(int j=1;j<=k&&i-j>=0;j++){
				int poss=dp[i-j]+mabs(h[i]-h[i-j]);
				if(poss<minV) minV=poss;
			}
			dp[i]=minV;
		}
		printf("%d\n",dp[n-1]);
	}
}


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

using namespace std;

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string s; cin >> s;

    int start = s.size(),finish = 0;

    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'A')start = min(i,start);
        if(s[i] == 'Z')finish = max(i,finish);
    }

    cout << finish-start + 1 << '\n';

    return 0;
}

Measured memory_bytes: 720
#include <iostream>
#include <limits.h>
#include <queue>
#define MAX_V 1000
#define MAX_E 2000
#define INF INT_MAX
using namespace std;

class Edge{
public:
  int from,to,cost;
};
Edge G[MAX_E+1];
int d[MAX_V+1];

int V,E;

int solve(int r){

  fill(d,d+V,INF);
  d[r]=0;
  int cycle=0;
  while(1){
    
    bool update=false;
    
    for(int i=0;i<E;i++){
      Edge e = G[i];
      if(d[e.from]!=INF && d[e.from]+e.cost < d[e.to]){
	d[e.to]=d[e.from]+e.cost;
	update = true;
      }
    }
    if(!update) break;
    cycle++;
    if(cycle>=V) return -1;
  }
 
  return 1;
}


int main(){

  int r;
  cin>>V>>E>>r;
  
  for(int i=0;i<E;i++){
    int from,to,cost;
    cin>>from>>to>>cost;
    G[i].from=from;
    G[i].to=to;
    G[i].cost=cost;
  }
  int ret = solve(r);
  if(ret==-1) cout<<"NEGATIVE CYCLE"<<endl;
  else
    for(int i=0;i<V;i++){
      if(d[i]==INF) cout<<"INF"<<endl;
      else cout<<d[i]<<endl;
    }
  return 0;
}

Measured memory_bytes: 3124
#include <stdio.h>

int main () {
  int n;
  scanf ("%d",&n);
  long long int x[10000];
  int i;
  long long int max,min,t;
  t = 0;
  for (i=0;i<n;i++) {
    scanf ("%lld",&x[i]);
    if (i==0) {
      max = x[0];
      min = x[0];
    }
    if (max <  x[i]) {
      max = x[i];
    }
    if (min > x[i]) {
      min = x[i];
    }
    t += x[i];
  }
  printf ("%lld %lld %lld\n",min,max,t);
  return 0;
}

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

using namespace std;
#define _for(i,j,N) for(int i = (j); i < (N);i++)
#define _rep(i,j,N) for(int i = (j); i <= (N);i++)
#define ALL(x) x.begin(),x.end()
#define LL long long

int get_int(){int x;scanf("%d",&x);return x;}
LL get_long(){LL x;scanf("%lld",&x);return x;}

int l,r;
int N;
string signs;

int main()
{
    scanf("%d",&N);
    int l = 0,r = N-1;
    printf("%d\n",l);
    fflush(stdout);
    string s;
    cin >> s;
    signs = s;
    if(s == "Vacant") return 0;

    printf("%d\n",r);
    fflush(stdout);
    cin >> s;
    if(s == "Vacant") return 0;

    while(true){
        int m = (l + r)/2;
        if(r - l == 2){
            printf("%d\n",m);
            fflush(stdout);
            cin >> s;
            if(s == "Vacant") return 0;
        }
        else if(m&1){
            m -= 1;
        }
        printf("%d\n",m);
        fflush(stdout);
        cin >> s;
        if(s == "Vacant") return 0;
        if(s == signs) l = m;
        else r = m;
    }


    return 0;
}


Measured memory_bytes: 852
#include<bits/stdc++.h>
using namespace std;
int f,n,a;
int main ()
{
cin>>n>>a;
int g[n];
for(int i=0;i<n;i++)
cin>>g[i];
for(int i=0;i<n;i++)
  if(g[i]>=a)f++;
cout<<f;
return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <float.h>
#include <limits>
#include <vector> 
#include <string.h>
#include <iomanip>

#define rep(i,a,n) for(ll int (i) = (a);(i) < (n);(i)++)
#define urep(i,a,n) for(ll int (i) = (a);(i) > (n);(i)--)
#define MOD 1000000007
#define INF 2147483647
#define ll long long
#define asort(a) sort(a.begin(),a.end());
#define usort(a) sort(a.rbegin(),a.rend());

using namespace::std;

ll int jo(ll int a, ll int b){//累乗
    ll int num=1;
    rep(i,0,b) num=num*a;
    return num;
}
char tobig(char s){//char大文字化
  return (s-0x20);
}
char tolow(char s){//char小文字化
  return (s+0x20);
}
int ctoi(char a){//char->int
  if('0'<=a&&a<='9') return (a-'0');
  return -1;
}
 
ll int gcd(ll int a,ll int b) {//最大公約数
  if(a<b) return gcd(b,a);
  int c;
  while ((c=a%b)) {
    a=b;
    b=c;
  }
  return b;
}
ll int lcm(ll int a,ll int b){//最小公倍数
 return (a*b)/gcd(a,b);
}
ll int NotMinus(ll int a){
  if(a>0) return a;
  else return 0;
}


int main(){
  int A; cin>>A;
  while(1){
  int check=0;
  rep(i,2,A){
    if(A%i==0){
      check=1;
      break;
    }
  }
  if(check==0) break;
    A++;
  }
  cout<<A;
}
// int *p = new int[N];

//  sort(変数名.begin(),変数名.end());//昇順ソート
//  sort(変数名.rbegin(),変数名.rend());//降順ソート

// vector<vector<int>> 変数名(左の個数, vector<int>(右の個数));

//cout<<fixed<<setprecision(n);  //小数点n桁まで表示

//  vector<pair<int,int>> data(N);  //2つのデータを格納、.first/.secondで参照
// pairのソートはfirst優先の昇順

//cout.fill('0');
//cout<<setw(N)<<value;  //整数の左側を0梅して指定桁数出力

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(ll i=0; i<n; i++)
#define repr(i, s, e) for(ll i=s; i>=e; i--)
#define reps(i, s, e) for(ll i=s; i<=e; i++)
#define inf 1e18
#define all(v) v.begin(),v.end()
#define ceil(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
template<typename T> inline bool chmax(T &a, T b){ if(a<b) a=b; return a<b; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a) a=b; return b<a; }
template<typename T> void vdeb(T v){
    cout << "#vector set debug" << endl;
    for(auto vv : v) cout << vv << " ";
    cout << endl;
}
template<typename T1, typename T2> void adeb(T1 arr[], T2 n){
    cout << "#adebug" << endl;
    for(int i=0; i<=n; i++) cout << arr[i] << " ";
    cout << endl;
}
template<typename T1> void mdeb(T1 mp){
    cout << "#map pair debug" << endl;
    for(auto const& m : mp) cout << m.first sp m.second << endl;
}
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){ fill((T*)array, (T*)(array+N), val); }
void ans(bool b){ cout << (b ? "Yes" : "No") << endl; }
void ans2(bool b){ cout << (b ? "YES" : "NO") << endl; }
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};


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

    int n;
    ll a;
    cin >> n;
    bool second = true;
    rep(i, n){
        cin >> a;
        if(a % 2 == 1) second = false;
    }

    if(second) cout << "second" << endl;
    else cout << "first" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int  compr(string a,string b){
  for(int i = 0; min(a.size(),b.size()) > i; i++){
    if(a[i] < b[i]){
      return 1;
    }else if(a[i] > b[i]){
      return 0;
    }
  }
  if(a.size() < b.size()){
    return 1;
  }else if(a.size() > b.size()){
    return 0;
  }else{
    return -1;
  }
}
int main(){
  int n;cin>>n;
  int t = 0;
  int h = 0;
  for(int i = 0; n > i; i++){
    string a,b;cin>>a>>b;
    int k = compr(a,b);
    if(k == 1){
      t += 3;
    }else if(k == 0){
      h += 3;
    }else{
      t+=1;
      h+=1;
    }
  }
  cout << h << " " << t << endl;
}


Measured memory_bytes: 3160
#include <iostream>  
#include <cstdio>  
#include <fstream>  
#include <algorithm>  
#include <cmath>  
#include <deque>  
#include <vector>  
#include <queue>  
#include <string.h>  
#include <cstring>  
#include <map>  
#include <stack>  
#include <set> 
#include <iterator> 
#include <list>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
//#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define ll long long
typedef vector <ll> vi;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,m,i,j,k,a,b,d,x,c=0,u=0,ans=0;
	string s;
	cin>>n>>a>>b>>c>>d;
	cin>>s;
	a--;
	b--;
	c--;
	d--;
	for(i=a+1;i<c-1;i++){
	    if(s[i]=='#' && s[i+1]=='#'){
	        cout<<"No";
	        return 0;
	    }
	}
	for(i=b+1;i<d-1;i++){
	    if(s[i]=='#' && s[i+1]=='#'){
	        cout<<"No";
	        return 0;
	    }
	}
	if(c<d){
	    cout<<"Yes";
	   return 0;
	} 
	else{
	    for(i=b-1;i<d;i++){
	        if(s[i]=='.' && s[i+1]=='.' && s[i+2]=='.'){
	            cout<<"Yes";
	            return 0;
	        }
	    }
	}
	cout<<"No";
	return 0;
}



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

using namespace std;

int main()
{
	int n, mn = 23232323, ans = 0;
	cin >> n;
	int a[n];
	for (int i = 1; i <= n;  i ++)
		cin >> a[i];
	for (int i = 1; i <= n; i ++)
	{
		if (mn >= a[i])
		{
			ans ++;
			mn = a[i];
		}
	}
	cout << ans;

}

Measured memory_bytes: 1024
object Main {
  def main(args: Array[String]): Unit = {
    val s = new Main()
    s.solve()
    s.out.flush()
  }
}

class Main {
  import java.io._
  import java.util.StringTokenizer

  import scala.collection.mutable
  import scala.util.Sorting
  import math.{abs, max, min}
  import mutable.{ArrayBuffer, ListBuffer}
  import scala.reflect.ClassTag

  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def solve(): Unit = {
    val N = ni()
    val A = na(N)
    val S = sumL(A)
    val unit = N.toLong * (N + 1) / 2

    val ok = if (S % unit != 0) {
      false
    } else {
      val diff = Array.ofDim[Int](N)
      rep(N) { i =>
        diff(i) = A(i) - A((N + i - 1) % N)
      }
      val cnt = S / unit
      var applys = 0L
      val ok = 0 until N forall { i =>
        val d = diff(i) - cnt
        if (diff(i) <= cnt && d % N == 0) {
          applys += d / -N
          true
        } else {
          false
        }
      }
      ok && applys == cnt
    }

    val ans = if (ok) "YES" else "NO"
    out.println(ans)
  }


  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = _

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  val sc = new InputReader(System.in)
  def ni(): Int = sc.nextInt()
  def nl(): Long = sc.nextLong()
  def nc(): Char = sc.nextChar()
  def ns(): String = sc.next()
  def ns(n: Int): Array[Char] = ns().toCharArray
  def na(n: Int): Array[Int] = map(n)(_ => ni())
  def nal(n: Int): Array[Long] = map(n)(_ => nl())
  def nm(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
  def rep(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = offset
    val N = n + offset
    while(i < N) { f(i); i += 1 }
  }
  def rep_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = n - 1 + offset
    while(i >= offset) { f(i); i -= 1 }
  }

  def map[@specialized A: ClassTag](n: Int)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    rep(n)(i => res(i) = f(i))
    res
  }

  def sumL(as: Array[Int]): Long = {
    var s = 0L
    rep(as.length)(i => s += as(i))
    s
  }
}


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

#define llint long long int
#define pb push_back

using namespace std;

int main(){
  int n, m, c;
  cin >> n >> m >> c;
  int b[m];
  for(int i = 0 ; i < m; i++)cin >> b[i];
  int ans = 0;
  while(n--){
    int a;
    int sum = 0;
    for(int i = 0; i < m; i++){
      cin >> a;
      sum += a*b[i];
    }
    sum += c;
    if(sum > 0)
      ans++;
  }
  cout << ans;
  return 0;
}

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

int main(void)
{
  int N;
  scanf("%d", &N);
  map<string, int> S;
  string s;
  int maxv = 0;
  for (int i = 0; i < N; i++)
  {
    cin >> s;
    S[s]++;
    maxv = max(maxv, S[s]);
  }

  vector<string> result;
  for (auto i = S.begin(); i != S.end(); i++)
  {
    if (i->second == maxv)
    {
      result.push_back(i->first);
    }
  }

  sort(result.begin(), result.end());

  for (int i = 0; i < result.size(); i++)
  {
    cout << result[i] << endl;
  }
}

Measured memory_bytes: 26868
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
using namespace std;

typedef long long ll;

int n;
int a;
map <int, int> M;
ll res;

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a); M[a]++;
	}
	res = 1;
	for (int i = 0; i < 2; i++) {
		map <int, int>::reverse_iterator it = M.rbegin();
		for (; it != M.rend(); it++)
			if (it->second >= 2) { res *= it->first; it->second -= 2; break; }
		if (it == M.rend()) { printf("0\n"); return 0; }
	}
	cout << res << endl;
	return 0;
}

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

long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % 1000000007;
        a = a * a % 1000000007;
        n >>= 1;
    }
    return res;
}
int main()
{
    int p,check=0;
    long long n;
    int chk[100000];
    cin >> n;
    for(int i=0;i<100000;i++) chk[i]=0;

    for(int i=0;i<n;i++){
        cin >> p;
        chk[p]++;
    }

    if(n%2){
        if(chk[0]!=1)check=1;
        for(int i=1;i<100000;i++){
            if(i%2){
                if(chk[i]!=0)check=1;
            }else if(i>=n){
                if(chk[i]!=0)check=1;
            }else{
                if(chk[i]!=2)check=1;
            }
        }
    }else{
        if(chk[0]!=0)check=1;
        for(int i=1;i<100000;i++){
            if((i%2)==0){
                if(chk[i]!=0)check=1;
            }else if(i>=n){
                if(chk[i]!=0)check=1;
            }else{
                if(chk[i]!=2)check=1;
            }
        }
    }

    if(check){
        cout << 0 << endl;
    }else{
        if(n%2){
            cout << modpow(2,(n-1)/2) << endl;
        }else{
            cout << modpow(2,n/2) << endl;
        }
    }

    return 0;
}


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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
 
//Write From this Line

//const ll mod = 1e9+7;
//const ll mod = 998244353;

const int dy[] = {0,0,1,-1};
const int dx[] = {1,-1,0,0};
const int inf = 1e9;
int main()
{
	int h, w;
	cin >> h >> w;

	int sh, sw;
	cin >> sh >> sw;
	int gh, gw;
	cin >> gh >> gw;
	sh--, sw--, gh--, gw--;

	vector<string> field(h);
	rep(i,h) cin >> field[i];

	vector<vector<bool>> seen(h, vector<bool> (w,false));
	vector<vector<int>> dist(h,vector<int>(w,inf));

	queue<P> q;
	queue<P> nq;
	q.push({sh,sw});
	nq.push({sh,sw});
	dist[sh][sw] = 0;
	seen[sh][sw] = true; // コストが確定したらtrue
	while(1){
		bool u = true;
		while(!q.empty()){
			u = false;
			// BFSでコスト0で行けるところをマーキングする
			int y = q.front().first; 
			int x = q.front().second;
			nq.push({y,x});
			q.pop();
			rep(i,4){
				int ny = y + dy[i];
				int nx = x + dx[i];
				if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
				if(seen[ny][nx]) continue;
				if(field[ny][nx] == '#') continue;

				q.push({ny,nx});
				seen[ny][nx] = true;
				dist[ny][nx] = dist[y][x];
			}
		} 
		while(!nq.empty()) {
			u = false;
			// コスト0で行けるところはマーキング済み。
			// nq からワープを使って行けるとこを登録していく
			int y = nq.front().first; 
			int x = nq.front().second;
			nq.pop();

			for(int i = -2; i <= 2; i++){
				for(int j = -2; j <= 2; j++){
					int ny = y + i;
					int nx = x + j;
					if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
					if(seen[ny][nx]) continue;
					if(field[ny][nx] == '#') continue;

					dist[ny][nx] = dist[y][x] + 1;
					seen[ny][nx] = true;
					q.push({ny,nx});
				}
			}
		}
		if(u) break;
	}
	int ans = dist[gh][gw];
	if(ans == inf) ans = -1;
	cout << ans << endl;

	//rep(i,h){
	//	rep(j,w){
	//		cout << dist[i][j] << " ";
	//	}
	//	cout << endl;
	//}
}


Measured memory_bytes: 9692
#pragma region header
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr int inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
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;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */
#pragma endregion
int main() {
    /*int n;string s;cin >> n >> s;
    int white = 0;
    int black = 0;
    int count = 0;
    rep(i, n) {
        if(s[i]=='.') white++;
        else black++;
    }*/
    /*rev(i, n) {
        if(s[i]=='.') {
            // white++;
            if(s[i-1]=='#') {
                count++;
                s[i-1]='.';
            }
        }
    }
    cout << min(white,count) << endl;*/
    int n;string s;cin >> n >> s;
    vi black(n+1),white(n+1);
    rep(i, n) {
        if(s[i]=='#') black[i+1]++;
        // else white[n-i]++;
        black[i+1]+=black[i];
        // white[n-i-1]+=white[n-i];
    }
    rev(i, n) {
        if(s[i]=='.') white[i]++;
        white[i]+=white[i+1];
    }

    int mi = inf;
    /*for(auto p:black)cout << p << ' ';
    cout << endl;
    for(auto p:white)cout << p << ' ';
    cout << endl;*/
    rep(i, n+1) {
        chmin(mi,black[i]+white[i]);
    }
    cout << mi << endl;
    return 0;
}

Measured memory_bytes: 5216
#include <iostream>
#include <cstdio>
using namespace std;
int main(void){
  int n;
  int a;

  while(cin>>n,n!=0){
    int count[7]={0};
    for(int i=0;i<n;i++){
      cin>>a;
      if(a>60)a=60;
      count[(int)a/10]++;
    }
    for(int i=0;i<7;i++){
      printf("%d\n",count[i]);
    }
  }
  return 0;
}

Measured memory_bytes: 1144
import math

a,b = map(int,input().split())

a_1 = math.ceil(a/0.08)
a_2 = math.ceil((a+1)/0.08)
b_1 = b * 10
b_2 = (b+1) * 10

if a_1 >=b_2 or b_1 >= a_2:
    print(-1)
else:
    print(max(a_1,b_1))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int d[100010]; //始点からの距離を保持する配列
const int INF = 1001001001;
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}return false;}

int main(){
    int n, m, r; cin >> n >> m >> r;
    vector<vector<P>> G(n);
    fill(d, d + n, INF); //0からn-1までINFにする
    d[r] = 0; //始点は0にして初期化完了
    for(int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c;
        G.at(a).push_back({c, b}); //priority_queの時にコストが小さい順位取り出されるように(c, b)というpairを作る
    }
    priority_queue<P, vector<P>, greater<P>> que; 
    que.push({0, r}); //始点を入れる
    while(!que.empty()){
        P v = que.top(); que.pop();
        for(auto nv: G.at(v.second)){ //取り出した点から行ける全ての頂点について
            int dist = nv.first, next = nv.second;
            if(chmin(d[next], d[v.second] + dist)) que.push({d[next], next}); //もし最短距離が更新されたらqueに入れる
        }
    }
    for(int i = 0; i < n; i++){
        if(d[i] == INF) cout << "INF" << endl;
        else cout << d[i] << endl;
    }
}


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

const int MAX_V=110;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    int n,w;
    while(cin >> n >> w,n){
        vector<int> cnt(MAX_V,0);
        for (;n--;){
            int v; cin >> v;
            ++cnt[v/w];
        }
        int wid,M=0;
        for (int i=0;i<MAX_V;++i){
            if (cnt[i]) wid=i;
            M=max(M,cnt[i]);
        }
        double ans=0.01,now=1;
        for (int i=0;i<=wid;++i){
            ans+=(double)now*cnt[i]/(double)M;
            now-=1.0/(double)wid;
        }
        cout << ans << '\n';
    }
}


Measured memory_bytes: 3140
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int r;
    while(cin>>r)
    {
        if(r<1200)
            cout<<"ABC\n";
        else if(r<2800)
            cout<<"ARC\n";
        else
            cout<<"AGC\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#define rep(i,n) for(int i = 0; i < n; i++)
#define INF 1000000000
#define MOD 1000000007
#define ll long long
using namespace std;
int n;
ll sum,ans;
ll a[100000];
ll sa[100000];
int main(){
    cin>>n;
    rep(i,n){cin>>a[i]; sum+=a[i];}
    ll set=n*(n+1)/2;
    ll kai=sum/set;
    rep(i,n){
        sa[i]=kai-a[(i+1)%n]+a[i];
        ans+=(sa[i]/n)*(n-i);
    }
    if (ans==a[0]){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<string.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define see(x) cout<<#x<<" : "<<(x)<<endl;
#define ya cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define ff first
#define sc second
typedef long long ll;
using namespace std;
 
const ll N=100009;
ll n,u,vv,w;
vector<ll>v[N],ww[N];
bool vis[N];
ll ans[N];
void dfs(ll i)
{
    vis[i]=1;
    for(ll j=0;j<v[i].size();j++)
    {
        u=v[i][j];
        w=ww[i][j];
        if(!vis[u])
        {
            if(w&1)
            {
                ans[u]=!ans[i];
            }
            else
            {
                ans[u]=ans[i];
            }
            dfs(u);
        }
    }
}
int main()
{
    ll i,j;
    cin >>n;
    for(i=1;i<n;i++)
    {
        cin >> u >> vv >> w;
        v[u].pb(vv);
        v[vv].pb(u);
        ww[u].pb(w);
        ww[vv].pb(w);
    }
    dfs(1);
    for(i=1;i<=n;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 17864
#include <iostream>
#include <vector>

using ll = long long;
int main(int argc, char ** argv)
{
  //
  int n;
  std::cin >> n;
  std::vector<ll> a(n);
  ll ans = 0;
  std::cin >> a[0];
  ll min = a[0];

  for (int i = 1; i < n; ++i) {
    std::cin >> a[i];
    if (min > a[i]) {
      ans += min - a[i];
    }
    min = std::max(min, a[i]);
  }

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


Measured memory_bytes: 4804
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    ll n,ans=0; cin>>n;
    vector<ll> a(n+1,0),b(n,0);
    rep(i,n+1) cin>>a[i];
    rep(i,n) cin>>b[i];
    rep(i,n){
        if(a[i]>b[i]){
            a[i]-=b[i];
            ans+=b[i];
        }
        else{
            ans+=a[i];
            b[i]-=a[i];
            a[i]=0;
            if(a[i+1]>b[i]){
                ans+=b[i];
                a[i+1]-=b[i];
            }
            else{
                ans+=a[i+1];
                a[i+1]=0;
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	static ll N;
	static ll a[10010],b[10010];
	scanf("%lld",&N);
	for(int i = 1 ; i <= N ; i ++){
		scanf("%lld",&a[i]);
	}
	for(int i = 1 ; i <= N ; i ++){
		scanf("%lld",&b[i]);
	}
	
	static ll cnt = 0;
	for(int i = 1 ; i <= N ; i ++){
		cnt += b[i];
		cnt -= a[i];
	}
	static ll cnt_a = 0, cnt_b = 0;
	for(int i = 1 ; i <= N ; i ++){
		if((a[i]+b[i])&1){
			cnt_b ++;
			b[i] ++;
		}
		if(a[i] > b[i]){
			cnt_b += a[i]-b[i];
		}
		if(a[i] < b[i]){
			cnt_a += (b[i]-a[i])/2;
		}
	}
	
	if(cnt < cnt_a || cnt < cnt_b){
		puts("No");
	}
	else puts("Yes");
}



Measured memory_bytes: 384
import sys


input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    alist = [set([]) for _ in range(N+1)]
    for _ in range(M):
        X, Y, _ = map(int, input().split())
        alist[X].add(Y)
        alist[Y].add(X)

    f = [0]*(N+1)
    f[0] = 1
    stack = []
    ans = 0
    for i in range(1, N+1):
        if len(alist[i]) and not f[i]:
            stack.append(i)
            ans += 1
        elif not len(alist[i]):
            ans += 1
        while len(stack):
            n = stack.pop()
            f[n] = 1
            for m in alist[n]:
                if not f[m]:
                    stack.append(m)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 77488
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    print(input().replace("?","D"))
if __name__ == "__main__":
    main() #endline===============================================

Measured memory_bytes: 10020
package main

import (
	"fmt"
)

/*
1 ▢ keyence
2 k ▢ eyence
3 ke ▢ yence
4 key ▢ ence
5 keye ▢ nce
6 keyen ▢ ce
7 keyenc ▢ e
8 keyence ▢
*/
func main() {
	var s string
	fmt.Scan(&s)

	k := "keyence"
	for i := 0; i < 8; i++ {
		prefix := k[0:i]
		suffix := k[i:]
		j := len(s) - len(suffix)
		if prefix == s[:i] && suffix == s[j:] {
			fmt.Println("YES")
			return
		}
	}
	fmt.Println("NO")
}


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using P = pair<ll, ll>;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}
struct edge {
  ll to, cost;
};

vector<int> L; 

int main() {
  int N; cin >> N;
  L.resize(N); REP(i, N) cin >> L[i];
  sort(all(L)); // にぶたん？
  ll ans = 0;
  REP(i, N) {
    for(int k = i + 1; k < N; ++k) {
      int right = lower_bound(L.begin(), L.end(), L[i] + L[k]) - L.begin();
      ans += max(right - (k + 1), 0);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>G[N];
int n,dp[N],f=-1;
void dfs(int i,int p)
{
    int F=0;
    for(auto j:G[i])
    {
        if(j==p)continue;
        dfs(j,i);
        dp[i]+=dp[j];
        if(!dp[j])
        {
            if(!F)F=1;
            else dp[i]++;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1,u,v; i<n; i++)
        scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    for(int i=0; i<n; i++)
        if(G[i].size()>2)
        {
            f=i;
            break;
        }
    if(f==-1)printf("1\n");
    else dfs(f,-1),printf("%d\n",dp[f]);
    return 0;
}


Measured memory_bytes: 10368
from collections import deque
n = int(input())
A = list(map(int, input().split()))
B = deque()

for i in range(n):
    if i % 2 == 0:
        B.append(A[i])
    else:
        B.appendleft(A[i])

if n % 2 == 0:
    print(*B)
else:
    B = list(B)
    print(*(B[::-1]))

Measured memory_bytes: 25536
N = gets.to_i
p = gets.split.map(&:to_i)

ans = 0
f = false
p.each.with_index(1) do |n,i|
  if n == i && !f
    ans += 1
    f = true
  elsif n == i && f
    f = false
  else
    f = false
  end
end
p ans


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

int main() {
  int N,total=0;
  cin >> N;
  
  int AA;
  cin >> AA;
  
  while (AA%2 == 0) {
    AA /= 2;
    total++;
  }
  
  
  for (int i=0; i<(N-1); i++) {
    int A, sum=0;
    cin >> A;
    
    while (A%2 == 0) {
      A /= 2;
      sum++;
    }
    
    if (total >= sum) {
      total =sum;
    }
  }
  
  cout << total << endl;
  
}  

Measured memory_bytes: 3596
#include <bits/stdc++.h>  // ver1.9.5
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define Pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define Vout(a) rep(i,0,a.size()-1)cout<<a[i]<<' ';cout<<a[a.size()-1]<<endl
#define INF 9000000000000000000  //  9.0 * 10^18
#define MOD 1000000007  //  10^9 + 7
using namespace std;

signed main() {
  cout << fixed << setprecision(8);
  int n,k;
  cin >> n >> k;
  int memo;
  Vi a(n);
  rep(i,0,n){
    cin >> memo;
    memo -= k;
    a[i] = memo;
  }
  sort(ALL(a));
  
  map<int,int> ans,now;
  ans[2500]++;
  now[2500]++;
  
  rep(i,0,n){
    for (auto p : now) {
      auto k = p.first;
      auto v = p.second;
      ans[k+a[i]] += now[k];
      //cout << k << endl;
    }
    now = ans;
  }
  
  /*for (auto p : ans ) {
    auto k = p.first;
    auto v = p.second;
    cout << k-2500 << " " << v << endl;
  }*/
  
  cout << ans[2500]-1 << endl;
  return 0;
}

Measured memory_bytes: 384
N = int(input())
stations = [ list(map(int, input().split())) for _ in range(N-1)]

time = [0] * N


for i, station in enumerate(stations):
    C, S, F = station
    for j in range(i + 1):
        if S > time[j]:
            time[j] = S + C
        elif time[j] % F == 0:
            time[j] += C
        else:
            time[j] += F - (time[j] % F) + C

[ print(t) for t in time ]


Measured memory_bytes: 3188
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-9;
const int inf=2e9;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
#define M 5000000
ll MOD=1000000007;
// a^b mod MOD
ll powmod(ll a,ll b){
	ll out=1;
	ll p=a%MOD;
	while(b){
		if(b&1)out=out*p%MOD;
		p=p*p%MOD;
		b>>=1;
	}
	return out;
}
vector<ll> fact;
void init(){
	fact=vector<ll>(M);
	fact[0]=fact[1]=1;
	loop(i,2,M)fact[i]=fact[i-1]*i%MOD;
}
// nCr
ll nCr(ll n,ll r){
	ll out=fact[n]*powmod(fact[r]*fact[n-r]%MOD,MOD-2)%MOD;
	return out;
}	
ll n,m,dp[2010][2010];
ll f(){
	dp[0][0]=1;
	rep(i,n+1)loop(j,i,n+1){
		if(i)dp[i][j]=dp[i-1][j];
		if(j!=i)(dp[i][j]+=nCr(i-1+j*(m-1),m-2)*dp[i][j-1]%MOD)%=MOD;
	}
//	rep(i,4){rep(j,4)cout<<" "<<dp[i][j];cout<<endl;}
	return dp[n][n];
}
int main(){
	init();
	cin>>n>>m;
	cout<<(m-1?fact[n]*f()%MOD:1)<<endl;
}












Measured memory_bytes: 61952
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <limits.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
using namespace std;

int main(){
  int N, ans = 0 ;
  long long int D ;
  cin >> N >> D ;
  long long int A, B ;
  D *= D ;
  for(int i=0;i<N;i++){
    cin >> A >> B ;
    A *= A ;
    B *= B ;
    if(D >= (A + B) ) ans++ ;
  }
  cout << ans << endl ;
  return 0 ;
}  

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

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }


int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    ios::sync_with_stdio(false);
    string s;
    while (cin >> s) {
        char cnt[128] = {0};
        FOR_ALL(c,s)
            cnt[*c]++;
        bool good = true;
        FOR(c,0,128) if (cnt[c])
            good &= cnt[c] == 2;
        const string ans = good ? "Yes" : "No";
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define MAXN (200000 + 5)
#define MAXL (32 + 5)
using namespace std;
LL n, a[MAXN], b[MAXN], ak[MAXL][MAXN], bk[MAXL][MAXN], k = 30, ans[MAXL];
int main()
{
	//	freopen("in.in", "r", stdin);
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		for (int j = 1; j <= k; j++)
			ak[j][i] = a[i] & ((1 << j) - 1);
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &b[i]);
		for (int j = 1; j <= k; j++)
			bk[j][i] = b[i] & ((1 << j) - 1);
	}
	for (int i = 1; i <= k; i++)
		sort(bk[i] + 1, bk[i] + n + 1), sort(ak[i] + 1, ak[i] + n + 1);
	/*for (int i = 1; i <= k; i++)
	{
		for (int j = 1; j <= n; j++)
			printf("%d ", ak[i][j]);
		puts("");
	}
	for (int i = 1; i <= k; i++)
	{
		for (int j = 1; j <= n; j++)
			printf("%d ", bk[i][j]);
		puts("");
	}*/
	for (int i = 1; i <= n; i++) // ai + bj >= (1 << (k - 1)) && ai + bj < (1 << (k))
	{
		for (int j = 1; j <= k; j++)
		{
			int to = upper_bound(bk[j] + 1, bk[j] + n + 1, (1 << j) - ak[j][i] - 1) - bk[j];
			int to1 = upper_bound(bk[j] + 1, bk[j] + n + 1, (1 << (j + 1)) - 1 - ak[j][i]) - bk[j];
			int from = lower_bound(bk[j] + 1, bk[j] + n + 1, (1 <<(j - 1)) - ak[j][i]) - bk[j];
			int from1 = lower_bound(bk[j] + 1, bk[j] + n + 1, (1 << j) + (1 << (j - 1)) - ak[j][i]) - bk[j];
			ans[j] += to - from + to1 - from1;
		}
	}
	LL outp = 0;
	for (int i = 1; i <= k; i++)
		outp += (ans[i] & 1) << (i - 1);
	printf("%lld", outp);
	return 0;
}

/*
2
1 2
3 4
*/

Measured memory_bytes: 101120
n,m=map(int,input().split())
master,sub=[],[]
for i in range(n):
    master.append(input())
for j in range(m):
    sub.append(input())
def chk(a,b,y,x):
    t=len(b)
    for i in range(t):
        if a[y+i][x:x+t]!=b[i]:
            return 0
    return 1

for i in range(n-m+1):
    for j in range(n-m+1):
        if master[i][j:j+m]==sub[0]:
            if chk(master,sub,i,j):
                print('Yes')
                exit()
print('No')

Measured memory_bytes: 38384
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <tuple>
#include <cmath>
using namespace std;


int main()
{
	int n;
	cin >> n;
	using param = tuple<int, int, int>;
	auto data = vector<param>(n);
	for(auto i = 0; i < n; ++i){
		int x, y, h;
		cin >> x >> y >> h;
		data[i] = tie(h, x, y);
	}
	sort(data.begin(), data.end(), greater<param>());
	bool ans = false;
	for(auto y = 0; y <= 100; ++y){
		for(auto x = 0; x <= 100; ++x){
			int c, a, b;
			tie(c, a, b) = data[0];
			int h = c + abs(x - a) + abs(y - b);
			bool fit = true;
			for(auto i = 1; i < n; ++i){
				tie(c, a, b) = data[i];
				if(max(h - abs(x - a) - abs(y - b), 0) != c){
					fit = false;
					break;
				}
			}
			if(fit){
				ans = true;
				cout << x << " " << y << " " << h << endl;
			}
			if(ans) break;
		}
		if(ans) break;
	}
	return 0;
}

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

const int inf = 2000000000;

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

    int ans = inf;
    for (int i = 0; i < S.length() - 2; i++) {
        int tmp = (S[i] - '0') * 100 + (S[i+1] - '0') * 10 + (S[i+2] - '0');
        if (ans > abs(tmp - 753)) ans = abs(tmp - 753);
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//解説動画写し
vector<int>to[100005];
int main(){
  int n,m;
  cin>>n>>m;
  rep(i,m){
    int a,b;
    cin>>a>>b;
    --a;--b;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  queue<int>q;
  vector<int>dist(n,INT_MAX);
  vector<int>pre(n,-1);
  dist[0]=0;
  q.push(0);
  while(!q.empty()){
    int v=q.front();q.pop();
    for(int u:to[v]){
      if(dist[u]!=INT_MAX)continue;
      dist[u]=dist[v]+1;
      pre[u]=v;
      q.push(u);
    }
  }
  cout<<"Yes"<<endl;
  rep(i,n){
    if(i==0)continue;
    int ans=pre[i];
    ++ans;
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 10652
import statistics

N = int(input())
p = [list(map(int,input().split())) for i in range(N)]

p.sort()
delta = []
for i in range(N):
    for j in range(i+1,N):
        dx = p[j][0]-p[i][0]
        dy = p[j][1]-p[i][1]
        delta.append([dx,dy])
delta.sort()
best = [0,0]
bestc = 0
nowc = 0
for i in range(len(delta)):
    if i == 0:
        best = delta[i]
        bestc = 1
        nowc = 1
    else:
        if delta[i-1][0]==delta[i][0] and delta[i-1][1]==delta[i][1]:
            nowc += 1
            if nowc > bestc:
                best = delta[i]
                bestc = nowc
        else:
            nowc = 1
ans = 1+(N-1-bestc)
print(ans)




Measured memory_bytes: 5148