akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
S = str(input())

cnt = 0
A = "CODEFESTIVAL2016"

for i in range(len(S)) :
  if S[i] != A[i] :
    cnt += 1
print (cnt)



Measured memory_bytes: 38256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a) = min((a), (b)))
#define chmax(a, b) ((a) = max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const double pi = acos(-1);
const double eps = 1e-10;

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

int n, m;
vector<vector<int>> G(100000);

int s, t;
vector<vector<bool>> visited(100000, vector<bool>(5));

void dijkstra(){
    vector<vector<int>> dist(n, vector<int>(3, 1e9));
    priority_queue<P, vector<P>, greater<P>> que;
    dist[s][0] = 0;
    que.emplace(0, s);

    while(que.size()){
        int ccost, cv;
        tie(ccost, cv) = que.top();
        que.pop();

        if(dist[cv][ccost%3] < ccost) continue;

        for(auto x : G[cv]){
            int nv = x;

            if(dist[cv][(ccost) % 3] + 1 < dist[nv][(ccost + 1) % 3]){
                dist[nv][(ccost + 1) % 3] = dist[cv][(ccost) % 3] + 1;
                que.emplace(dist[nv][(ccost + 1) % 3], nv);
            }

        }
    }

    if(dist[t][0] == 1e9){
        cout << -1 << endl;
    }
    else{
        cout << dist[t][0] / 3 << endl;
    }
}

int main(){
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int u, v; cin>>u>>v;
        u--, v--;
        G[u].emplace_back(v);
    }

    cin>>s>>t;
    s--, t--;

    dijkstra();
}


Measured memory_bytes: 18176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using loop = int;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(loop (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(loop (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(loop (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(loop (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#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()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
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; }
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& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int n; cin >> n;
    VL a(n), b(n);
    FOR(i, 0, n)cin >> a[i] >> b[i];

    ll ans = 0, acc = 0;
    rFOR(i, 0, n) {
        a[i] += acc;
        acc += (b[i] - a[i] % b[i]) % b[i];
        ans += (b[i] - a[i] % b[i]) % b[i];
    }

    cout << ans << "\n";
}

Measured memory_bytes: 1792
N, M = map(int,input().split())
nlike = [0]*M
for n in range(N):
  tmp = list(map(int,input().split()))
  for k in range(1,tmp[0]+1):nlike[tmp[k]-1] +=1
cnt = 0
for m in range(M):
  if nlike[m] == N:cnt += 1
print(cnt)

Measured memory_bytes: 3060
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define VLL vector<long long>
#define SORT(x) sort(x.begin(),x.end())
#define REVE(x) reverse(x.begin(),x.end())
#define rep(i,n) for(int i=0;i<n;i++)
#define COUT(x) cout<<x<<endl
double pai = 3.1415926535;
string atc = "atcoder";
typedef pair<long long, long long> data_t;
string strnum = "0123456789";
string alpS = "abcdefghijklmnopqrstuvwxyz";
string alpL = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int sizealp = (int)(alpS.size());
int mod = 1e9 + 7;
bool test = false;

void Test(char a) {
	if (test) {
		printf("%c", a);
	}
}
int gcd(LL a, LL b) {
	if (a == 0 || b == 0)return 0;
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	else gcd(b, a % b);
}
int main() {
	int N;
	cin >> N;
	VLL a(N);
	rep(i, N)cin >> a[i];
	SORT(a);
	int g = gcd(a[0], a[1]);
	for (int i = 1; i < N; i++) {
		g = gcd(a[i], g);
	}
	COUT(g);
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        void solve(InputReader in, PrintWriter out) {
            // write your code here
            int X = in.nextInt();
            if (X == 3 || X == 5 || X == 7) {
                out.println("YES");
            } else {
                out.println("NO");
            }
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

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

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Measured memory_bytes: 21460
#include <stdio.h>
//#include <stdlib.h>
#include <string.h>
//#include <limits.h>
//#include <math.h>

int main() {
  char s[101], t[101];
  scanf("%s%s", s, t);
  int n = strlen(s);
  for (int i=0; i<n; i++) {
    int j=0;
    while (s[(j+i)%n] == t[j] && j<n) j++;
    if (j==n) {
      printf("Yes\n");
      return 0;
    }
  }
  printf("No\n");
  return 0;
}


Measured memory_bytes: 128
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
	long long int n, x, ans = 0;
	cin>>n;
	x = n;
	while(n != 0)
	{
		ans += n%10;
		n = n/10;
	}
	if(x%ans == 0) printf("Yes\n");
	else printf("No\n");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

int main()
{
  int n;
  cin>>n;
  vecll a(n);
  for(auto&& e:a)cin>>e;
  vecll sum(n+1);
  boost::partial_sum(a, begin(sum)+1);
  vector<vecll> dp(n+1, vecll(n));
  for(auto&& l:irange(2,n+1)) {
    for(auto&& i:irange(0,n)) {
      if (i+l > n) break;
      ll tmp = 1e14;
      for(auto&& k:irange(i+1, i+l)) {
        tmp = min(tmp, dp[k-i][i] + dp[i+l-k][k]);
      }
      tmp += sum[i+l] - sum[i];
      dp[l][i] = tmp;
    }
  }
  cout<<dp[n][0]<<endl;
  return 0;
}


Measured memory_bytes: 1536
// D - Islands War
#include <bits/stdc++.h>
using namespace std;
int V[100000+1];

int in(){int x;scanf("%d",&x);return x;}

int main(){
	int N=in(), M=in();
	while(M--){
		int l=in(), r=in();
		V[r] = max(V[r], l);
	}
	int ans = 0, R = 0;
	for(int r=1; r<=N; ++r)
		if(V[r]>0 && V[r] >= R){ R = r; ans++; }
	cout<< ans <<endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int main(void){
	          int i;

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

	      	  int N,A,B;
	      	  cin >> N >> A >> B;

	      	  int d=B-A+1;
	      	  if(d%2==1) cout << "Alice" << endl;
	      	  else cout << "Borys" << endl;


	          return 0;
}


Measured memory_bytes: 256
n=int(input())
x = list(map(int, input().split()))
val=1
length=range(n)
zflag=0
flag=0
for i in length:
    if x[i]==0:
        zflag=1;
if zflag==1:
    print(0)
else:
    for i in length:
        val=val*x[i];
        if val>1000000000000000000:
            print(-1)
            flag=1
            break
    if flag==0:
        print(val)

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

using namespace std;
int n,i,a[200005];
long long tree[800005],x,sol;
const int mod=1e9+7;
long long querry(int nod,int st,int dr)
{
    if(dr<=a[i])
        return tree[nod];
    else {
        long long mij=(st+dr)>>1,x=0,y=0;
        x=querry(2*nod,st,mij);
        if(mij<a[i])
            y=querry(2*nod+1,mij+1,dr);
        return max(x,y);
    }
}
void update(int nod,int st,int dr)
{
    if(st==dr)tree[nod]=x;
    else {
     int mij=(st+dr)>>1;
     if(mij>=a[i])
     update(2*nod,st,mij);
     if(mij<a[i])
        update(2*nod+1,mij+1,dr);
     //if(nod<=n)
        tree[nod]=max(tree[2*nod],tree[2*nod+1]);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(i=1;i<=n;i++)
    cin>>a[i];
    for(i=1;i<=n;i++)
    {
        cin>>x;
        x+=querry(1,1,n);
        sol=max(sol,x);
        update(1,1,n);
    }
    cout<<sol;
    return 0;
}


Measured memory_bytes: 7168
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define max(x,y)(x>y?x:y)
#define min(x,y)(x>y?y:x)
typedef long long int ll;
typedef unsigned long long int ull;
int asc_cmp(const void* X,const void* Y){int x=*(int*)X,y=*(int*)Y;if(x<y)return -1;else if(x==y)return 0;else return 1;}
int desc_cmp(const void* X,const void* Y){int x=*(int*)X,y=*(int*)Y;if(x<y)return 1;else if(x==y)return 0;else return -1;}

int main(){
    int n;scanf("%d",&n);
    int a[n];for(int i=0;i<n;i++)scanf("%d",&a[i]);
    int b[n];for(int i=0;i<n;i++)scanf("%d",&b[i]);
    int c[n-1];for(int i=0;i<n-1;i++)scanf("%d",&c[i]);

    int ans=0,before;
    ans+=b[a[0]-1];
    before=a[0];
    for(int i=1;i<n;i++){
        ans+=b[a[i]-1];
        if(before+1==a[i])ans+=c[before-1];
        before=a[i];
    }
    printf("%d\n",ans);
}

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

using namespace std;

#define MAX_V 10000

int V,E,cmp[MAX_V];
bool used[MAX_V];
vector<int> G[MAX_V],rG[MAX_V],vs;

void add_edge(int from,int to){
  G[from].push_back(to);
  rG[to].push_back(from);
}

void dfs(int v){
  used[v] = true;
  for(int i = 0 ; i < (int)G[v].size() ; i++){
    if(!used[G[v][i]]){ dfs(G[v][i]); }
  }
  vs.push_back(v);
}

void rdfs(int v,int k){
  used[v] = true;
  cmp[v] = k;
  for(int i = 0 ; i < (int)rG[v].size() ; i++){
    if(!used[rG[v][i]]){ rdfs(rG[v][i],k); }
  }
}

int scc(){
  memset(used,false,sizeof(used));
  vs.clear();
  for(int v = 0 ; v < V ; v++){
    if(!used[v]){ dfs(v); }
  }
  memset(used,false,sizeof(used));
  int k = 0;
  for(int i = vs.size() - 1 ; i >= 0 ; i--){
    if(!used[vs[i]]){ rdfs(vs[i],k++); }
  }
  return k;
}

int main(){
  int u,v,Q;
  cin >> V >> E;
  for(int i = 0 ; i < E ; i++){
    cin >> u >> v;
    add_edge(u,v);
  }
  scc();
  cin >> Q;
  while(Q--){
    cin >> u >> v;
    cout << (cmp[u] == cmp[v]) << endl;
  }
  return 0;
}

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef long long ll;
namespace mp = boost::multiprecision;
using Mint = mp::cpp_int;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = int(a); i < int(b); i++)
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define sort_g(v) sort(all(v), greater<int>())
#define dump(x) cerr << #x << ' ' << '=' << ' ' << x << endl

int sum_digit(int n) {
    int sum = 0;
    while(n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    int N;
    cin >> N;
    int S = sum_digit(N);
    cout << (N % 10 == 0 ? 10 : S) << endl;
}

Measured memory_bytes: 3544
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<utility>
#include<functional>
#include<stack>
#include<queue>
#include<cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef std::pair<int, int> int_pair;
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }


int main() {
	int n = 0, ans = 0;
	int a[100000] = {};
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}

	ans = a[0];

	rep(i, n) {
		ans = gcd(ans, a[i]);
	}

	cout << ans << endl;
}


Measured memory_bytes: 640
object Main {
  def main(args: Array[String]) {
    val input = io.Source.stdin.getLines().mkString("\n");
    println(solve(input).trim());

  }

  def solve(input: String): String = {
    if (input.split(" ").map(_.toInt).product % 2 == 0)"Even" else "Odd"
  }
}

Measured memory_bytes: 25424
while(1):
    M=int(raw_input())
    if M==0:
        break
    else:
        starxy=[]
        constxy=[]
        constdirect=[]
        for i in range(M):
            constxy.append([int(x) for x in raw_input().split()])
        N=int(raw_input())
        for j in range(N):
            starxy.append([int(x) for x in raw_input().split()])
        for i in range(1,M):
            constdirect.append([constxy[i][0]-constxy[0][0],constxy[i][1]-constxy[0][1]])
        const0=constxy[0]
        for star in starxy:
            fin=1
            for nextvector in constdirect:
                if not [star[0]+nextvector[0],star[1]+nextvector[1]] in starxy:
                    fin=0
                    break
            if fin:
                print star[0]-const0[0],star[1]-const0[1]
                break

Measured memory_bytes: 4432
import sys
n = int(input())
ls = []
for i in range(n):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    ls.append([a, b])
_sum = 0
for a, b in ls[::-1]:
    if (a + _sum) % b:
        _sum += (b - (a + _sum) % b)
print(_sum)

Measured memory_bytes: 20340
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def resolve():
    readline=sys.stdin.readline
    mod=10**9+7
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    ans = 0
    x = 1
    for i in range(60):
        c = 0
        for j in range(n):
            if arr[j]&x != 0:
                c += 1
        ans += (c * (n-c)) * x
        ans %= mod
        x = x*2
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Measured memory_bytes: 58028
class BIT_2D():
    def __init__(self,h,w):
        self.h=h
        self.w=w 
        self.table=[[0]*(w+1) for _ in range(h+1)]

    def add(self,i,j,x):
        init_j=j
        while i<=self.h:
            while j<=self.w:
                self.table[i][j]+=x
                j+=(j&-j)
            j=init_j
            i+=(i&-i)
        return None

    def sum(self,i,j):
        s=0
        init_j=j
        while i>0:
            while j>0:
                s+=self.table[i][j]
                j-=(j&-j)
            j=init_j
            i-=(i&-i)
        return s
      
n,m,q=map(int,input().split())
bit2d=BIT_2D(n,n)
for i in range(m):
  i,j=map(int,input().split())
  bit2d.add(i,j,1)
for i in range(q):
  i,j=map(int,input().split())
  ans=bit2d.sum(j,j)-bit2d.sum(j,i-1)-bit2d.sum(i-1,j)+bit2d.sum(i-1,i-1)
  print(ans)

Measured memory_bytes: 61016
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// K, Xの入力
		int K = sc.nextInt();
		int X = sc.nextInt();
		
		// startとendの判定
		int start = Math.max(X-K+1, -1000000);
		int end = Math.min(X+K-1, 1000000);
		
		// 結果の出力
		for (int i = start; i <= end; i++) {
			System.out.print(i + " ");
		}
		
		sc.close();
	}

}


Measured memory_bytes: 23124
class Dice:
    def __init__(self):
        self.number = [0]*6
        self.work = [0]*6
        
    def setNumber(self,n0,n1,n2,n3,n4,n5): #Diceの面に与えられた引数の値をセット
        self.number[0] = n0
        self.number[1] = n1
        self.number[2] = n2
        self.number[3] = n3
        self.number[4] = n4
        self.number[5] = n5
    
    def lotate(self,st):
        for i in range(len(self.number)):
            self.work[i] = self.number[i]  
        if st == 'E':
            self.setNumber(self.work[3],self.work[1],self.work[0],self.work[5],self.work[4],self.work[2])
        if st == 'N':
            self.setNumber(self.work[1],self.work[5],self.work[2],self.work[3],self.work[0],self.work[4])
        if st == 'W':
            self.setNumber(self.work[2],self.work[1],self.work[5],self.work[0],self.work[4],self.work[3])
        if st == 'S':
            self.setNumber(self.work[4],self.work[0],self.work[2],self.work[3],self.work[5],self.work[1])

    def top(self):
        return self.number[0]
    


s = list(map(int,input().split()))

dice = Dice()
dice.setNumber(s[0],s[1],s[2],s[3],s[4],s[5])

request = input()       #命令の入力
for w in request:       #命令の実行
    dice.lotate(w)

result = dice.top()
print(result)





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

using namespace std;

typedef long long ll;

const long long MOD = 1e9 + 7;
const int INF = 1e9;

int main() {
  int N, M;
  cin >> N >> M;
  vector<bool> flag1(N, false), flag2(N, false);
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    if (a == 1) flag1[b - 1] = true;
    if (b == N) flag2[a - 1] = true;
  }
  bool ok = false;
  for (int i = 0; i < N; ++i) {
    if (flag1[i] && flag2[i]) {
      ok = true;
      break;
    }
  }
  cout << (ok ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

int main(){
    int W,H,N; cin>>W>>H>>N;
    vector<tuple<int,int,int>> Dot(N);
    rep(n,0,N){
        int x,y,a; cin>>x>>y>>a;
        Dot.at(n)=make_tuple(x,y,a);
    }

    vector<pair<int,int>> vertex{make_pair(0,0),make_pair(W,H)};
    for(auto d:Dot){
        int x,y,a;
        tie(x,y,a)=d;

        if(a==1){
            vertex.at(0).first=max(vertex.at(0).first,x);
        }else if(a==2){
            vertex.at(1).first=min(vertex.at(1).first,x);
        }else if(a==3){
            vertex.at(0).second=max(vertex.at(0).second,y);
        }else{
            vertex.at(1).second=min(vertex.at(1).second,y);
        }
    }

    int ans=0;
    if(vertex.at(0)<vertex.at(1)){
        ans=(vertex.at(1).first-vertex.at(0).first)*(vertex.at(1).second-vertex.at(0).second);
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>
int main(){
 long long n,k;
 scanf("%lld%lld",&n,&k);

 long long a[n];
 long long b;
 for(b=0;b<n;b++)
  scanf("%lld",&a[b]);

 long long memo[n+1],j=0,ok=0,m=k;
 long long point=1,cnt=0,ans=1,i;
 memo[1]=0;
  
 for(i=2;i<=n;i++)
   memo[i]=k+1;
  
 for(i=1;i<=k;i++){
  ok=0;
  point=a[point-1];
 // printf("point %lld\n",point);
  if(memo[point]!=k+1){
  // printf("%lld %lld %lld\n",point,i,memo[point]);
   j=memo[point];
   k=(k-j)%(-j+i);
 // printf("j %lld k %lld\n",j,k);
   ok=1;break;
  }
  if(ok)break;
  memo[point]=i;
 // printf("memo[point] %lld\n",memo[point]);
 }

 for(i=1;i<=j+k;i++)
   ans=a[ans-1];

 printf("%lld\n",ans);

return 0;}

Measured memory_bytes: 4856
#pragma GCC optimize(2)
#include <bits/stdc++.h>

// Defination {{{
#define PI pair<int, int>
#define mk make_pair
#define reg register
#define ll long long
#define rep(i, a, b) for(reg int i = a; i <= b; ++i)
#define per(i, a, b) for(reg int i = a; i >= b; --i)
#define pb push_back
// }}}

using namespace std;

int min(reg int a, reg int b) { return a < b ? a : b; }
int max(reg int a, reg int b) { return a > b ? a : b; }

template<typename T> void read(T &x) {
    x = 0; reg char ch = getchar(); reg int f = 1;
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') ch = getchar();
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= f;
}

#define N 100005

char s[N], t[N];
vector<int> pos[50];

int main() {
    scanf ("%s", s + 1);
    scanf ("%s", t + 1);
    int lens = strlen(s + 1), lent = strlen(t + 1);
    rep (i, 1, lens) {
        pos[s[i] - 'a' + 1].push_back(i);
    }
    rep (i, 1, 26) pos[i].push_back(lens + 1);
    int now = 0;
    ll len = 0;
    rep (i, 1, lent) {
        int id = t[i] - 'a' + 1;
        now = *lower_bound(pos[id].begin(), pos[id].end(), now + 1);
        if (now == lens + 1) {
            now = 0;
            now = *lower_bound(pos[id].begin(), pos[id].end(), now + 1);
            if (now == lens + 1) {
                puts("-1");
                return 0;
            }
            len += lens;
        }
    }
    len += now;
    cout << len << endl;
    return 0;
}

/*
 _____  ____    _____
|__  / |  _ \  |__  /
  / /  | |_) |   / /
 / /_  |  _ <   / /_
/____| |_| \_\ /____|

 _____________________________________
< E.cpp is created by zrz who is weak >
 -------------------------------------
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||
*/


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

ll func(ll num, ll x){

    if(num >= 0){
        return num / x + 1;
    }
    else return 0;
}

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

    ll a, b, x;
    cin >> a >> b >> x;

    cout << func(b, x) - func(a - 1, x) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b; cin >>a >>b;
  int tmp;
  if(b/100>0) tmp=1000;
  else if(b/10) tmp=100;
  else tmp=10;
  int x;
  x=a*tmp+b;
  //cout <<x <<endl;
  tmp=sqrt(x);
  //cout <<tmp <<endl;
  if(x==tmp*tmp) cout <<"Yes" <<endl;
  else cout <<"No" <<endl;
}

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

s = input()

cnt = 0
f = s[0]
for i in range(1, n):
    l = s[i]
    if l == f:
        continue
    else:
        f = l
        cnt +=1

minus = max(cnt-2*k, 0)

ans = n - 1 - minus

print(ans)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define int long long
#define maxn 10000005
#define inf 2000000000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
const double PI = acos(-1);
using namespace std;

string s,t,ls; int n,m;
int hs[maxn]; int fmul[maxn];
int base = 31;
int Hash (int l, int r){
	//cout<<l<<' '<<r<<'\n';
	int val = hs[r]-hs[l-1]*fmul[r-l+1];
	val%=mod; val=(val+mod)%mod;
	return val;
}
bool ok (int x){
	string lt; int i,j;
	if (m*x > ls.size()) return false;
	for (i=1;i<=x;i++){
		lt+=t;
	}
	int hlt=0;
	for (i=0;i<lt.size();i++){
		hlt=hlt*base+lt[i]-96; hlt%=mod;
	}
	for (i=0;i<=ls.size()-lt.size();i++){
		int val = Hash(i,i+lt.size()-1);
		if (val==hlt) return true;
	}
	return false;
}
int binsTnum(int lo,int hi){
	int daps=0;
	while (lo<=hi){
		int mid=(lo+hi)/2;
		if (ok(mid)){
			daps=max(daps,mid);
			lo=mid+1;
		}
		else hi=mid-1;
	}
	return daps;
}

main(){
	ios::sync_with_stdio(false); cin.tie(0); srand(time(NULL));
	//freopen("inp.txt","r",stdin); //freopen("out.txt","w",stdout);
	//freopen(".inp","r",stdin); freopen(".out","w",stdout);
	cin>>s>>t; n=s.size(); m=t.size();
	int i,j,k;
	ls = s+s+s;
	while (ls.size()<=t.size()) ls+=s;
	fmul[0]=1; for(i=1;i<maxn;i++) fmul[i]=(fmul[i-1]*base)%mod;
	
	hs[0]=ls[0]-96;
	for (i=1;i<ls.size();i++){
		hs[i]=hs[i-1]*base+ls[i]-96;
		hs[i]%=mod;
	}
	int ans1= binsTnum(1,ls.size());
	ls=ls+ls;
	hs[0]=ls[0]-96;
	for (i=1;i<ls.size();i++){
		hs[i]=hs[i-1]*base+ls[i]-96;
		hs[i]%=mod;
	}
	int ans2=binsTnum(1,ls.size());
	//cout<<ans1<<' '<<ans2<<'\n';
	if (ans1==ans2){
		cout<<ans1; return 0;
	}
	else{
		cout<<-1; return 0;
	}
	
	
}

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

typedef long long ll;
 
int main(int argc, char const *argv[])
{
	int n,k;
	cin >> n >> k;
	vector<ll> a;
	a.resize(n);
	for(int i=0; i<n; i++) cin >> a[i];

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

	ll mininum = a[n-1]-a[0];
	for(int i=0; i<n-k+1; i++){
		if((a[i+k-1]-a[i]) < mininum) mininum = (a[i+k-1]-a[i]);
	}
	cout << mininum << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int bit[200000], n;
int query(int a)
{
	int ans = 0;
	while (a)
	{
		ans+=bit[a];
		a-=a&-a;
	}
	return ans;
}
void update(int a, int val)
{
	while (a <= n)
	{
		bit[a]+=val;
		a+=a&-a;
	}
}
pair<int, pair<int, int> > lines[100010];
void sor(ld x, int* ordering, bool first = false)
{
	pair<ld, int> ord[100010];
	for (int i = 1; i <= n; i++)
	{
		ord[i].first = ((ld)lines[i].first/-lines[i].second.first)*x + lines[i].second.second/(ld)lines[i].second.first;
		ord[i].second = i;
	}
	sort(ord+1, ord+n+1);
	if (first)
	{
		for (int i = 1; i <= n; i++)
	{
		ordering[i] = ord[i].second;
	}
	return;
	}
	for (int i = 1; i <= n; i++)
	{
		ordering[ord[i].second] = i;
	}
}
int original[100010];
int _new[100010];
ld findcoord()
{
	sor(-99999999999999.9, original, true);
	ll n22 = (n*((ll)n-1))/2;
	ll n2  = n22/2;
	if (n22 % 2) n2++;
	ld s = -999999999;
	ld e = 999999999;
	/*for (int i = 1; i <= n; i++)
	{
		printf("%d ", original[i]);
	}
	printf("\n");*/
	while (abs(s-e) > 0.000000001)
	{
		ld mid = (s+e)/2;
		sor(mid, _new);
		fill_n(bit, 100010, 0);
		for (int i = 1; i <= n; i++)
		{
			update(i, 1);
		}
		ll ans = 0;
		for (int i = 1; i <= n; i++)
		{	
			ans+=query(_new[original[i]])-1;
		//	printf(" %d %d %d\n", original[i], _new[original[i]], ans);
			update(_new[original[i]], -1);
		}
	//	printf("%d %Lf\n", ans, mid);
		if (ans >= n2) e = mid;
		else s = mid;
	//	break;
	}
	return s;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d %d", &lines[i].first, &lines[i].second.first, &lines[i].second.second);
	}
	ld x = findcoord();
	for (int i = 1; i <= n; i++)
	{
		swap(lines[i].first, lines[i].second.first);
	}
	ld y = findcoord();
	printf("%.10Lf %.10Lf\n", x, y);
}

Measured memory_bytes: 4608
import java.io.*;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/10;
    public static final int inf = Integer.MAX_VALUE/10;

    static void solve(InputReader in, PrintWriter out){
        int n = in.ni();
        long sum = 0;
        int[] num = new int[200001];
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            int a = in.ni();
            arr[i] = a;
            num[a] += 1;
            sum += num[a]-1;
        }
        for (int i = 0; i < n; i++) {
            out.println(sum-num[arr[i]]+1);
        }
    }


    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 50060
main = do
    (n:_) <- map read . words <$> getLine
    d <- filter (/=' ') <$> getLine
    print . head $ dropWhile (d `notElems`) [n..]

notElems :: String -> Int -> Bool
notElems a b = not . and  $ a >>= \x -> map (x/=) (show b)

Measured memory_bytes: 1020
#include<iostream>
#include <vector> 
#include <algorithm>
#include<iomanip>
#include<math.h>
#include<string>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
using namespace std;
struct Room {
	int *a;
	int shortest;
	int way;
	int ways;
};
//for (int x = 0; x < N; x++)room[x].a=(int*)malloc(room[x].way * sizeof(int));
int main() {
	static long long X, Y;
	cin >> X >> Y;
	if (Y % 2 == 1) {
		cout << "No" << endl;
		return 0;
	}
	if ((2 * X) - (Y / 2) < 0) {
		cout << "No" << endl;
		return 0;
	}
	if ((Y / 2) - X < 0) {
		cout << "No" << endl;
		return 0;
	}if ((2 * X) - (Y / 2) == 0 && (Y / 2) - X == 0) {
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	return 0;
}

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

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

    vector<int> dp(S.size()+1);

    dp.at(0) = 0;
    int ans = 0;

    for(int i = 1; i <= S.size(); i++)
    {
        if(S.at(i-1) == 'A' || S.at(i-1) == 'T' || S.at(i-1) == 'C' || S.at(i-1) == 'G'){
            dp.at(i) = dp.at(i-1) +1;
        }
        else dp.at(i) = 0;

        if(dp.at(i) > ans)ans = dp.at(i);
    }

    cout << ans << endl;
    
}

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

#define ll long long
#define ar array


void solve(){
    string s;
    cin >> s;
    int a = 0, b = 0;
    for(int i = 0; i < 3; ++i){
        if(s.at(i) == 'A'){
            a++;
        } else {
            b ++;
        }
    }
    if(a > 0 && b > 0){
        cout << "Yes" << endl;
    } else{
        cout << "No" << endl;
    }
}

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


Measured memory_bytes: 256
// AOJ 0635 Snake JOI
// 2018.2.15 bal4u

#include <stdio.h>

typedef unsigned char uchar;

#define QMAX 3000
typedef struct { int t, s; uchar b, x; } QUE;
QUE que[QMAX]; int qsize;

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

void min_heapify(int i)
{
	int l, r, min;
	QUE qt;

	l = LEFT(i), r = RIGHT(i);
	if (l < qsize && que[l].t < que[i].t) min = l; else min = i;
	if (r < qsize && que[r].t < que[min].t) min = r;
	if (min != i) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		min_heapify(min);
	}
}

void deq()
{
	que[0] = que[--qsize];
	min_heapify(0);
}

void enq(int s, int t, uchar b, uchar x)
{
	int i, min;
	QUE qt;

	i = qsize++;
	que[i].s = s, que[i].t = t, que[i].b = b, que[i].x = x;
	while (i > 0 && que[min = PARENT(i)].t > que[i].t) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		i = min;
	}
}

uchar t[10002];
int to[10002][20]; uchar d[10002][20]; short hi[10002];
char mk[10002][3][201];

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

int dijkstra(int start, int goal, int X)
{
	int i, u, v, c, e;
	unsigned char b, x;

	qsize = 0;
	enq(start, 0, 1, X);		// t[0] = 1
	while (qsize) {
		u = que[0].s, c = que[0].t, b = que[0].b, x = que[0].x, deq();
		if (u == goal) break;

		if (mk[u][b][x]) continue;
		mk[u][b][x] = 1;

		for (i = 0; i < hi[u]; i++) {
			v = to[u][i], e = d[u][i];
			if ((b | t[v]) == 3 && e < x) continue;

			if (t[v] > 0) {
				if (!mk[v][t[v]][X]) enq(v, c+d[u][i], t[v], X);
			} else {
				int k = (int)x- e; if (k < 0) k = 0;
				if (!mk[v][b][k]) enq(v, c+d[u][i], b, k);
			}
		}
	}
	return c;
}

int main()
{
	int N, M, X, i, a, b, c;

	N = in(), M = in(), X = in();

	for (i = 0; i < N; i++) {
		a = getchar_unlocked() & 3; if (a < 2) a = !a;
		t[i] = a;			// 0:快適, 1:寒, 2:暑. 
		getchar_unlocked();
	}

	while (M--) {
		a = in()-1, b = in()-1, c = in();
		i = hi[a]++, to[a][i] = b, d[a][i] = c;
		i = hi[b]++, to[b][i] = a, d[b][i] = c;
	}

	printf("%d\n", dijkstra(0, N-1, X));
	return 0;
}


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

bool prime[10000005];
vector < int > yotsugo;

int main()
{
    int N;
    fill_n(prime, 10000005, true);

    for ( int i = 2; i < 3335; i++ ) {
        if ( prime[i] ) {
            for ( int j = i * i; j < 10000005; j += i ) {
                prime[j] = false;
            }
        }
    }
    for ( int i = 5; i <= 10000000 - 8; i++ ) {
        if ( prime[i] && prime[i + 2] && prime[i + 6] && prime[i + 8] ) {
            yotsugo.push_back(i + 8);
        }
    }

    while ( cin >> N , N != 0 ) {
        cout << *(upper_bound(yotsugo.begin(), yotsugo.end(), N) - 1) << endl;
    }

    return ( 0 );
}



Measured memory_bytes: 12936
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repr(i, a, b) for (int i = a; i >= b; i--)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (a).size()
#define pb(a) push_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define mp(a, b) make_pair(a, b)
#define mt(...) make_tuple(__VA_ARGS__)
using namespace std;
using pii = pair<int, int>;
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr double EPS = 1e-10;

int calc(int x) {
  int r = 0;
  while (x) {
    r += x % 10;
    x /= 10;
  }
  return r;
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int N;
  cin >> N;
  int ans = INF;
  rep(i, 1, N) {
    ans = min(ans, calc(i) + calc(N-i));
  }
  cout << ans << endl;

  return 0;
}

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

using namespace std;
const int maxn=1e5+5;
int book[maxn];
int h[maxn];
vector<int>edg[maxn];
int main()
{
    int a, b, n, m;
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int l, x;
        scanf("%d", &l);
        for(int j=0; j<l; j++)
        {
            scanf("%d", &x);
            book[x]++;
        }
    }
    int ans=0;
    for(int i=1; i<=n; i++)ans+=(book[i]==0);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 6108
import sys
stdin = sys.stdin
 
mod = 10**9 + 7
 
def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))
 
def main():
    n = ni()
    a = na()
    ans = 0
    for i in range(61):
        cnt = 0
        for ai in a:
            if (ai >> i) & 1:
                cnt += 1
        ans += ((cnt * (n - cnt)) * 2**i) % mod
    ans %= mod
    print(ans)
 
 
if __name__ == "__main__":
    main()

Measured memory_bytes: 50848
import java.util.Scanner;

public class Main {
    static long dp[][] = new long[100010][3];
    
    public static void main(String[] args) {
        Scanner std = new Scanner(System.in);
        int n = std.nextInt();

        int[][] a = new int[n][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                a[i][j] = std.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    // prohibit 2 days
                    if (j == k) {
                        continue;
                    }
                    dp[i + 1][k] = Math.max(dp[i + 1][k], dp[i][j] + a[i][j]);
                }
            }
        }
        
        long ans = 0;
        for (int i = 0; i < 3; i++) {
            ans = Math.max(dp[n][i], ans); 
        }
        
        System.out.println(ans);
    }
}


Measured memory_bytes: 101768
import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int K = sc.nextInt();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length() - 1; ++i) {
            char cur = str.charAt(i);
            if (cur != 'a') {
                int ops = 'z' - cur + 1;
                if (ops <= K) {
                    K -= ops;
                    sb.append('a');
                } else {
                    sb.append(cur);
                }
            } else {
                sb.append('a');
            }
        }

        char last = str.charAt(str.length() - 1);
        while (K > 0) {
            last++;
            if (last > 'z') {
                last = 'a';
            }
            K--;
        }
        sb.append(last);
        System.out.println(sb.toString());
    }
}

Measured memory_bytes: 15300
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(a){return a?cin[cid++]:+cin[cid++];}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var mod = 998244353;
function mul(){for(var a=arguments,r=a[0],i=a.length;--i;)r=((r>>16)*a[i]%mod*65536+(r&65535)*a[i])%mod;return r;}
var fac=[],finv=[],invs=[],pow2=[];
function fset(n){
  fac.length=n+1,fac[0]=fac[1]=1;
  for(var i=2;i<=n;)fac[i]=mul(fac[i-1],i++);
  finv.length=n+1,finv[0]=finv[1]=1,finv[n]=inv(fac[n]);
  for(i=n;2<i;)finv[i-1]=mul(finv[i],i--);
  //invs.length=n+1,invs[0]=invs[1]=1;
  //for(i=2;i<=n;)invs[i]=mul(fac[i-1],finv[i++]);
  //pow2.length=n+1,pow2[0]=1;
  //for(i=1;i<=n;i++)pow2[i]=pow2[i-1]*2%mod;
}
function inv(b){for(var a=mod,u=0,v=1,t;b;v=t)t=a/b|0,a-=t*b,u-=t*v,t=a,a=b,b=t,t=u,u=v;u%=mod;return u<0?u+mod:u;}
function pow(a,n){for(var r=1;n;a=mul(a,a),n>>=1)if(n&1)r=mul(a,r);return r;}
function ncr(n,r){return mul(fac[n],finv[r],finv[n-r]);}
function npr(n,r){return mul(fac[n],finv[r]);}
function mput(n){return (n%mod+mod)%mod;}

var myOut = main();
if(myOut !== undefined)console.log(myOut);

function main(){
  var [n,m,k] = nexts(3);
  if(m === 1){
    return k === n-1 ? 1 : 0;
  }
  var kx = m;
  var invm = inv(m-1);
  for(var i = 1; i < n; i++)kx = mul(kx,m-1);
  var ans = kx;
  fset(n);
  for(var i = 1; i <= k; i++){
    kx = mul(kx,invm);
    var ki = mul(kx,ncr(n-1,i));
    ans += ki;
  }
  return mput(ans);
}

Measured memory_bytes: 43428
#include <iostream>
#include <string>

int main()
{
    int n;
    std::cin >> n;
    std::string s, t;
    std::cin >> s >> t;
    std::size_t index = 0;
    for(std::size_t i = 0; i != t.length(); ++i)
    {
        if(t[index] == s[i])
        {
            ++index;
        }
        else
        {
            i -= index;
            index = 0;
        }
    }
    std::cout << s.length() + t.substr(index).length() << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,l,n) for(ll i=l;i<n;i++)
#define E "\n"
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll fact[1000001];
void fac()
{
    fact[0]=1;
    f(i,1,1000001)
    {
        fact[i]=fact[i-1]*i;
    }
}

ll ncr(ll n,ll r)
{
    return fact[n]/(fact[r]*fact[n-r]);
}


int main() {
	fast;
	ll n;
	cin>>n;
	ll a[n],b[n];
	f(i,0,n) cin>>a[i],b[i]=a[i];
	sort(b,b+n);
	f(i,0,n)
	{
		if(a[i]==b[n-1]) cout<<b[n-2]<<E;
		else cout<<b[n-1]<<E;
	}
	
}


Measured memory_bytes: 4736
// E.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> dp[2];

void update(int a, int b) {
	vector<int> v = { dp[0][a], dp[1][a], dp[0][b], dp[1][b] };
	sort(v.rbegin(), v.rend());
	dp[0][a] = v[0];
	dp[1][a] = v[1];
}

int main(int argc, char *argv[])
{
	int n;
	cin >> n;
	int bm = 1 << n;
	dp[0].resize(bm);
	dp[1].resize(bm);
	for (int i = 0; i < bm; ++i) {
		cin >> dp[0][i];
	}
	for (int i = 1; i < bm; i <<= 1) {
		for (int j = 0; j < bm; ++j) {
			if (j & i) {
				update(j, j ^ i);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i < bm; ++i) {
		ans = max(ans, dp[0][i] + dp[1][i]);
		cout << ans << endl;
	}
}


Measured memory_bytes: 5120
///                    بِسْمِ ٱللَّٰهِ ٱلرَّحْمَٰنِ ٱلرَّحِيمِ
///                   لآ اِلَهَ اِلّا اللّهُ مُحَمَّدٌ رَسُوُل اللّهِ




#include <bits/stdc++.h>

using namespace std;
#define endl "\n"

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

    if(x % 10 == 3) cout << "bon" << endl;
    else if(x%10== 0||x%10== 1||x%10== 6||x%10==8) cout << "pon" << endl;
    else cout << "hon" << endl;



	return 0;
}



Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

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

    int n;
    cin >> n;
    VI v;
    v.resize(n);
    rep(i, 0, n) cin >> v[i];
    sort(all(v));
    reverse(all(v));

    ll cnt = v.front();
    rep(i, 2, n) {
        cnt += (ll)v[i / 2];
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acosl(-1);

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

    string S;
    cin >> S;
    if (S.back() == 's') {
        S.push_back('e');
        S.push_back('s');
    } else
        S.push_back('s');
    cout << S << endl;

    return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
typedef pair<ll,ll> pll;

#define reps(i,f,n) for(int i = int(f); i <= int(n); i++)
#define rep(i,n) reps(i,0,int(n)-1)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)

#define all(x) (x).begin(),(x).end()
#define X first
#define Y second

#define sz size()
#define eb emplace_back

int s[1024];

int main(void){
  int n;
  reps(i,1,999){
    int sum = i;
    reps(j,i+1,1000){
      sum += j;
      if( sum > 1000)break;
      s[sum]++;
    }
  }

  while(cin >> n,n){
    cout << s[n] << endl;
  }


  return 0;
}

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

int main() {
    int x, tem, ans;
    cin >> x;
    
    ans = 1;
    for ( int i = 2; i <= x ; i++ ) {
        tem = i * i;
        while ( tem <= x ) {
            ans = max(ans, tem);
            tem *= i;
        }
    } 
    
    cout << ans << endl;
    
    return (0);
}

Measured memory_bytes: 3596
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
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; }
const long long INF = 1LL << 60;
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 1000000007
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

int main(){
    ll n,ans=0;
    cin >> n;
    ll a[n],s[n+1];
    for (ll i=0;i<n;i++){
        cin >> a[i];
    }
    s[0]=0;
    for (ll i=1;i<=n;i++){
        s[i]=s[i-1]+a[i-1];
    }
    sort(s,s+n+1);
    ll count=1;
    for (ll i=1;i<n+1;i++){
        if (s[i]==s[i-1])count++;
        else{
            ans+=(count*(count-1))/2;
            count=1;
        }
    }
    ans+=(count*(count-1))/2;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3328