akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;

const int N = 1e5 + 10;
int n, ans, a[N]; map<int, int> pos;

template <class T> inline void in(T &x) {
	x = 0; int f = 1; char ch = getchar();
	for (; ch<'0' || ch>'9';) {if (ch=='0') f=-1; ch = getchar();}
	for (; ch>='0' && ch<='9';) x = x*10 + ch-'0', ch = getchar();
	x *= f;
}

int main() {
	in(n);
	for (int i = 1; i <= n; ++i) in(a[i]), pos[a[i]] = i;
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i)
		ans += (pos[a[i]] - i) & 1;
	printf("%d\n", ans >> 1);
	return 0;
}

Measured memory_bytes: 5376
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9 + 7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A, B, C, D, E, F, G, H, I, J, K, L, N, M, O, P, Q, R, S, T, U, V, W, x, y, z;
long long max_value = INF, max_index = -1;
long long min_value = MAX, min_index = -1;
typedef long long ll;
typedef pair<ll, ll> Pa;

vector<Pa> to[100001];
ll range[100001];
int main() {
	cin >> N;
	rep(i, N-1){
		cin >> A >> B >> C;
		to[A].push_back(Pa(B, C));
		to[B].push_back(Pa(A, C));
	}
	rep(i, N){
		range[i+1] = MAX;
	}
	range[1] = 0;
	queue<int> que;
	que.push(1);
	while(!que.empty()){
		int curr = que.front(); que.pop();
		rep(i, to[curr].size()){
			if(range[to[curr][i].first] == MAX){
				range[to[curr][i].first] = range[curr] + to[curr][i].second;
				que.push(to[curr][i].first);
			}
		}
	}
	rep(i, N){
		cout << range[i+1]%2 << endl;
	}
}

Measured memory_bytes: 8704
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD (1000000007)
#define PI acos(-1)
#define eps (1e-8)
#define INF (1e18)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
//ifstream cinn("input.txt");ofstream coutt("output.txt");


signed main(){
    FASTER;
    int n,m;cin>>n>>m;
    if(m==n){
        cout<<"Yes";
    }else cout<<"No";
}

Measured memory_bytes: 256
using System;

class Program {
    static void Main(string[] args) {

        string wea = Console.ReadLine();
        string result = "";

        switch (wea) {
            case "Sunny":
                result = "Cloudy";
                break;

            case "Cloudy":
                result = "Rainy";
                break;

            case "Rainy":
                result = "Sunny";
                break;
        }
        Console.WriteLine(result);
    }
}

Measured memory_bytes: 11092
from collections import deque
 
s = deque(input())
q = int(input())
 
direction = 0
for _ in range(q):
    a = input()
    if a[0]=='1':
        direction+=1
    else:
        t,f,c = a.split()
        if f=='1':
            if direction%2==0:
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if direction%2==0:
                s.append(c)
            else:
                s.appendleft(c)
 
if direction%2==1:
    s.reverse()
print(''.join(s))

Measured memory_bytes: 73944
if __name__ == '__main__':
    N, M = map(int, input().split())
    H = list(map(int, input().split()))

    is_good = [True for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if H[a] > H[b]:
            is_good[b] = False
        elif H[a] < H[b]:
            is_good[a] = False
        elif H[a] == H[b]:
            is_good[a] = False
            is_good[b] = False

    print(is_good.count(True))

Measured memory_bytes: 20124
# UnionFind
class UnionFind():

    #0~Nまでの頂点数で初期化していることに注意
    def __init__(self, n):
        self.n = n
        self.root = [-1] * n

    def FindRoot(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.FindRoot(self.root[x])
            return self.root[x]

    def Unite(self, x, y):
        x = self.FindRoot(x)
        y = self.FindRoot(y)

        if x == y:
            return False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

    def isSameGroup(self, x, y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self, x):
        return -self.root[self.FindRoot(x)]


N, M = map(int, input().split())
p = list(map(int, input().split()))

Uni = UnionFind(N)

# どことどこが繋がっているかでグループ分けする
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1; y -= 1
    # 添字の値そのまま(-1されてるけど)で、連結されているものは同じグループ
    Uni.Unite(x, y)

a = [set() for _ in range(N)]
for i in range(N):
    #　ああ！この添字はこのグループだよ！
    r = Uni.FindRoot(i)
    # 同じグループなところにその添字を突っ込む！
    a[r].add(i)

ans = 0
for i in range(N):
    for j in a[i]:
        if p[j] - 1 in a[i]:
            ans += 1
print(ans)


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

int main(){
  int n,k;
  cin >> n>> k;
  vector<int> price(n);
  rep(i,n){
    cin >> price[i];
  }
  sort(price.begin(),price.end());
  int tot = 0;
  rep(i,k){
    tot += price[i];
  }
  cout << tot <<endl;

  return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

// 一段減らす
vector<int> sub(vector<int> &v) {
    if (v.size() == 1) return v;
    vector<int> v2(v.size() - 1);
    rep(i, v.size() - 1) {
        v2[i] = abs(v[i] - v[i + 1]);
    }
    return v2;
}

// 半分にする
vector<int> tournament(vector<int> &v) {
    vector<int> next;
    for (int i = 0; i < v.size(); i += 2) {
        int a = abs(v[i] - v[i + 1]);
        next.push_back(a);
    }
    return next;
}

// 偶数なら半分にする
// 奇数なら一段減らしてから半分にする
int solv(vector<int> v) {
    while (v.size() != 1) {
        if (v.size() % 2 == 0) {
            v = tournament(v);
        } else {
            v = sub(v);
        }
    }
    return v.front();
}

int main() {
    int n;
    cin >> n;
    vector<char> u(n);
    rep(i, n)cin >> u[i];
    vector<int> v(n);
    rep(i, n) v[i] = u[i] - '0';

    v = sub(v);
    v = sub(v);
    v = sub(v);
    v = sub(v);

    cout << solv(v) << endl;

}


Measured memory_bytes: 15944
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

int main(){
		
	int N;
	cin>>N;
	if(N==1){
		cout<<"Hello World"<<endl;
	}else if(N==2){
		int A,B;
		cin>>A;
		cin>>B;
		cout<<A+B<<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++)
static const int MAX=250;

int Heap[MAX+1];

void printnode(int node,int n){
    printf("node %d: key = %d, ",node,Heap[node]);
    if(node/2!=0){
        printf("parent key = %d, ",Heap[node/2]);
    }
    if(node*2<=n){
    printf("left key = %d, ",Heap[node*2]);
    }
    if(node*2+1<=n){
    printf("right key = %d, ",Heap[node*2+1]);
    }
    printf("\n");
}

int main(){
    int n;cin>>n;
    rep(i,n){scanf("%d",&Heap[i+1]);}
    rep(i,n)printnode(i+1,n);
}


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

using namespace std;

int main()
{
    char c;
    cin>>c;
    if (c=='A')cout<<'T'<<endl;
    else if (c=='T')cout<<'A'<<endl;
    else if (c=='G')cout<<'C'<<endl;
    else if (c=='C')cout<<'G'<<endl;

    return 0;
}


Measured memory_bytes: 256
//#pragma GCC optimize("Ofast",3,"inline")
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define m_p make_pair
#define y1 ygftgfgcdtfgxffgx
#define y2 yfdsesgvtyghftfvv
#define x1 xvyr6cf6fgcfgf676
#define x2 xcr6rfc5r66y6r6fr
#define up_bound upper_bound
#define low_bound lower_bound
#define next_per next_permutation
#define pb push_back
#define i_to_s to_string
typedef priority_queue<int> p_queue;
typedef priority_queue<int, vector<int>, greater<int> > min_p_queue;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int mon[20]={31,28,31,30,31,30,31,31,30,31,30,31};
ll gcd(ll x,ll y){return ((y==0)?x:gcd(y,x%y));}
long long n,ans1,f[100001],a[100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
   	cin>>n;
   	for(int i=1;i<=n;i++)
   		cin>>a[i];
    for(int i=n-1;i>=1;i--){
        if(a[i]>=a[i+1])f[i]=f[i+1]+1;
        ans1=max(ans1,f[i]); 
    }
    cout<<ans1;
}

Measured memory_bytes: 1920
n = input()
le = len(n)

def count(x):
    k = len(x) // 2
    for i in range(k):
        if i==0:
            ans = '9'
        else:
            ans += '09'
    return (int(ans))

if le == 1:
    print(int(n))
    exit()

elif le % 2 == 0:
    ans = count(n)
else:
    nn = n[1:]
    ans = count(nn)
    ans += int(n) - 10**(le-1) + 1
print(ans)

Measured memory_bytes: 3064
import java.util.*;

public class Main {
    static int MOD = 1000000007;
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] broken = new int[m];
        for (int i = 0; i < m; i++) {
            broken[i] = sc.nextInt();
            
            if (i > 0 && broken[i] - broken[i - 1] == 1) {
                System.out.println("0");
                return;
            }
        }
        
        int oldNum = 0;
        long count = 1;
        
        for (int i = 0; i < m; i++) {
            int num = broken[i];
            count = count * fibonacci((num - 1) - oldNum) % MOD;
            oldNum = num + 1;
        }
        
        count = count * fibonacci(n - oldNum) % MOD;
        
        System.out.println(count);
    }
    
    public static long fibonacci(long n) {
        long num1 = 1;
        long num2 = 1;
        long tmp = 1;
        
        for (long i = 1; i < n; i++) {
            tmp = (num1 + num2) % MOD;
            num1 = num2;
            num2 = tmp;
        }
        
        return tmp;
    }
}


Measured memory_bytes: 46516
#include<stdio.h>

int main(){
	int i,a,b,c,cnt=0;
	
	scanf("%d %d %d",&a,&b,&c);
    for(a;a<=b;a++){
        if(c%a==0){
        	cnt++;
        }
	}
	printf("%d\n",cnt);
    return 0;
}

Measured memory_bytes: 596
n = list(input())
n_ = [int(x) for x in n]
num = max(n_)
if n_[0] < num:
  n = [n_[0] + 1 for x in n_]
else:
  n = [num for x in n_]

n = [str(x) for x in n]

print(int(''.join(n)))

Measured memory_bytes: 3060
S = gets.chomp

n = m = 0

1.upto(S.size) do |i|
  if S[i - 1] != ((i % 2) == 0 ? '1' : '0')
    n += 1
  end
  if S[i - 1] != (i % 2).to_s
    m += 1
  end
end

puts [n, m].min

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b,c,d;cin >> a >> b >> c >> d;
	if(a+b<c+d) cout << "Right" << endl;
	else if(a+b==c+d) cout << "Balanced" << endl;
	else cout << "Left" << endl;
}

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

#define int long long
#define INT int
#define MOD 1000000007

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}
typedef long long ll;
const long long INF = 1LL << 60;

signed main()
{

    int n;
    cin >> n;
    int ans = (1000 - n % 1000) % 1000;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int N;
  cin >> N;
  map<string, vector<P>> mp;
  rep(i, N) {
    string S;
    int P;
    cin >> S >> P;
    mp[S].emplace_back(P, i);    
  }
  for (auto p : mp) {
    sort(p.second.rbegin(), p.second.rend());
    for (auto p2 : p.second) {
      cout << p2.second + 1 << '\n';
    }
  }
  return 0;
}

Measured memory_bytes: 3580
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Numerics;

public class Program
{
    public static void Main(string[] args)
    {
        list = new List<int>[4];
        for (int i = 0; i < list.Length; i++)
        {
            list[i] = new List<int>();
        }

        for (int i = 0; i < 3; i++)
        {
            string[] line = Console.ReadLine().Split(' ');
            int a = int.Parse(line[0]) - 1;
            int b = int.Parse(line[1]) - 1;

            list[a].Add(b);
            list[b].Add(a);
        }

        for (int i = 0; i < 4; i++)
        {
            if(move(i, 0))
            {
                Console.WriteLine("YES");
                Console.ReadLine();
                return;
            }
        }


        Console.WriteLine("NO");
        Console.ReadLine();
    }

    static List<int>[] list;
    public static bool move(int p, int bit)
    {
        bit = bit | (1 << p);
        if (bit == 15) return true;

        foreach (int i in list[p])
        {
            int m = (1 << i);
            if((bit & m) != m)
            {
                if(move(i, bit))
                {
                    return true;
                }
            }
        }

        return false;
    }
}


Measured memory_bytes: 13268
use std::io::BufRead; fn main() { let handle = std::io::stdin();
    let mut word = String::new();
    handle.lock().read_line(&mut word).unwrap();
    word.pop();
    let mut s = String::new();
    for line in handle.lock().lines().map(|a| a.unwrap()) {
        line.trim();
        if line == "END_OF_TEXT" { break; }
        line.to_lowercase().split_whitespace()
            .map(|a| {
                let mut string_a = a.to_string();
                string_a.push(' ');
                s.push_str(&string_a);
            }).count();
    }
    println!("{}", s.split_whitespace().filter(|a| **a == word).count());
}


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

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

}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm> // sort
#include <map>       // pair
#include <string>
#include <stdio.h>
#include <numeric>
using namespace std;

int GCD(int x, int y)
{
    return x ? GCD(y % x, x) : y;
}

int main(int argc, const char *argv[])
{

    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    vector<int> stacked_GCD_from_Left (N,0);
    vector<int> stacked_GCD_from_Right (N,0);
    for(int i = 0; i < N; i++)
    {
        if(i == 0)
        {
            stacked_GCD_from_Left[i] = A[i];
        }
        else
        {
            stacked_GCD_from_Left[i] = GCD(stacked_GCD_from_Left[i-1],A[i]);
        }
    }

    for (int i = N-1; i >= 0; i--)
    {
        if (i == N-1)
        {
            stacked_GCD_from_Right[i] = A[i];
        }
        else
        {
            stacked_GCD_from_Right[i] = GCD(stacked_GCD_from_Right[i +1], A[i]);
        }
    }

    vector<int> one_changed_GCD(N,0);

    for(int i = 0; i < N; i++)
    {
        if(i == 0)
        {
            one_changed_GCD[i] = stacked_GCD_from_Right[i+1];
        }
        else if (i == N -1) 
        {
            one_changed_GCD[i] = stacked_GCD_from_Left[i-1];
        }
        else
        {
            one_changed_GCD[i] =GCD(stacked_GCD_from_Left[i-1],stacked_GCD_from_Right[i+1]);
        }
    }

    std::vector<int>::iterator iter = std::max_element(one_changed_GCD.begin(), one_changed_GCD.end());
    size_t index = std::distance(one_changed_GCD.begin(), iter);

    cout << one_changed_GCD[index];
        // int GCD_1 = 0;
        // int GCD_2;

        // for (int i = 0; i < N - 1; i++)
        // {
        //     if (N == 2)
        //     {
        //         cout << max(A[0], A[1]);
        //         return 0;
        //     }

        //     GCD_1 = gcd<int, int>(A[0], A[1]);
        //     GCD_2 = gcd<int, int>(A[1], A[2]);
        // }

        return 0;
}

Measured memory_bytes: 1920
import scala.io.StdIn._

object Main extends App {


  val Array(n,w) = readLine().split(" ").map(_.toInt)
  val wv = Array.fill(n)(readLine().split(" ").map(_.toInt))
  def solve() = {
    rec(w, 0)
  }

  val dp = Array.fill(w+1)(Array.fill(n+1)(-1L))

  def rec(restW: Int, i: Int): Long = {
    if(dp(restW)(i) != -1) dp(restW)(i)
    else {
      val value = if(i == n) 0
      else {
        if(restW >= wv(i)(0)) {
          Math.max(rec(restW, i+1), rec(restW - wv(i)(0), i+1) + wv(i)(1))
        } else rec(restW, i+1)
      }
      dp(restW)(i) = value
      value
    }
  }

  println(solve())

}



Measured memory_bytes: 135724
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<array>
using namespace std;
#define  ll long long
#define  ull unsigned long long
#define  ul unsigned long
#define all(v) v.begin(),v.end()
#define sz(n) (int)n.size()
#define pb(s) push_back(s);
#define format(n) fixed<<setprecision(n)
#define finl "\n"
#define Mohammed_Atef_Hassan fast();
#define mod 1000000007
#define INF LLONG_MAX
#define PI acos(-1)
#define clr(dp,n) memset(dp,n,sizeof dp)
#define ex(n) return cout<<n<<finl,0;
int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
int dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
void fast() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

#ifdef ONLINE_JUDGE
	//	freopen("palindrome.in", "r", stdin);

	//freopen("palindrome.out", "w", stdout);
#endif
#ifndef ONLINE_JUDGE
	//freopen("input.in", "r", stdin);
	//  freopen("output.out", "w", stdout);
#endif
}
int main()
{
	Mohammed_Atef_Hassan
		int n, w, h;
	cin >> n >> w >> h;
	cout << (n - w + 1)*(n - h + 1) << finl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int a,b,id;
};
bool c1(node a,node b)
{
    return a.id<b.id;
}
node a[100000];
int main()
{
    int n;
    cin>>n;
    for (int i=0;i<n;i++)
    {
        cin>>a[i].id;
        if (i==0)a[i].a=1;
        else a[i].a=50000+a[i-1].a;
    }
    int need=1000000000;
    for (int i=n-1;i>=0;i--)
    {
        a[a[i].id-1].b=need-a[a[i].id-1].a;
        need--;
    }
    cout<<a[0].a;
    for (int i=1;i<n;i++)
        cout<<' '<<a[i].a;
    cout<<endl<<a[0].b;
    for (int i=1;i<n;i++)
        cout<<' '<<a[i].b;
    cout<<endl;
}


Measured memory_bytes: 896
#include <stdio.h>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;

int main(void){
	int num, min, a[1000];

	while(1){
		scanf("%d", &num);
		if(!num) break;
		for(int i=0; i<num; i++){
			scanf("%d", &a[i]);
		}

		sort(a, a+num);
		min=INT_MAX;
		for(int i=0; i<num-1; i++){
			min = fmin(min, a[i+1]-a[i]);
		}

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

	return 0;
}


Measured memory_bytes: 2736
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;
using LP = pair<ll,ll>;
using P = pair<ll,int>;
ll inf = 1e18;

int main()
{
    int n;
    cin >> n;
    vector<tuple<int, int, int>> g(n);
    
    rep(i, n) {
        int t, x, y;
        cin >> t >> x >>y;
        g[i] = make_tuple(t, x, y);
    }
    bool flag = true;
    rep(i,n){
        int t = 0, x= 0, y= 0;
        if (i!=0){
            t = get<0>(g[i-1]);
            x = get<1>(g[i-1]);
            y = get<2>(g[i-1]);
        }
        int nt, nx, ny;
        nt = get<0>(g[i]);
        nx = get<1>(g[i]);
        ny = get<2>(g[i]);
        if (nt%2 != (nx+ny)%2 or abs(nx-x)+abs(ny-y) > nt-t) {
            flag = false;
            break;
        }
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 4548
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<iomanip>
#include<stack>
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define sz(a) (int)a.size()
using namespace std;

int main() {
	int k, a, b;
	cin >> k >> a >> b;
	bool flag = false;
	for (int i = a; i <= b; i++) {
		if (i % k == 0) flag = true;
	}
	if (flag) cout << "OK" << endl;
	else cout << "NG" << endl;
}

Measured memory_bytes: 3596
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		BigInteger res = BigInteger.valueOf(1);
		for(int i = 1; i <= n; i++)
			res = res.multiply(BigInteger.valueOf(i));
		System.out.println(res);
	}
}

Measured memory_bytes: 12000
import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int t = Integer.parseInt(sc.next());
        int x = Integer.parseInt(sc.next());

        // 主処理

        double result = (double) t / x;

        // 出力
        System.out.println(result);
        sc.close();
    }
}

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


int main(){
    int H, W;
    cin>>H>>W;
    vector<vector<int>> Dif(81, vector<int>(81));
    vector<vector<int>> A(81, vector<int>(81));
    vector<vector<int>> B(81, vector<int>(81));
    for(int i=1; i<=H; i++){
        for(int j=1; j<=W; j++){
            cin>>A[i][j];            
        }
    }
    for(int i=1; i<=H; i++){
        for(int j=1; j<=W; j++){
            cin>>B[i][j];            
        }
    }
  	int MaxDif=0;
    for(int i=1; i<=H; i++){
        for(int j=1; j<=W; j++){
            Dif[i][j]=abs(A[i][j]-B[i][j]);
          	MaxDif=max(MaxDif, Dif[i][j]);
        }
    }
    bool DP[81][81][81*(81+81)];
    DP[1][1][Dif[1][1]]=true;
  	
    for(int i=1; i<H+1; i++){
        for(int j=1; j<W+1; j++){
            for(int k=0; k<(H+W+2)*MaxDif+1; k++){
                if(!DP[i][j][k])continue;

                if(i+1<=H){
                    DP[i+1][j][abs(k-Dif[i+1][j])]=true;
                    DP[i+1][j][abs(k+Dif[i+1][j])]=true;
                }
                if(j+1<=W){
                    DP[i][j+1][abs(k-Dif[i][j+1])]=true;
                    DP[i][j+1][abs(k+Dif[i][j+1])]=true;
                }
            }
        }
    }
  	
    for(int i=0; i<MaxDif*(H+W+2)+1; i++){
        if(DP[H][W][i]){
            cout<<i<<endl;
            break;
    	}
    }
}




Measured memory_bytes: 84352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

int main() {
	ll n,k,c;
	cin>>n>>k>>c;
	string s;
	cin>>s;
	ll l[200010]={},r[200010]={};
	for(ll i=0;i<n;i++){
		if(s[i]=='o'){
			l[0]=i;
			break;
		}
	}
	for(ll i=1;i<k;i++){
		ll now=l[i-1]+c;
		for(ll j=now+1;j<n;j++){
			if(s[j]=='o'){
				l[i]=j;
				break;
			}
		}
	}
	for(ll i=n-1;i>=0;i--){
		if(s[i]=='o'){
			r[k-1]=i;
	//		cout << i<<endl;
			break;
		}
	}
//	cout <<endl;
	for(ll i=k-2;i>=0;i--){
		ll now=r[i+1]-c;
		for(ll j=now-1;j>=0;j--){
			if(s[j]=='o'){
				r[i]=j;
		//		cout << j<<endl;
				break;
			}
		}
	}
//	cout <<endl;
	for(ll i=0;i<k;i++){
		if(r[i]==l[i]){
			cout << r[i]+1<<endl;
		}
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 6860
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    int a, b, c; cin >> a >> b >> c;

    for(int i=0; i<=b; ++i){
        if((a*i)%b == c){
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;

    return 0;
}

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

const int Max=8010;
const int mod=1e9+7;
int n,m,k,ans;
int f[Max][Max],inv[Max],mul[Max],a[200010],b[200010];

inline int get_int()
{
	int x=0,f=1;
	char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	if(c=='-') c=-1,c=getchar();
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return x*f;
}

inline int ksm(int a,int b)
{
	int ans=1;
	while(b)
	{
	  if(b&1) ans=(1ll*ans*a)%mod;
	  b>>=1;
	  a=(1ll*a*a)%mod;
	}
	return ans;
}

inline void pre()
{
	mul[0]=mul[1]=1;
	for(int i=2;i<=8000;i++) mul[i]=(1ll*mul[i-1]*i)%mod;
	inv[0]=inv[1]=1;
	for(int i=2;i<=8000;i++) inv[i]=ksm(mul[i],mod-2);
}

inline int C(int n,int m)
{
	if(n>=0 && m>=0 && n>=m) return (1ll*mul[n]*inv[m]%mod*inv[n-m]%mod)%mod;
	return 0;
}

int main()
{
	pre();
	n=get_int();
	for(int i=1;i<=n;i++) a[i]=get_int(),b[i]=get_int(),f[2001-a[i]][2001-b[i]]++;
	for(int i=1;i<=4001;i++)
	  for(int j=1;j<=4001;j++)
	    f[i][j]=(f[i][j]%mod+(f[i][j-1]+f[i-1][j])%mod)%mod;

	for(int i=1;i<=n;i++) ans=(ans+f[2001+a[i]][2001+b[i]])%mod;
	for(int i=1;i<=n;i++) ans=((ans-C((a[i]<<1)+(b[i]<<1),a[i]<<1))%mod+mod)%mod;
	ans=1ll*ans*(mod+1)/2%mod;
	cout<<(ans%mod+mod)%mod<<"\n";

	return 0;
}

Measured memory_bytes: 127104
#include <bits/stdc++.h>
using namespace std;
#define AB_BHI_NI_DEGI                \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define int long long
#define pb push_back
#define N 100009
#define inf 1e18
const double PI = 3.141592653589793238462643383279;
int mod = 1e9 + 7;
//int mod = 998244353;
#define P pair<int, int>
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define vi vector<int>
#define ld long double

int power(int a, int n)
{
    int res = 1;
    while (n)
    {
        if (n & 1)
            res = (res * a) % mod;
        n = n / 2;
        a = (a * a) % mod;
    }
    return res;
}

void solve()
{
    int n, d;
    cin >> n >> d;
    int ans = 0;
    while (n--)
    {
        int x, y;
        cin >> x >> y;
        x = x * x;
        y = y * y;
        if ((x + y) <= (d * d))
            ans++;
    }
    cout << ans << "\n";
}
int32_t main()
{
    AB_BHI_NI_DEGI
    int Test = 1;
    //cin >> Test;
    while (Test--)
        solve();
    return 0;
}

Measured memory_bytes: 3644
#include<cstdio>
#include<iostream>
using namespace std;
int a,b,c;
long long k;
int main()
{
	scanf("%d%d%d%lld",&a,&b,&c,&k);
	if (k&1) printf("%d",b-a);
	else printf("%d",a-b);
} 

Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
int N,M,a[1005];
int main(){
	scanf("%d%d",&N,&M);
	int cnt=0;
	for(int i=1;i<=M;i++)
		scanf("%d",&a[i]),cnt+=a[i]%2;
	if(M==1) return (a[1]==1? puts("1\n1\n1"):printf("%d\n2\n%d 1",a[1],a[1]-1)),0;
	if(cnt>2) return puts("Impossible"),0;
	int pos=1;
	for(int i=1;i<=M;i++)
		if(a[i]%2) swap(a[i],a[pos]),pos=M;
	
	if(a[M]==1) swap(a[1],a[M]);
	for(int i=1;i<=M;i++) printf("%d ",a[i]);puts("");
	
	a[1]++;a[M]--;
	if(a[M]==0) M--;
	printf("%d\n",M);
	for(int i=1;i<=M;i++) printf("%d ",a[i]);
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[200010];
struct edge{int to,cost;};
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;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
int n;
int a[200010],b[200010];
signed main(){
	cin>>n;
	rep(i,n){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b,b+n);
	rep(i,n){
		if(a[i]==b[n-1])cout<<b[n-2]<<endl;
		else cout<<b[n-1]<<endl;
	}
	return 0;
}


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

int main(){
    int n;
    cin >> n;
    
    vector<vector<vector<int> > > building(4,vector<vector<int> >(3,vector<int>(10,0)));
    
    rep(i, n){
        int b,f,r,v;
        cin >> b >> f >> r >> v;
        b--;
        f--;
        r--;
        
        building[b][f][r]+=v;
    }
    
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < 10; k++){
                cout << " " << building[i][j][k];
                if(k == 9) cout << endl;
            }
        }
        if(i < 3) cout << "####################" << endl;
    }
}





Measured memory_bytes: 3148
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

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

	string s;
	cin >> s;
	N = s.size();
	for (int i = 0; i < (N+1)/2; i++) {
		if (s[i] != s[N - i - 1])M++;
	}
	cout << M << endl;
}

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

int main(){

    int n,k;
    string s;
    cin>>n>>k>>s;

    if(s.at(k-1)=='A') s.at(k-1)='a';
    if(s.at(k-1)=='B') s.at(k-1)='b';
    if(s.at(k-1)=='C') s.at(k-1)='c';

    cout<<s<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int o=0;
	int n;
	string s;
	cin>>n;
	if(n>999){
		cout<<"ABD"<<endl;
	}
	else cout<<"ABC"<<endl;
	
}
//伊勢田=sanadayukimura"73"
//伊勢田=48
//73=48
//両方から23を引いて
//50=25
//2=1


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

void main(){
  string s;
  for(;;){
    s=readln();
    if(stdin.eof()) break;
    int num = to!int(chomp(s));
    int result = 0;
    int[] nums = new int[num];
    for(int i=0;i  < num;++i) nums[i] = 1;
    nums[0] = 0;
    for(int i=1;i < sqrt(cast(double)num);++i){
      if(nums[i] == 1){
        for (int j = (i+1); (i+1) * j <= num; j++) nums[(i+1) * j - 1] = 0;
      }
    }
    for(int i = 0;i < num; ++i){
      if(nums[i] == 1)++result;
    }
    writeln(result);
  }
}

Measured memory_bytes: 9940
#include <iostream>
#include <math.h>
using namespace std;

int main(){
  int n;
  int a=0;
  cin>>n;
  for(int i=0;i<3;i++){
    if(n/pow(10,2*i+1)>=1) a += pow(10,2*i+1)-pow(10,2*i);
    else if(n/pow(10,2*i)>=1){a += n-pow(10,2*i)+1; break;}
    else {break;}
            
  }
  cout<<a<<endl;
  return 0;
}

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

using namespace std;
using Graph = vector<vector<int>>;
using Grid= vector<vector<char>>;
using vin= vector<int>;
using ll=long long;
using vll= vector<ll>;
using vbl=vector<bool>;
using vch=vector<char>;
using pinin=pair<int ,int>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rell(i,n) for (ll i=0; i< (ll)(n); i++)
#define sort(x) sort(x.begin(), x.end());
#define rese(x) reverse(x.begin(), x.end());

string yes="Yes",no="No";

int main() {
    int n;
    ll k;
    cin>>n>>k;
    vll a(n);
    rep(i,n) cin>>a[i];
    ll ng=-1;
    ll ok=1e9+100;
    while(ok-ng>1){
        ll mid=(ok+ng)/2;
        if(mid==0){
            cout<<1<<endl;
            return 0;
        }
        ll sum=0;
        rep(i,n){
            sum+=(a[i]-1)/mid;
        }
        if(sum>k) ng=mid;
        else ok=mid;
        
       
    }
    cout<<ok<<endl;
  

}


Measured memory_bytes: 4840
#include<iostream>
#include<algorithm>
#include<vector>

int main(){
    int n;
    std::cin>>n;
    std::vector<int> an(n,0);

    for (int i = 0; i < n; i++)
    {
        std::cin>>an[i];
    }

    decltype(an)::iterator result=std::unique(an.begin(),an.end());//resultは重複要素が削除された数列の末尾のイテレータ

    an.erase(result,an.end());//uniqueだけでは要素数の削除は行われない
    for(int i=0;i<an.size();i++){
        std::cout<<(i? " ":"")<<an[i];
    }
    std::cout<<std::endl;
    return 0;

}



Measured memory_bytes: 3112
object Main extends App {
	import scala.math._

	val NC = scala.io.StdIn.readLine.split(" ").map(_.toInt)

	val C = Array.ofDim[Int](NC(1), 100001)

	for(i<-0 until NC(0)){
		val temp = scala.io.StdIn.readLine.split(" ").map(_.toInt)

		for(j<-(temp(0)) to temp(1)){
			C(temp(2)-1)(j) = 1
		}
	}

	var count = 0
	var sum = 0

	for(i<-0 until 100000){
		sum = 0
		for(j<-0 until NC(1)){
			sum = sum + C(j)(i)
		}
		count = max(sum, count)
	}

	println(count)

	
}

Measured memory_bytes: 64716
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
/*using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define rep(i,l,r) for(int i=l;i<r;i++)
#define bep(i,l,r) for(int i=l;i>=r;i--)
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define el '\n'
#define sz(s) (int)s.size()
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define mr  make_pair

int mod = 1e9+7;
int inf = 4e18;
const int N = 5e5+5;
//int powmod(int a,int b) {int res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}
signed main()
{
    io
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
       int n,m;
       cin>>n>>m;
       int ans = ((n)*(n-1))/2 + ((m)*(m-1))/2;
       cout<<ans<<el;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

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

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

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

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

#define SUM(vec) accumulate(all(vec),0LL) // 配列の中身を全部足す
template<typename T>void print(T&& x){cout<<x<<endl;}// 改行付き出力
ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int ctoi(char c){return c-'0';}



// TODO: write
int main() { 
  string s;cin>>s;
  if(s.size()%2){
    print("No");
    return 0;
  }
  for(int i = 0;i < s.size();i+=2){
    if(s[i] == 'h' && s[i+1] == 'i');
    else{
      print("No");
      return 0;
    }
  }
  print("Yes");
  return 0;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int long long int
#define endl "\n"
const int MOD=1e9+7;
#ifndef HOME
#define cerr if(0)cerr
#endif

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int x = (n)*(n-1);
    x = x/2;
    cout<<x<<endl;
    
    return 0;
    
}



Measured memory_bytes: 256
n = int(input())
songs = []
for i in range(n):
    a,b = input().split()
    songs.append([a,b])
sleep = input()
s =0
r =0
for a,b in songs:
    if r ==1:
        s+=int(b)
    if a == sleep:
        r=1
print(s)

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


const int MAX = 510000;
const int MOD = 998244353;

long long fac[MAX], finv[MAX], inv[MAX];


long long modpow(long int a, long int n, long int mod) {
    long int res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    COMinit();

    ll N, M, K; cin >> N >> M >> K;
    ll SUM = modpow(M, N, MOD);
    ll SUB = 0;
    for(int i = 0; i <= K; i++){
        SUB += (((COM(N-1, i) * M)%MOD) * modpow(M-1, N-i-1, MOD))%MOD;
        SUB %= MOD;
    }
    cout << SUB << endl;
    

}

Measured memory_bytes: 15580
#include<iostream>

using namespace std;

int main(void)
{

	int N,i,ans=0;
	
	cin >> N;

	int A[N];
	int B[N];
	int C[N];

	for(i=0;i<N;i++)
	{

		cin >> A[i];
		A[i]--;
	}

	for(i=0;i<N;i++)
	{

		cin >> B[i];
		B[i];
	}

	for(i=0;i<N-1;i++)
	{

		cin >> C[i];
		C[i];
	}

	
	for(i=0;i<N;i++)
	{

		ans=ans+B[i];

	}

	
	for(i=0;i<N-1;i++)
	{

		if(A[i+1]==A[i]+1)
			ans=ans+C[A[i]];


	}

	cout << ans <<endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <limits>
#include <queue>
#include <iomanip>
#include <deque>
#include <stack>
#include <cstdio>
#include <cmath>
#include <complex.h>
#include <cstdio>
#include <random>
#include <chrono>
#include <numeric>
#include <cassert>
#include <iso646.h>
#include <exception>
#include <stdexcept>

using namespace std;

typedef long long i64;

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

    int n;
    cin >> n;

    int a[10];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        a[i] = a[i] & 1;
    }

    int cnt_odd = 1;
    for (int i = 0; i < n; i++)
        if (!a[i])
            cnt_odd *= 2;

    int cnt = 1;
    for (int i = 0; i < n; i++)
        cnt *= 3;

    cout << cnt - cnt_odd;
}

Measured memory_bytes: 256
N=int(input())
S=input()
R=S.count("R")
G=S.count("G")
B=S.count("B")
 
 
count=R*G*B
for i in range(0,N-2):
    for j in range(i+1,N-1):
        k=j+(j-i)
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            count=count-1
 
print(count)

Measured memory_bytes: 9180
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func readInts(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		a[i], _ = strconv.Atoi(sc.Text())
	}
	return a
}

func main() {
	var N int
	fmt.Scan(&N)
	h := readInts(N)
	dp := make([]int, N)
	dp[1] = abs(h[0] - h[1])
	for i := 2; i < N; i++ {
		dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
	}
	fmt.Println(dp[N-1])
}


Measured memory_bytes: 2688
def bomb(x,y):
    global M
    s=M[y+2]
    R=[-3,-2,-1,1,2,3]
    if s[x+2]=="0":return
    M[y+2]=s[:x+2]+"0"+s[x+3:]
    for d in R:
        bomb(x+d,y)
        bomb(x,y+d)
    return

A=range(14)
B=range(8)
M=["00000000000000" for i in A]
z="000"
n=input()
for i in range(n):
    s=raw_input()
    for j in B:
        M[j+3]=z+raw_input()+z
    x=input()
    y=input()
    bomb(x,y)
    print "Data %d:" %(i+1)
    for j in B:
        print M[j+3][3:-3]

Measured memory_bytes: 4288
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define println(x) cout << x << endl;
using namespace std;
int main()
{
    string a, b, c;
    cin >> a >> b >> c;
    cout << a[0] << b[1] << c[2] << endl;
    return 0;
}

Measured memory_bytes: 3560
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // Your code here!
        
       	Scanner sc=new Scanner(System.in);
		char c = sc.next().charAt(0); 
   
		if(Character.isUpperCase(c))
		{
		    System.out.println("A");
		}
		else if(Character.isLowerCase(c))
		{
		    System.out.println("a");
		}
    }
}

Measured memory_bytes: 35400
#include<iostream>
#include<cassert>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
const int INF = 1e10;
const long double PI = (acos(-1));


signed main() {
	int N;
	cin >> N;
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		if (i % 3 == 0)continue;
		if (i % 5 == 0)continue;
		sum += i;
	}
	cout << sum;
}

Measured memory_bytes: 3624
N, M = map(int, input().split())  # N本のマッチ棒, M種類の数字
A = list(map(int, input().split()))  # 使える数字の配列A0 ~ Am
A.sort()
A.reverse()


def num(a):  # sticks[A[i] - 1]でA[i]にに必要なマッチの本数
    return [2, 5, 5, 4, 5, 6, 3, 7, 6][a - 1]


dp = [0] * (N + 1)  # dp[N] = 桁数
for i in range(1, N + 1):
    match_match = [dp[i - num(a)] + 1 for a in A if i - num(a) >= 0]
    if match_match:
        dp[i] = max(match_match)
    else:
        dp[i] = -1000

remind = 0  # 消費したマッチ棒の数
ans = ''  # answer
for i in range(dp[N]):
    for a in A:
        if N - num(a) - remind >= 0:
            if dp[N - num(a) - remind] == dp[N] - 1 - i:
                remind += num(a)
                ans += str(a)
                break
print(ans)


Measured memory_bytes: 3308
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <bits/stdc++.h>
#include <set>
#include <vector>
#include <queue>
#include <bitset>
#define NL << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define fill(x, y) memset(x, y, sizeof(y))
#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define inarr(arr, n)                            \
    {                                       \
        for(int i =0;i<n;i++){              \
            cin >> arr[i];                  \
        }                                   \
    }
typedef long long ll;
const int MOD = 1e9 + 7;
using namespace std;

void solve()
{
    ll n, k ; cin >> n >> k;
    ll arr[n];
    inarr(arr, n);
    ll dp[n];

    
    dp[0] = 0;
    dp[1] = abs(arr[1] - arr[0]);
    if(n==2){
        cout << dp[1] << endl; return;

    }
    for(int j =2;j <n;j++){
        dp[j] = LLONG_MAX;
        for(int i =0;i<k;i++){
            if(j-i-1 >= 0){
                dp[j] = min(dp[j], dp[j-1 - i] + abs(arr[j] - arr[j-i-1]) );
            }
        }
         
    }
    cout << dp[n-1] << endl;

}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; t = 1; 
    // int t; cin >> t;
    while (t--)
        solve();
}


Measured memory_bytes: 5168
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();

    VI a(3); cin >> a;
    SORT(a);
    a.erase(unique(all(a)), a.end());
    cout << a.size() << "\n";
}


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

int main() {
    int a, b;
    cin >> a >> b;
    int ans = max(a+b, a-b);
    ans = max(ans, a*b);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 892