akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int,int> P;
ll comb(ll x){
  //2のcomb
  return (x*(x-1))/2;
}
int main()
{
  long N;
  cin >> N;
  vector<long> A(N);
  rep(i, N) cin >> A.at(i);
  rep(i, N) A.at(i) --;
  vector<long> M(N);
  rep(i, N) M.at(A.at(i))++;
  ll Max = 0; //最大値
  rep(i, N) Max += comb(M.at(i));
  rep(i,N){
    ll ans = Max;
    ans -= comb(M.at(A.at(i)));
    ans += comb(M.at(A.at(i))-1);
    cout << ans << endl;
  }
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> cnt(60, vector<int>(2, 0));
    rep(i, n){
        ll a;
        cin >> a;
        rep(j, 60){
            if(1 & (a >> j))cnt[j][1]++;
            else cnt[j][0]++;
        }
    }

    ll ans = 0;
    ll mod = 1000000007;
    ll pow = 1;
    rep(i, 60){
        ans += pow * cnt[i][0] % mod * cnt[i][1] % mod;
        ans %= mod;
        pow = pow * 2 % mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <iostream>
#include <climits>
#include <cfloat>


using namespace std;


int n, m, g, d;
int s[100];
bool l[100][100];
int works[100];
bool workl[100][100];

void shuffle()
{
	for (int i = 0 ; i < d; ++i)
	{
		for (int j = 0; j < n-1; ++j)
		{
			if (workl[i][j])
				swap(works[j], works[j+1]);
		}
	}
}

int main()
{
	char buf[128];
	while (true)
	{
		cin.getline(buf, sizeof(buf));
		sscanf(buf, "%d", &n);
		if (n == 0)
			break;

		for (int i = 0; i < n; ++i)
			s[i] = i;

		cin.getline(buf, sizeof(buf));
		sscanf(buf, "%d", &m);
		cin.getline(buf, sizeof(buf));
		sscanf(buf, "%d", &g);
		cin.getline(buf, sizeof(buf));
		sscanf(buf, "%d", &d);
		--m;
		--g;

		for (int i = 0; i < d; ++i)
		{
			cin.getline(buf, sizeof(buf));
			for (int j = 0; buf[j] != '\0'; ++j)
				l[i][j] = (buf[j] == '1');
		}

		memcpy(works, s, sizeof(works));
		memcpy(workl, l, sizeof(workl));
		shuffle();
		if (works[g] == m)
		{
			puts("0");
			continue;
		}

		int x, y;
		bool ok = false;
		for (y = 0; y < d; ++y)
		{
			for (x = 0; x < n-1; ++x)
			{
				if (l[y][x]
					|| (x != 0 && l[y][x-1])
					|| (x != n-2 && l[y][x+1])
					)
					continue;

				memcpy(works, s, sizeof(works));
				memcpy(workl, l, sizeof(workl));
				workl[y][x] = true;

				shuffle();
				if (works[g] == m)
				{
					ok = true;
					break;
				}
			}
			if (ok)
				break;
		}
		if (ok)
			printf("%d %d\n", y+1, x+1);
		else
			puts("1");
	}

	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

int main(void)
{
  int i, n, total = 0;
  char moji[100001];
  scanf("%d", &n);
  scanf("%s", moji);
  
  for( i = 0; i < n; i++ ){
    if( moji[i] != moji[i+1] ){
      total += 1;
    }  
  }
      
  printf("%d\n", total);
  
  return 0;
}

Measured memory_bytes: 256
n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)
ans = 0
(n-1).times do |i|
  if a[i] + 1 == a[i+1]
    ans += c[a[i]-1]
  end
end
puts ans + b.sum


Measured memory_bytes: 14284
#include<bits/stdc++.h>
#define boost ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define mem(a,b) memset(a,b,sizeof(a))
#define endl "\n"
#define mod 1000000007
#define PI 3.1415926535897932384626
#define pq priority_queue
#define pb push_back
#define mp make_pair
using namespace std;
/*
int gcd(int x,int y)
{
    if(x%y==0)
    return y;
    return gcd(y,x%y);
}

int no1(int x)
{
    int count=0;
    while(x)
    {
        if(x%2)
        count++;
        x=x>>1;
    }
    return count;
}
ll power(int  b,int p)
{
    if(p==0)
    return 1;
    ll temp=power(b,p/2);
    temp=temp*temp;
    if(p%2==1)

    temp=temp*b;
    return temp;
}
bool cmp(const pair<int, pair<int,int> > & p1,const pair<int, pair<int,int> > & p2)
{
    if(p1.first>p2.first)
        return true;
    if(p1.first==p2.first&&p1.second.first<p2.second.first)
        return true;
    return false;
}
*/
int dp[3][100005];
int points(int x,int p,int a[],int b[],int c[],int n)
{
    if(x>n)
        return 0;
    if(dp[p][x]!=-1)
        return dp[p][x];
    if(p==0)
    dp[p][x]=max(b[x]+points(x+1,1,a,b,c,n),c[x]+points(x+1,2,a,b,c,n));
    else
        if(p==1)
        dp[p][x]=max(a[x]+points(x+1,0,a,b,c,n),c[x]+points(x+1,2,a,b,c,n));
    else
        dp[p][x]=max(b[x]+points(x+1,1,a,b,c,n),a[x]+points(x+1,0,a,b,c,n));
    return dp[p][x];
}
int main()
{
    int n;
    int a[100005],b[100005],c[100005];
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
    }

    for(int i=0;i<100005;i++)
        {
            dp[0][i]=-1;
            dp[1][i]=-1;
            dp[2][i]=-1;
        }
    cout<<max(a[1]+points(2,0,a,b,c,n),max(b[1]+points(2,1,a,b,c,n),c[1]+points(2,2,a,b,c,n)));
    return 0;

}


Measured memory_bytes: 11904
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	if (!(n&(n-1))) return puts("No"),0;
	puts("Yes");
	printf("1 2\n2 3\n3 %d\n%d %d\n%d %d\n",n+1,n+1,n+2,n+2,n+3);
	for (int i=4;i<n;i+=2) printf("1 %d\n%d %d\n1 %d\n%d %d\n",i,i,i+1+n,i+1,i+1,i+n);
	if (!(n&1))
	{
		for (int i=2;i<=n;i++)
		{
			int j=i^n^1;
			if (i!=3&&j!=3&&j<=n)
			{
				printf("%d %d\n%d %d\n",i,n,j,2*n);
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2304
from sys import stdin
from math import factorial

def permutations_count(n, r):
  return factorial(n) // factorial(r) // factorial(n - r)

N,K = map(int,stdin.readline().split())
mod = pow(10,9)+7

frame = N-K+1
for i in range(1,K+1):
  if K == N:
    if i == 1:
      print("1")
    else:
      print("0")
  else:
    if i > frame:
      print("0")
    else:
      select=permutations_count(frame, i) % mod
      pattern=permutations_count(K-1, i-1) % mod
      print((select * pattern) % mod )

Measured memory_bytes: 69336
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func nextInt() int {
   sc.Scan()
   i, _ := strconv.Atoi(sc.Text())
   return i
}

func storeIntArr(n int) []int {
    var a []int
    for i := 0; i < n; i++ {
        a = append(a, nextInt())
    }
    return a
}

func main() {
    sc.Split(bufio.ScanWords)

    a := nextInt()
    b := nextInt()
    c := nextInt()
    x := nextInt()

    var count int
    for i := 0; i <= a; i++ {
        for j := 0; j <= b; j++ {
            for k := 0; k <= c; k++ {
                total := i*500 + j*100 + k*50
                if total == x {
                    count++
                }
            }
        }
    }
    fmt.Println(count)
}


Measured memory_bytes: 640
//package at_coder;

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc =  new Scanner(System.in);
		String str = sc.next();
		int length = str.length();
		char[] num = {'0','1'};
		int count = 0;
		for(int i=0;i<length;i++)
			if(str.charAt(i)==num[i%2])
				count++;
		System.out.println(count <= length/2 ? count : length-count);
	}
}

Measured memory_bytes: 23580
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#define int long long
using namespace std;
const int INF = 1000000000000;
const int mod = 1000000007;
int test[345678];
signed main() {
	int n, a, mae = 0, sum = 0, ans = 0; cin >> n;
	for (int h = 0; h < n; h++) {
		cin >> test[h];
	}
	for (int h = 0; h < n; h++) {
		int b = h;
		while (b--) {
			if (b < 0) { break; }
			if (test[b] > test[b + 1]) {
				swap(test[b], test[b + 1]);
			}
			else { break; }
		}
		for (int i = 0; i < n; i++) {
			if (i == 0) { cout << test[i]; }
			else { cout << ' ' << test[i]; }
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3100
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<numeric>
#include<cassert>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define rep(i,s,n) for(int i=(s); i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x)

using namespace std;

typedef unsigned int uint;
typedef long long ll;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

int ans[10][10];

int main(){
  int cs = 1;
  while(int n = getInt()){
    int cnt = 0;
    REP(i, n){
      REP(j, i + 1){
	int y = i % 2 == 1 ? j : i - j;
	int x = i - y;
	ans[y][x] = ++cnt;
      }
    }

    int cnt2 = n * n;
    REP(i, n - 1){
      REP(j, i + 1){
	int y = i % 2 == 1 ? j : i - j;
	int x = i - y;
	ans[n - y - 1][n - x - 1] = cnt2--;
      }
    }

    printf("Case %d:\n", cs++);

    REP(i, n){
      REP(j, n){
	printf("%3d", ans[i][j]);
      }
      puts("");
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,i,a,b;
    cin>>n;
    for(i=0;i<=n/2;i++)
    {
        if(pow(2,i)<=n)
            b=pow(2,i);
        if(pow(2,i)>n)
            break;
    }
    cout<<b<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
int main()
{
   string s;
  cin>>s;
  if(s.find("AB")!=-1 || s.find("BA")!=-1)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}
   





Measured memory_bytes: 256
import java.util.*

const val MOD: Long = (1e9+7).toLong()
fun Double.format(digits: Int) = String.format("%.${digits}f", this)
fun <T : Comparable<T>> Iterable<T>.argmax(): Int? = withIndex().maxBy{it.value}?.index
fun <T : Comparable<T>> Iterable<T>.argmin(): Int? = withIndex().minBy{it.value}?.index

fun main(args: Array<String>) {
    val reader = System.`in`.bufferedReader()
    var (n, a, b, c, d) = reader.readLine()!!.split(" ").map{it.toInt()}
    val s = reader.readLine()!!

    if (c < d) {
        if (s.take(d).drop(b-1).contains("##")) {
            println("No")
        } else {
            if (s.take(c).drop(a-1).contains("##")) {
                println("No")
            } else {
                println("Yes")
            }
        }

        return
    }

    if (b > 1) {
        if (!s.take(d+1).drop(b-2).contains("...")) {
            println("No")
        } else {
            if (s.take(c).drop(a-1).contains("##")) {
                println("No")
            } else {
                if (s.take(d).drop(b-1).contains("##")) {
                    println("No")
                } else {
                    println("Yes")
                }
            }
        }
    } else {
        if (!s.take(d+1).drop(b-1).contains("...")) {
            println("No")
        } else {
            if (s.take(c).drop(a-1).contains("##")) {
                println("No")
            } else {
                if (s.take(d).drop(b-1).contains("##")) {
                    println("No")
                } else {
                    println("Yes")
                }
            }
        }
    }
}


Measured memory_bytes: 41240
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
#define ll long long
#define re register
#define pb push_back
#define fi first
#define se second
const int N=1e6+10;
const int mod7=1e9+7;
const int mod=1e9+7;
void read(int &a)
{
    a=0;int d=1;char ch;
    while(ch=getchar(),ch>'9'||ch<'0')
        if(ch=='-')
            d=-1;
    a=ch^48;
    while(ch=getchar(),ch>='0'&&ch<='9')
        a=(a<<3)+(a<<1)+(ch^48);
    a*=d;
}
void read(ll &a)
{
    a=0;int d=1;char ch;
    while(ch=getchar(),ch>'9'||ch<'0')
        if(ch=='-')
            d=-1;
    a=ch^48;
    while(ch=getchar(),ch>='0'&&ch<='9')
        a=(a<<3)+(a<<1)+(ch^48);
    a*=d;
}
int main()
{
    int x,y,z;
    read(x),read(y),read(z);
    swap(x,y),swap(x,z);
    cout<<x<<" "<<y<<" "<<z<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define ll long long
#define fr(i, n) for (int i = 0; i < n; i++)
#define frf(i, j, n) for (int i = j; i <= n; i++)
#define frd(i, n) for (int i = n; i >= 0; i--)
#define mp(i, j) make_pair(i, j)
#define pb(x) push_back(x)
using namespace std;
// typedef vector<vector<ll> > matrix;
// const ll S = 3e5 + 20;
// const ll N = 1e6 + 1;
// const ll PRIME = 1e9 + 7;
// const ll MAX = 1e6;

void solve()
{
    int n;
    cin >> n;
    string str = "";
    int i = 0;
    if (n == 1)
    {
        cout << "a";
        return;
    }
    while (n > 0)
    {
        n--;
        str += ((n % 26) + 'a');
        n/=26;
    }
    reverse(str.begin(), str.end());
    cout << str;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

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


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

vector<int> dp;
vector<int> x,y;
int N;

int calc(int id){
	if(dp[id]>=0) return dp[id];
	int res=1;
	for(int i=0;i<N;i++){
		if(x[id]>x[i] && y[id]>y[i]){
			res=max(res,calc(i)+1);
		}
	}
	dp[id]=res;
	return res;
}

int main()
{
	int n,m;
	while(cin>>n){
		if(n==0) break;
		x=vector<int>();
		y=vector<int>();
		for(int i=0;i<n;i++){
			int a,b;
			cin>>a>>b;
			x.push_back(a);
			y.push_back(b);
		}
		cin>>m;
		N=n+m;
		dp=vector<int>(N,-1);
		for(int i=0;i<m;i++){
			int a,b;
			cin>>a>>b;
			x.push_back(a);
			y.push_back(b);
		}
		int res=0;
		for(int i=0;i<N;i++){
			res=max(res,calc(i));
		}
		cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
const int N=1e3+10;
int max(int a,int b){return a>b?a:b;}
int main(){
	int n,m,d[N][N],ans;
  pair<int,int> nxt;
  string s[N];
  	queue<pair<int,int>> q;
  	cin>>n>>m;
  for(int i=0;i<n;i++)cin>>s[i];
  for(int i=0;i<n;i++)for(int j=0;j<m;j++){
  d[i][j]=-1;
    if(s[i][j]=='#'){
    	q.push({i,j});
      d[i][j]=0;
    }
  }
  while(!q.empty()){
  	nxt=q.front();
    q.pop();
    if(nxt.first>0&&d[nxt.first-1][nxt.second]==-1){
    	d[nxt.first-1][nxt.second]=d[nxt.first][nxt.second]+1;
     	q.push({nxt.first-1,nxt.second});
    }
    if(nxt.first<n-1&&d[nxt.first+1][nxt.second]==-1){
    	d[nxt.first+1][nxt.second]=d[nxt.first][nxt.second]+1;
      q.push({nxt.first+1,nxt.second});
    }
    if(nxt.second>0&&d[nxt.first][nxt.second-1]==-1){
    d[nxt.first][nxt.second-1]=d[nxt.first][nxt.second]+1;
      q.push({nxt.first,nxt.second-1});
    }
    if(nxt.second<m-1&&d[nxt.first][nxt.second+1]==-1){
    	d[nxt.first][nxt.second+1]=d[nxt.first][nxt.second]+1;
      q.push({nxt.first,nxt.second+1});
    }
  }
  ans=0;
  for(int i=0;i<n;i++)for(int j=0;j<m;j++)ans=max(ans,d[i][j]);
  cout<<ans<<endl;
}

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

#define froop1(a,n) for(int i = a;i < n;i++)
#define froop2(a,n) for(int i = a;i > n;i--)
int main(){
	long long N,count = 0;
  cin >> N;
  vector<long long> num(N);
  froop1(0,N){
	cin >> num.at(i);
  }
  sort(num.begin(),num.end());
  long long max = num.at(N - 1);
  vector<bool> check(max + 1,false); //配列に値があるか
  vector<long long> check2(max + 1,0);//値が被っていないか
  froop1(0,N){
    check.at(num.at(i)) = true;
    check2.at(num.at(i))++; 
  }
  	vector<bool> prime(max + 1,true);
	for(long long i = 1;i <= max;i++){
		if(prime.at(i) == true && check.at(i) == true){
		  for(long long j = i * 2;j <= max;j += i){
		  prime.at(j)=false;
          }
		}
	}
  
	froop1(0,N){
		if(prime.at(num.at(i)) == true && check2.at(num.at(i)) == 1) count++;
	}	
	cout << count << endl;
return 0;
}

Measured memory_bytes: 12672
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()[::-1]
n = len(s)
# dp[i][j] := 先頭 i + 1 文字として考えられるもののうち，13 で割ったあまりが j であるものの数
dp = [[0 for _ in range(13)] for _ in range(n)]
# 初期値
if s[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(s[0])] = 1

# dp[i + 1][(j + x * d) % 13] += dp[i][j]，前のやつの余りj（j=0～12に集約されている）を用いて，次のやつを考えていく，
# xを10倍していくが，値が大きくなりすぎるとまずいので，mod13を毎回とる（結果は変わらない）
x = 10
for i in range(n - 1):
    if s[i + 1] == "?":
        start = 0
        end = 10
    else:
        start = int(s[i + 1])
        end = int(s[i + 1]) + 1
    for d in range(start, end):
        for j in range(13):
            dp[i + 1][(j + x * d) % 13] += dp[i][j]
            dp[i + 1][(j + x * d) % 13] %= mod
    x = x * 10 % 13

print(dp[n - 1][5] % mod)

Measured memory_bytes: 91736
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iterator>
#include <set>
#include <functional>

using namespace std;

#define DT int
#define forn(i,n)for(i=0;i<n;i++)
#define forc(i,c,n)for(i=c;i<=n;i++)
#define all(x) (x).begin(), (x).end()


int main() {
	ifstream fin("Text.txt");
	DT i, j, q;
	DT a, b, n, m,x;
	cin >> x;
	if (x < 1200)
		cout << "ABC";
	else
		cout << "ARC" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
//f[j](x) = a[j]x + b[j]でaがjの増加に伴い単調減少する場合
//クエリのxが単調でない場合はコメントアウトしたにぶたんの方を用いる
template<typename T> class CHT
{
private:
    using ptt = pair<T, T>;
    bool check(ptt l1, ptt l2, ptt l3){
        return (l2.first-l1.first)*(l3.second-l2.second)>=(l2.second-l1.second)*(l3.first-l2.first);
    }
    T f(int i, T x){
        return lines[i].first * x + lines[i].second;
    }
public:
    vector<ptt> lines;
    int head;
    CHT(): head(0){};
    void add(T a, T b){
        ptt line(a, b);
        while((int)lines.size() - head >= 2 && check(*(lines.end()-2), lines.back(), line)){
            lines.pop_back();
        }
        lines.emplace_back(line);
    }
    T get(T x){
        while((int)lines.size() - head >= 2 && f(head, x) >= f(head + 1, x)){
            head++;
        }
        return f(head, x);
        // int low = -1, high = lines.size() - 1;
		// while (high - low > 1) {
		// 	int mid = (high + low) / 2;
        //     if(f(mid, x) >= f(mid+1, x)){
        //         low = mid;
        //     }else{
        //         high = mid;
        //     }
		// }
		// return f(high, x);
    }
};

ll dp[200010];
int main(){
    ll n,c;
    cin >> n >> c;
    vector<ll>h(n);
    
    rep(i,n) cin >> h[i];
    CHT<ll> cht;
    rep(i,n){
        if(i==0){
            dp[i] = 0;
            cht.add(-2*h[i],h[i]*h[i]+dp[i]);
        }else{
            ll s = cht.get(h[i]);
            dp[i] = h[i]*h[i]+c+s;
            cht.add(-2*h[i],h[i]*h[i]+dp[i]);
        }
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 8560
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int N; cin >> N;
    int R; cin >> R;
    cout << R + 100 * (10 - min(N, 10)) << endl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, k;
	cin>>n>>k;
	vector<double> arr;
	for(int i =0;i<n;i++)
	{
		double a;
		cin>>a;
		arr.push_back((a + 1)/2);
	}
	double start = 0;
	for(int i =0;i<k;i++)
		start +=arr[i];
	
	double best = start;
	for(int i = k;i<arr.size();i++)
	{
		start +=arr[i];
		start -=arr[i- k];
		best = max(best,start);
	}
	cout<<fixed<<setprecision(10)<<best<<endl;
	return 0;
}

Measured memory_bytes: 2420
#偶奇合わせてたのはグルグル回してたからだが
#一意に決めるんなら偶奇合わせる必要ないのでは
def 解():
    N = int(input())
    dA ={}
    def lenbin(a):
        return len(bin(a)) - 2
    def addData(oDict,a):
        if a in oDict:
            oDict[a]+=1
        else:
            oDict[a]=1
    for a in map(int,input().split()):
        addData(dA,a)
    def searchPair(oD):
        iC = 0
        for a in sorted(oD.keys(),reverse=True):
            if oD[a]:
                t = ( 1 << lenbin(a)) - a
                if t == a:
                    iAT = oD[a] // 2
                    iC += iAT
                    oD[a] -= iAT *2
                elif t in oD:
                    iAT = min(oD[a],oD[t])
                    iC += iAT
                    oD[a] -= iAT
                    oD[t] -= iAT
        return iC
    print(searchPair(dA))
解()


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

int main(void){
  int a, b;
  cin >> a >> b;
  
  if (a >= 13) {
    cout << b << endl;
  }
  else if (6 <= a && a <= 12) {
    cout << b /2 << endl;
  }
  else {
    cout << 0 << endl;
  }
  
}

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

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define size(x) int(x.size())
#define pb push_back

using namespace std;
using ll=long long;
using pii= pair<int, int>;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template<typename... T> void rd(T&... args) {((cin>>args), ...);}
template<typename... T> void wr(T... args) {((cout<<args<<" "), ...);cout<<endl;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int X,n;
    cin>>X>>n;
    set<int> st;
    forn(i,n){
        int x;
        cin>>x;
        st.insert(x);
    }
    for(int i=0;;i++){
        if(!st.count(X-i)){
            cout<<X-i;
            return 0;
        }else if(!st.count(X+i)) return cout<<X+i,0;
    }
    return 0;
}



Measured memory_bytes: 3624
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int main() {
    int n, m, l;
    long *a[MAX];
    long *b[MAX];
    long *c[MAX];

    scanf("%d %d %d", &n, &m, &l);

    for (int i=0; i<n; ++i) {
        a[i] = (long*)malloc(sizeof(long)*m);
        for (int j=0; j<m; ++j) {
            scanf("%ld", &a[i][j]);
        }
    }
    for (int i=0; i<m; ++i) {
        b[i] = (long*)malloc(sizeof(long)*l);
        for (int j=0; j<l; ++j) {
            scanf("%ld", &b[i][j]);
        }
    }
    for (int i=0; i<n; ++i) {
        c[i] = (long*)malloc(sizeof(long)*l);
        for (int j=0; j<l; ++j) {
            c[i][j] = 0;
        }
    }
    for (int k=0; k<m; ++k) {
        for (int i=0; i<n; ++i) {
            for (int j=0; j<l; ++j) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }

    for (int i=0; i<n; ++i) {
        for (int j=0; j<l; ++j) {
            if (j > 0) {
                printf(" ");
            }
            printf("%ld", c[i][j]);
        }
        printf("\n");
    }

    return 0;
}



Measured memory_bytes: 2148
#include <iostream>

using namespace std;

int dp[3001][3001];
string LCS(string &s,string &t,int len){
    int i=0,j=0,k=0;
    string v;
    while(len>0){
        if(s[i]==t[j]){
            v.push_back(s[i]);
            i++;
            j++;
            
            len--;
        }
        else{
            if(dp[i][j+1]>dp[i+1][j]){
                j++;
            }
            else i++;
        }
    }
    return v;
}
int lenLCS(string &s,string &t,int i,int j){
    if(i>=s.length() ||j>=t.length()){
        return 0;
    }
    if(dp[i][j]!=-1){
        return dp[i][j];
    }
    if(s[i]==t[j]){
        return dp[i][j]=1+lenLCS(s,t,i+1,j+1);
    }
    if(s[i]!=t[j]){
        int ans=max(lenLCS(s,t,i+1,j),lenLCS(s,t,i,j+1));
        return dp[i][j]=ans;
    }
}

int main(){
    for(int i=0;i<3001;i++){
        for(int j=0;j<3001;j++){
            dp[i][j]=-1;
        }
    }
    string s,t;
    cin>>s>>t;
    int len=lenLCS(s,t,0,0);
    string ans=LCS(s,t,len);
    cout<<ans;
}

Measured memory_bytes: 39232
#include <complex>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, lower, upper) for (long long i = lower; i < upper; i++)
#define ALL(list) (list.begin()), (list.end())

using namespace std;
typedef long long ll;
const int MOD = 10000007;

vector<long long> divisor(long long n) {
  vector<long long> ret;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n)
        ret.push_back(n / i);
    }
  }
  return (ret);
}

//--------------------------------

void execute() {
  int a, b;
  cin >> a >> b;
  cout << 6 - a - b << endl;
}

//--------------------------------

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  // cout<<fixed<<setprecision(20);

  execute();

  return (0);
}

Measured memory_bytes: 3136
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    s = [1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51]

    K = int(input())

    print(s[K-1])



main()


Measured memory_bytes: 3064
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>
#include<functional>

using namespace std;
typedef long long int ll;

#define C(I) cout<<(I)<<endl

ll n,m,a,b,c,x,y,z,aa[100010],ba[100010];
bool r,ra,rb,rc;
string s,sa,sb,sc;
char ca,cb,cc;
vector<ll> va,vb,vc;

char amd(char st='a'){
    
    for(int i=0;i<=int('z')+10;i++)aa[i]=0;
    
    for(int i=0;i<s.size();i++){
        if(aa[int(s[i])]==1)return char(0);
        aa[int(s[i])]=1;
        
    }
    m=int(st);
    while(aa[m]==1)m++;
    
    if(m>int('z'))m=0;
    
    return char(m);
    
}


int main(){
    cin>>s;

    if(s=="zyxwvutsrqponmlkjihgfedcba"){
        s="-1";
    }
    else if(s.size()!=26){
        s+=amd();
    }
    else{
        
        do{
            cc=s[s.size()-1];
            //C(char(cc+1));
            s.pop_back();
        }while(int(amd(char(cc+1)))==0);
        s+=amd(char(cc+1));
        /*
        if(amd()!='0')s+=amd();
        else{
            
        }
        */
    }
    
    C(s);
}

Measured memory_bytes: 256
N = gets.to_i
H = gets.split.map(&:to_i)
S = Array.new(N, H[0])
(1 ... N).each do |i|
  S[i] = (H[i] >= S[i - 1] ? H[i] : S[i - 1])
end
puts N.times.count{|i| H[i] == S[i] }



Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll dp[57][57][57 * 57];
int a[57];
int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
    int n, x;
    scanf("%d %d", &n, &x);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            for (int k = 0; k <= 2500; k++)
            {
                if (dp[i][j][k])
                {
                    dp[i + 1][j][k] += dp[i][j][k];
                    dp[i + 1][j + 1][k + a[i + 1]] += dp[i][j][k];
                }
            }
        }
    }
    ll res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += dp[n][i][x * i];
    }
    printf("%lld\n", res);
}

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

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A[i];
    for(int a : A) if(a%2 == 0 && a%3 && a%5){
        cout << "DENIED" << endl;
        return 0;
    }
    cout << "APPROVED" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<utility>
#include<stdio.h>

typedef std::pair<int,int> P;

int main()
{
	std::priority_queue<P> pq;
	int t, a;
	int *ans;

	while( scanf( "%d,%d", &t, &a ), t | a )
		pq.push( std::make_pair( a, t ) );

	ans = new int [pq.size()+1];

	int prev = -1, now = 0;

	while( !pq.empty() )
	{
		P p = pq.top();
		pq.pop();

		if( p.first != prev )
			now++;

		ans[p.second] = now;
		prev = p.first;
	}

	int n;
	while( std::cin >> n )
		std::cout << ans[n] << std::endl;

	delete [] ans;

	return 0;
}

Measured memory_bytes: 1248
//#pragma comment(linker,"/STACK:36777216")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define itoc(c) (char)((int)'0' + c)
#define ctoi(c) (int)(c - '0')
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define emb emplace_back
#define pb push_back

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;

const int oo = 1e9;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;

int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int A, B, C; cin >> A >> B >> C;
  set<int> st;
  st.emplace(A);
  st.emplace(B);
  st.emplace(C);
  if (st.size() == 2) cout << "Yes";
  else cout << "No";
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,k,ans;
struct node{
	int order;
	int i;
}a[100001];
int qpow(int x,int y)
{
	int tmp=1;
	while(y){
		if(y&1)tmp*=x;
		y>>=1;
		x*=x;
	}return tmp;
}
int cmp(node x,node y)
{
	return x.order<y.order;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].order;
		a[i].i = i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)cout<<a[i].i<<" ";
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>

using namespace std;
typedef long long ll;
ll a,b;
int main(){
    scanf("%lld%lld",&a,&b);
    if(a==b&&b==1) {printf("1\n");
    return 0;}
    if(a==1||b==1)printf("%lld", (a*b)-2);
    else printf("%lld", (a*b)-(2*(a+b)-4));
    return 0;
}


Measured memory_bytes: 256
n = int(input())
h = list(map(int,input().split()))

dp=[10**10]*(n+2)

dp[0]=0
dp[1]=0
dp[2]=abs(h[1]-h[0])

for i in range(3,n+1):
  dp[i]=min(dp[i],dp[i-1]+abs(h[i-1]-h[i-2]),dp[i-2]+abs(h[i-1]-h[i-3]))

print(dp[n])

Measured memory_bytes: 52208
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;

bool ok(ll t, ll a, ll b, vl& h) {
  ll add = 0;
  rep(i, h.size()) {
    if (h[i] > b * t) {
      add += ceil((double)(h[i] - b * t) / (a - b));
    }
  }
  return (add <= t);
}

int main() {
  //
  ll n,a,b;
  cin>>n>>a>>b;
  vl h(n);
  ll maxh = 0;
  rep(i,n) {
    cin>>h[i];
    maxh = max(maxh, h[i]);
  }
  ll l = 1, r = maxh / b + 1, m = (l + r) / 2;
  while (r - l > 1) {
    m = (l + r) / 2;
    if (ok(m, a, b, h) == 0) {
      l = m;
    } else {
      r = m;
    }
  }
  if (ok(l, a, b, h)) {
    cout << l << endl;
  } else {
    cout << r << endl;
  }
  return 0;
}


Measured memory_bytes: 1024
N = int(input())
A = list(map(int,input().split()))
dp = [[0 for i in range(N-1)] for j in range(2)]
dp[0][0] = A[0]
dp[1][0] = -A[0]
for i in range(1,N-1):
    dp[0][i] = max(dp[0][i-1]+A[i],dp[1][i-1]-A[i])
    dp[1][i] = max(dp[0][i-1]-A[i],dp[1][i-1]+A[i])
print(max(dp[0][-1]+A[-1],dp[1][-1]-A[-1]))

Measured memory_bytes: 16716
/*input
475254
*/

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int64_t n; cin >> n;
  vector<char> cc;
  while (n > 0) {
    int m = (n - 1) % 26;
    cc.emplace_back(m + 'a');
    n = (n - 1) / 26;
  }

  for (int i = cc.size() - 1; i >= 0; --i) {
    cout << cc[i];
  }

  return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <string>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
	int a,b; cin>>a>>b;
	if((a+b)%2==0) cout << (a+b)/2;
	else cout << "IMPOSSIBLE";

	
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int i,j,c=0;
	long n;
	for(;scanf("%ld",&n)&&n;c=0){
		for(;n-1;){
			if(n%2==0)n/=2;
			else n=n*3+1;
			c++;
		}
		printf("%d\n",c);
	}
	return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> vec_1(N);
    vector<int> vec_2(N);
    rep(i,N){
        cin >> vec_1[i];
    }
    rep(i,N){
        cin >> vec_2[i];
    }
    rep(i,N - 1){
        vec_1[i + 1] += vec_1[i];
    }
    vec_2[0] += vec_1[0];
    for(int i = 1; i < N; i++){
        vec_2[i] += max(vec_2[i - 1], vec_1[i]);
    }
    cout << vec_2[N - 1] << endl;
}


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

const int N = 2e5 + 5;

LL n, ans, a[N], cnt[N];

int main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        ++cnt[a[i]];
    }
	for (int i = 1; i <= n; ++i) ans += 1LL * cnt[i] * (cnt[i] - 1) / 2;
	for (int i = 1; i <= n; ++i)
		printf("%lld\n", ans - cnt[a[i]] + 1);
	return 0;
}


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

using namespace std;

int main()
{

    int n;
    cin >> n;
    for(int i = 1; i <= 9; i ++)
    {
        for(int j = 1; j <= 9; j ++)
        {
            if(i * j == n)
            {
                cout << "Yes\n";
                return 0;
            }
        }
    }

    cout << "No\n";

    return 0;
}


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

const int mod = 998244353;
const int N = 200001;
long long fact[N];
long long binpow(long long a, long long b){
	long long ans = 1;
	while(b>0){
		if (b&1){
			ans = (ans*a) %mod;
		}
		a = (a*a) %mod;
		b = b/2;
	}
	return ans;
}

long long mod_inv(long long n){
	return binpow(n, mod-2);
}

long long ncr (long long n, long long r){
	if (r==0) return 1;
	long long denom = (mod_inv(fact[r])*mod_inv(fact[n-r]))%mod;
	
	return (fact[n]*denom)%mod;
}


int main()
{   
	fact[0] = 1;
	for (int i=1; i<=N; i++){
		fact[i] = (fact[i-1]*i)%mod;
	}
	
	int n, m, K;
	cin>>n>>m>>K;
	long long ans = 0;
	for (int k=0; k<=K; k++){
		ans =  (ans + (binpow(m-1, n-1-k)* (ncr(n-1, k)*m %mod)) %mod) %mod;
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 5212
// ABC058A - 

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;

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

	if (b - a == c - b) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#from collections import defaultdict, deque
#import itertools
#import numpy as np

def main():
    N, K = tuple(int(c) for c in input().split(' '))
    A = [None] + list(int(c) for c in input().split(' '))
    
    memo = {1: 0}
    machi = 1
    k = 0
    while k < K:
        machi = A[machi]
        k += 1
        if not machi in memo:
            memo[machi] = k
        else:
            cycle = k - memo[machi]
            res = (K-k) % cycle
            k = K - res
            #print(machi, K, k, cycle, res)

    print(machi)

if __name__ == "__main__":
    main()

Measured memory_bytes: 32276
#include <iostream>
using namespace std;
int main(void){
    int n, m, l;
    long long t;
    cin>> n >> m >> l;
    int A[n][m], B[m][l];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>A[i][j];
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<l;j++){
            cin>>B[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<l;j++){
            t=0;
            for(int k=0;k<m;k++){
                t+=A[i][k]*B[k][j];
            }
            if(j==0) cout<<t;
            else cout<<" "<<t;
        }
        cout<<endl;
    }
    // Your code here!
    
}



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

int main(){
  int N; cin >> N;
  
  char inp;
  int b,w; b=w=0;
  int count=0;
  for(int i=0; i<N; i++){
    cin >> inp;
    if('.'==inp){
      if(b>0){w++;}
    }
    else{
      if(b>0 && b<w){count=count+b; b=w=0;}
      b++;
    }
  }
  
  cout << count + min(w,b);
  
  return 0;
}

Measured memory_bytes: 256
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

q = []
heapq.heappush(q, (-(a[0] + b[0] + c[0]), 0, 0, 0))
kk = k
ans = []
chk = defaultdict(lambda:defaultdict(lambda:defaultdict(bool)))

while(k):
    k -= 1
    v, ai, bi, ci = heapq.heappop(q)
    ans.append(v)
    if ai + 1 < x:
        if chk[ai + 1][bi][ci] == False:
            heapq.heappush(q, (-(a[ai + 1] + b[bi] + c[ci]), ai + 1, bi, ci))
            chk[ai + 1][bi][ci] = True
    if bi + 1 < y:
        if chk[ai][bi + 1][ci] == False:
            heapq.heappush(q, (-(a[ai] + b[bi + 1] + c[ci]), ai, bi + 1, ci))
            chk[ai][bi + 1][ci] = True
    if ci + 1 < z:
        if chk[ai][bi][ci + 1] == False:
            heapq.heappush(q, (-(a[ai] + b[bi] + c[ci + 1]), ai, bi, ci + 1))
            chk[ai][bi][ci + 1] = True
for i in range(kk):
    print(-ans[i])

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

#define ln "\n"
#define SORT(X) sort(X.begin(), X.end())
#define SORTi(X) sort(X.begin(), X.end(), greater<ll>())
#define REP(x, a, b) for (auto x = a; x <= b; x++)
#define REPi(x, b, a) for (auto x = b; x >= a; x--)
#define REPit(x, A) for (auto x = A.begin(); x != A.end(); x++)
#define REPr(x, A) for (auto x : A)
#define ll long long
#define ull unsigned long long
#define PB push_back
#define EB emplace_back
#define UMP unordered_map
#define UST unordered_set

using namespace std;

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

    string A, B, C;
    cin>>A>>B>>C;
    if(A[A.size()-1] == B[0] && B[B.size()-1] == C[0])
        cout<<"YES"<<ln;
    else
        cout<<"NO"<<ln;
    return 0;
}

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

// 与えられた数以上で最小となる10の倍数を返す関数
int minDeci(int arg) {
  int rem;
  if(arg % 10 == 0) {
    rem = 0;
  }
  else {
  rem = 10 - (arg % 10);
  }
  return (arg + rem);
}

int main() {
  int a,b,c,d,e,k;
  cin >> a >> b >> c >> d >> e;
  vector<int> v = {a, b, c, d, e};
  for(auto &elm : v) {
    elm = minDeci(elm);
  }
  auto sum = accumulate(v.begin(), v.end(), 0);  

  vector<int> w = {a, b, c, d, e};
  for(int i = 0; i < v.size(); ++i) {
    w[i] = v[i] - w[i];
  }
  int minVal = *max_element(w.begin(), w.end());

  cout << sum - *max_element(w.begin(), w.end()) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int i,a,b;
	char op;
	for(i=0;;i++){
	scanf("%d %c %d", &a, &op, &b);
		if ( op == '+' ){
			printf("%d\n",a + b);
		} else if ( op == '-' ){
			printf("%d\n",a - b);
		} else if ( op == '*' ){
			printf("%d\n",a * b);
		} else if ( op == '/' ){
			printf("%d\n",a / b);
		} else if ( op == '?' )break;
		}return 0;
} 

Measured memory_bytes: 600
#include <stdio.h>

int main()
{
    int a1, a2, a3, total;
    scanf("%d%d%d", &a1, &a2, &a3);
    total = a1+a2+a3;
    if(total >= 22)
    {
        printf("bust\n");
    }
    else
    {
        printf("win\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double PI = 4*atan(1);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const string YES = "Possible";
const string NO = "Impossible";
#define pb push_back
#define mp make_pair

int A,B,C,D;

void solve()
{
	bool turn=true;
	while(true){
		if(turn){
			C-=B;
			if(C<=0) break;
			else turn = false;
		}else{
			A-=D;
			if(A <=0)break;
			else turn=true;
		}
	}
	if(turn) cout << "Yes\n";
	else cout << "No\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> A >> B >> C >> D;
	solve();
	return 0;
}

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

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD = 1e9 + 7;

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

	ll ai,ao,at,aj,al,as,az;
	cin>>ai>>ao>>at>>aj>>al>>as>>az;
	ll res=0;
	res+=(ai/2)*4;
	res+=ao*2;
	res+=(aj/2)*4;
	res+=(al/2)*4;

	if(ai&&aj&&al){
		ll tmp=0;
		ai--;aj--;al--;
		tmp+=6;
		tmp+=(ai/2)*4;
		tmp+=ao*2;
		tmp+=(aj/2)*4;
		tmp+=(al/2)*4;

		res=max(res,tmp);
	}
	cout<<res/2<<endl;
}


Measured memory_bytes: 256
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector < int > cnt(n + 1);
    while (m--) {
        int x, y;
        cin >> x >> y;
        cnt[x] ^= 1;
        cnt[y] ^= 1;
    }
    for (int v : cnt) {
        if (v & 1) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}

Measured memory_bytes: 640