akhauriyash/Code-Regression huggingface dataset:
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<unordered_set>
#include<vector>

#define ll long long
#define P pair<int,int>
#define FOR(i,N) for(int i=0;i<(int)N;i++)
#define FORIN(i,a,b) for(int i=a;i<(int)b;i++)
#define ALL(x) (x).begin(),(x).end()
#define LAST(x) (x)[(x).size()-1]
#define GI(name) int (name);scanf("%d",&(name))
#define GI2(name1,name2) int (name1),(name2);scanf("%d %d",&(name1),&(name2))
#define GI3(name1,name2,name3) int (name1),(name2),(name3);scanf("%d %d %d",&(name1),&(name2),&(name3))
#define GVI(name,size) vector<int> (name)(size);FOR(i,(size))scanf("%d",&(name)[i])
#define MOD 1000000007

using namespace std;

string to_hex(int x){
    stringstream ss;
    ss<<hex<<x;
    return ss.str();
}

inline int get_int(){
    int ret;
    scanf("%d",&ret);
    return ret;
}

inline vector<int> get_ints(int n){
    vector<int> ret(n);
    FOR(i,n){
        scanf("%d",&ret[i]);
    }
    return ret;
}

inline string get_str(){
    string ret;
    cin>>ret;
    return ret;
}

bool is_prime(int n){
    int s=sqrt(n)+1;
    for(int i=2;i<=s;++i){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

vector<P> prime_division(int n){
    vector<P> ret;
    int s=sqrt(n)+1;
    int c=0;
    for(int i=2;i<=n;++i){
        if(n%i==0){
            c=0;
            do{
                ++c;
                n/=i;
            }while(n%i==0);
            ret.push_back(P(i,c));
        }
    }
    return ret;
}

struct UnionFind{
    vector<int> data;
    UnionFind(int size){
        data=vector<int>(size,-1);
    }
    bool union_set(int x,int y){
        x=root(x);
        y=root(y);
        if(x!=y){
            if(data[y]<data[x])swap(x,y);
            data[x]+=data[y];
            data[y]=x;
        }
        return x!=y;
    }
    bool find(int x,int y){
        return root(x)==root(y);
    }
    int root(int x){
        return data[x]<0?x:data[x]=root(data[x]);
    }
    int size(int x){
        return -data[root(x)];
    }
};

string to_string(string s){
    return s;
}

template<class T>
string to_string(vector<T> v){
    string ret="{";
    FOR(i,v.size()-1){
        ret+=to_string(v[i])+",";
    }
    if(v.size()>0){
        ret+=to_string(LAST(v));
    }
    ret+="}";
    return ret;
}

void debug_print(){
    cerr<<endl;
}

template<class Head,class... Tail>
void debug_print(Head head,Tail... tail){
    cerr<<to_string(head)<<" ";
    debug_print(tail...);
}

template<class... T>
void debug(T... args){
    cerr<<"["<<__LINE__<<"]: ";
    debug_print(args...);
}

void print(){
    cout<<endl;
}

template<class Head,class... Tail>
void print(Head head,Tail... tail){
    cout<<to_string(head);
    print(tail...);
}

int main(){
    GI(N);
    vector<ll> dp(N,0);
    GVI(h,N);
    dp[1]=dp[0]+abs(h[0]-h[1]);
    FORIN(i,1,N){
        dp[i]=min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]));
    }
    print(dp[N-1]);
    return 0;
}

Measured memory_bytes: 1408
# しゃくとり
# ref. https://atcoder.jp/contests/abc124/submissions/4962905
N, K = map(int, input().split())
S = map(int, list(input()))

num_list = []
now = 1
count = 0

for char in S:
    if char == (0 + now):
        count += 1
    else:
        num_list.append(count)
        now = 1 - now
        count = 1
if count > 0:
    num_list.append(count)
# 1-0-1-0になっていたら、最後に1つ0を足す
if len(num_list) % 2 == 0:
    num_list.append(0)

ans = 0
add = 2 * K + 1

left = 0
right = 0
tmp = 0 # [left, right)のsum
for i in range(0, len(num_list), 2):
    next_left = i
    next_right = min(i + add, len(num_list))

    while left < next_left:
        tmp -= num_list[left]
        left += 1
    while right < next_right:
        tmp += num_list[right]
        right += 1
    ans = max(ans, tmp)
print(ans)


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


int main()
{
	std::string s;

	std::cin >> s;

	long long a = 10000000000, z = 0;
	for (long long i = 0; i < s.length(); i++) {
		if (s[i] == 'A') {
			a = std::min(a, i);
		} else if (s[i] == 'Z') {
			z = std::max(z, i);
		}
	}
	std::cout << z - a + 1 << std::endl;
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <math.h>
#include <string.h>
#define pai 3.1415926535

int main(void) {
	int N, K;
	scanf("%d%d", &N, &K);
	int l[50];
	int a;
	int count = 0;
	int sum = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &l[i]);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N - 1 - i; j++) {
			if (l[j] > l[j + 1]) {
				a = l[j];
				l[j] = l[j + 1];
				l[j + 1] = a;
			}
		}
	}
	for (int i = N - 1; count < K; i--) {
		sum += l[i];
		count++;
	}
	printf("%d", sum);

	return 0;

}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=1234567;
const ll INF=1000000010;
const ll LINF=4000000000000000010LL;
const int MAX=200010;
const double EPS=1e-3;
int dx[4]={0,1,0,1};
int dy[4]={0,0,1,1};
int main(){
	int n,m;cin>>n>>m;
	int a[100010];for(int i=1;i<=n;i++)cin>>a[i];
	ll sum[250000]={};
	ll ans=0;
	for(int i=1;i<n;i++){
		int l=a[i];int r=a[i+1];
		if(l>=r){
			r+=m;
		}
		ans+=r-l;
		sum[l+1]--;
		sum[r]+=r-l;
		sum[r+1]-=r-l-1;
	}
	for(int i=1;i<=2*m+1;i++){
		sum[i]+=sum[i-1];
	}
	for(int i=1;i<=2*m+1;i++){
		sum[i]+=sum[i-1];
	}
	ll s=ans;
	for(int i=1;i<=m;i++){
		ans=min(ans,s+sum[i]+sum[i+m]);
	}
	cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 2560
A,B,m = map(int,input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
mn = min(a)+min(b)
for i in range(m):
    x,y,c = map(int,input().split())
    res = a[x-1]+b[y-1]-c
    if mn > res:
        mn = res
print(mn)

Measured memory_bytes: 70380
# -*- coding: utf-8 -*-

N, L = map(int, input().split())

apple = [L + i - 1 for i in range(1, N + 1)]
diff = abs(apple[0])
for i in range(1, N):
    diff = min(diff, abs(apple[i]))

print(sum(apple) - diff if sum(apple) > 0 else sum(apple) + diff)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int n,w;
#define int long long int 
vector<pair<int,int> >v;
int dp[104][100005];
int solve(int idx,int weight)
{
	if(idx==0 || weight==0)
	return 0;
	if(dp[idx][weight]!=-1)return dp[idx][weight];
	if(v[idx-1].first>weight)
	return	dp[idx][weight]=solve(idx-1,weight);

	return dp[idx][weight]=max(v[idx-1].second+solve(idx-1,weight-v[idx-1].first),solve(idx-1,weight));
}
signed main()
{
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif*/
	cin>>n>>w;
	for(int i=0;i<n;i++)	
	{
		int a,b;
		cin>>a>>b;
		v.push_back({a,b});
	}
	memset(dp,-1,sizeof dp);
	cout<<solve(n,w);
}

Measured memory_bytes: 81536
n,k = map(int, input().split())
H = [0]+list(map(int, input().split()))
dp = [float("inf")]*(n+1)
dp[0] = 0
dp[1] = 0

for i in range(1, n):
  for k_i in range(1, k+1):
    if i+k_i<=n:
      dp[i+k_i] = min(dp[i+k_i], dp[i]+abs(H[i+k_i]-H[i]))
      
print(dp[-1])

Measured memory_bytes: 86364
n = int(input())
a = list(map(int, input().split()))

s = 0
s_pre = 10000000000

for j in range(-100, 101):
    for i in range(n):
        s += pow((a[i] - j),2)
    if s_pre > s:
        s_pre = s
    s = 0
print(s_pre)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
long long n,ans,c1,c2,c3;
string s;
int main()
{
	cin>>n>>s;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='R')
		{
			c1++;
		}
		if(s[i]=='B')
		{
			c2++;
		}
		if(s[i]=='G')
		{
			c3++;
		}
	}
	ans=c1*c2*c3;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			int k=j+(j-i);
			if(k>=n)
			{
				continue;
			}
			if(s[i]!=s[j] && s[j]!=s[k] && s[i]!=s[k])
			{
				ans--;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3628
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
a = lr()
default = [0 for i in range(n)]
next = [0 for i in range(n)]
for i in range(n):
    tmp = a[i]
    for j in range(i, n):
        if tmp > a[j]:
            default[i]+=1
    for j in range(n):
        if tmp > a[j]:
            next[i]+=1
ans = 0
for i in range(n):
    ans+=(default[i]*k)%mod+(next[i]*(((k)*(k-1)))//2)%mod
    ans%=mod
print(ans)

Measured memory_bytes: 73356
#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
#include<utility>//pair
#include<cmath>//abs,sqrt
#include<cstring>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) memset(arg,n,sizeof(arg))
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int INF=1e+9;
const ll INFLL=1e+17;
int a,b;
int main(){
  cin>>a>>b;
  if(a%3==0) prin("Possible");
  else if(b%3==0) prin("Possible");
  else if((a+b)%3==0) prin("Possible");
  else prin("Impossible");
    


  

  return 0;
}


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

int main(){
	string S;
	cin >> S;
	int N = S.size();
	int a, b;
	for(int i = 0; i < N; i++){
		if(S.at(i) == 'A'){
			a = i;
			break;
		}
	}
	for(int i = N - 1; i >= 0; i--){
		if(S.at(i) == 'Z'){
			b = i;
			break;
        }
	}
	
	int ans = b - a + 1;
	cout << ans << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;


int main(int argc, const char * argv[]) {
    int a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c - max(a, max(b, c)) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int N,X,Y;
int count[2020];
main()
{
	cin>>N>>X>>Y;
	X--,Y--;
	for(int i=0;i<N;i++)
	{
		for(int j=i+1;j<N;j++)
		{
      count[min(j-i,abs(X-i)+1+abs(Y-j))]++;
		}
	}


	for(int k=1;k<N;k++)cout<<count[k]<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define INF 1000000000000000
#define fi first
#define se second
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
struct edge { int to, cost; };
typedef pair<int, int> P;
int n;
int a[32];
int ma = 0;
int ans = 0;
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	rep(i, n) {
		if (ma <= a[i]) {
			ma = a[i];
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const int MAXN = 220000;

int fl[MAXN];
int ans[MAXN];
int go[MAXN];
int a[MAXN];
map<int, int> mm;

int get(int x) {
	if (!fl[x])
		return ans[x];
	fl[x] = 0;
	return ans[x] = get(go[x]);
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n - 1; ++i)
		scanf("%d", a + i);
	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; ++i) {
		int x;
		scanf("%d", &x);
		if (!mm.count(x))
			mm[x] = i;
		else
			fl[i] = 1, go[i] = mm[x];
	}
	int dd = 0;
	for (int i = n - 2; i >= 2; --i) {
		dd -= a[i];
		while (mm.begin()->first + dd < 0) {
			pair<int, int> tmp = *mm.begin();
			mm.erase(mm.begin());
			tmp.first = abs(tmp.first + dd) - dd;
			if (mm.count(tmp.first)) {
				fl[tmp.second] = 1;
				go[tmp.second] = mm[tmp.first];
			}
			else {
				mm[tmp.first] = tmp.second;
			}
		}
	}
	for (auto i: mm)
		ans[i.second] = a[0] - a[1] + i.first + dd;
	for (int i = 0; i < m; ++i)
		if (fl[i])
			ans[i] = get(i);
	for (int i = 0; i < m; ++i)
		printf("%d\n", ans[i]);
	return 0;
}




Measured memory_bytes: 14208
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

fn main() {
  input! {
    s: String
  };
  let res = if s == "ABC" { "ARC" } else { "ABC" };
  println!("{}", res);
}


Measured memory_bytes: 2092
#include <cmath>
#include <cstdio>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stack>
#include <fstream>
#include <queue>
#include <iomanip>
#include <iterator>
#include <map>
#include <unordered_map>
#include <set>
#define fast ios_base::sync_with_stdio(false)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define vvi vector<vi >
#define pi pair<ll,ll>
#define vvpi vector<vector<pi > >
#define vpi vector<pi >
#define vppi vector<pair<ll,pi > >
#define vs vector<string>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define fs first
#define se second
#define crz(v,n) v.clear(),v.resize(n+1,0)
#define print(v) for(ll it=0;it<v.size();it++) cout<<v[it]<<" ";cout<<endl
#define printp(v) for(ll it=0;it<v.size();it++) cout<<v[it].first<<" "<<v[it].second<<endl
using namespace std;
pi fx(ll a,ll b){
	return mkp(min(a,b),max(a,b));
}
int main(){
	ll i,n,k=0,f,ff=0;
	cin>>n;
	vvi g(n+1);vpi a(n-1);map<pi,ll>mp;vi d(n+1);
	for(i=0;i<n-1;i++){
		cin>>a[i].fs>>a[i].se;
		g[a[i].fs].eb(a[i].se);
		g[a[i].se].eb(a[i].fs);
		d[a[i].se]++,d[a[i].fs]++;
		k=max(k,max(d[a[i].se],d[a[i].fs]));
	}for(i=1;i<=n;i++){sort(all(g[i]));
		if(g[i].size()==1&&!mp[fx(i,g[i][0])]) mp[fx(i,g[i][0])]=1;
		else if(g[i].size()>1){f=1,ff=0;
			for(auto j:g[i]){
//				cout<<i<<" "<<j<<" "<<f<<" "<<mp[fx(i,j)]<<endl;
				if(!mp[fx(i,j)]) mp[fx(i,j)]=f%k+1,f++;
				else if(!ff) f=mp[fx(i,j)],ff=1;
//				cout<<i<<" "<<j<<" "<<f<<" "<<mp[fx(i,j)]<<endl;
			}
		}
	}cout<<k<<endl;
	for(auto i:a) cout<<mp[fx(i.fs,i.se)]<<endl;
}


Measured memory_bytes: 15104
#include <stdio.h>
#define MAX 101
#define INFINITY 1048576 // 2???20???
#define WHITE -1
#define GRAY 0
#define BLACK 1
#define true 1

void serch(int,int *);

int M[MAX][MAX];

int main() {

  int n,i,j,k,v,a,d[MAX];
  scanf("%d",&n);

  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++) {
      M[i][j] = INFINITY;
    }
  }
  for(i = 0; i < n; i++) {
    scanf("%d%d",&a,&k);
    for(j = 0; j < k; j++) {
      scanf("%d",&v);
      scanf("%d",&M[i][v]);
    }
  }

  serch(n,d);

  for(i = 0; i < n; i++) {
    printf("%d ",i);
    if(d[i] == INFINITY) printf("%d",-1);
    else printf("%d\n",d[i]);
  }
  return 0;
}

void serch(int n,int *d) {
  int u, v, min, i, j, p[MAX], c[MAX];

  for(i = 0; i < n; i++) {
    c[i] = WHITE; //?????????
    d[i] = INFINITY; //???????????§????????????????????????
  }

  d[0] = 0;
  c[0] = GRAY;

  while(true) {
    min = INFINITY;
    u = -1;

    for(i = 0; i < n; i++) {
      if(min > d[i] && c[i] != BLACK) {
        u = i; //u?????????
        min = d[i];
      }
    }

    if(u == -1) break;

    c[u] = BLACK;

    for(v = 0; v < n; v++) {
      if(c[v] != BLACK && M[u][v] != INFINITY) {
        if(d[v] > M[u][v] + d[u]) {
          d[v] = M[u][v] + d[u];
          c[v] = GRAY;
        }
      }
    }
  }

  return;
}

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

int main() {
  int N; cin >> N;

  rep_eq( i, 1, 9 ) {
    rep_eq( j, 1, 9 ) {
      if ( N==i*j ) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
/*
.....            
.        .       *
.....   . .      .
    .  .....     .
..... .     .    .
*/
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
   
using namespace std;
   
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
   
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}
#define int long  long
#define left left228
#define right right228
#define prev prev228

const int N = 100 * 1000 + 228;

int a[N];

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	int i = 1;
	int res = 0;
	while (i <= n) {
		if (a[i] == 0) {
			++i; continue;
		}
		int j = i;
		int sum = a[i];
		while (j + 1 <= n && a[j + 1]) ++j, sum += a[j];
		res += sum / 2;
		i = j + 1;
	}
	cout << res << endl;
	return 0;
}


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

int cmp(const void *p, const void *q) {
  return *(int*)q - *(int*)p;
}

int main() {
  int height[10];
  int h, i, n;
  for(i = 0; i < 10; i++) {
    scanf("%d", &h);
    height[i] = h;
  }

  n = sizeof(height)/sizeof(int);
  qsort(height, n, sizeof(int), cmp);
  for(i = 0; i < 3; i++) {
    printf("%d\n", height[i]);
  }
  
  return 0;
}

Measured memory_bytes: 604
N, *A = map(int, open(0).read().split())
print(' '.join([str(a) for a in A]))
for i in range(1, N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j + 1] = A[j]
        j -= 1
    A[j+1] = v
    print(' '.join([str(a) for a in A]))


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

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

int main() {
  int n; cin >> n;
  vector<long long> a(n);
  rep(i, n) cin >> a[i];

  long long dp[n][n];
  rep(i, n) dp[i][i] = a[i];

  for (int i = n - 2; i > -1; --i) {
    for (int j = i + 1; j < n; ++j) {
      dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]);
    }
  }
  cout << dp[0][n - 1] << endl;
}


Measured memory_bytes: 70528
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<cstring>
#include<algorithm> 
using namespace std;
const double pai=3.1415926535;

int main()
{
	double res;
	int r;
	cin>>r;
	res=pai*2*r;
	printf("%.7lf",res);
}
 

Measured memory_bytes: 3764
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;

class Solver {
    Scanner sc = new Scanner();

    class pair {
        public int c;
        public int t;
    }

    public void Solve() {
        int N = sc.nextInt();
        int T = sc.nextInt();
        var p = new pair[N];
        for (int i = 0; i < N; i++) {
            p[i] = new pair { c = sc.nextInt(), t = sc.nextInt() };
        }

        if (p.Count(a => a.t <= T) == 0) {
            WriteLine("TLE");
        } else {
            WriteLine(p.Where(a => a.t <= T).Min(a => a.c));
        }
    }

}



class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}


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

int main() {
  int n;
  long long ans = 0;
  cin >> n;
  vector<int>data(n);
  for(int i = 0;i < n;i++){
    cin >> data.at(i);
  }
  for(int i = 0;i < n-1;i++){
    for(int j = i+1;j < n;j++){
      ans += data.at(i)*data.at(j);
    }
  }
  cout << ans << endl;
}


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

int E;

int solve(){
  int ans = 1000000;
  for(int z = 0; z * z * z <= E; ++z){
    int F = E - z * z * z;
    for(int y = 0; y * y <= F; ++y){
      int x = F - y * y;
      ans = min(ans, x + y + z);
    }
  }
  return ans;
}

int main(){
  while(scanf("%d", &E) && E > 0){
    printf("%d\n", solve());
  }
}

Measured memory_bytes: 1028
#include <cstdio> 
#include <iostream>
#include<algorithm>
#include <cstring>

using namespace std;

int main(){
	char coffee[10];
	scanf("%s",coffee);
	if(coffee[2] == coffee[3] && coffee[4] == coffee[5]){
		printf("Yes");
	}else{
		printf("No");
	}
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
int main(){
  int r,g,b,ans;
  cin >> r >> g >> b;
  g = g*10;
  ans = g+b;
  if((g+b)%4 != 0) cout << "NO" << endl;
  else if(g == 0 && b==0) cout << "NO" << endl;
  else cout << "YES" << endl;
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
//#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
const int maxn = (ll) 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
int a[maxn];
bool vis[maxn];
int num[maxn];

void solve() {
    int n;
    cin >> n;
    int maxx = 0;
    rep(i, 1, n)cin >> a[i], maxx = max(maxx, a[i]), ++num[a[i]];
    int ans = 0;
    rep(i, 1, n) {
        if (!vis[a[i]]) {
            for (int j = a[i] + a[i]; j <= maxx; j += a[i])
                vis[j] = true;
        }
    }
    rep(i, 1, n)ans += (!vis[a[i]] && num[a[i]] == 1);
    cout << ans;
}

signed main() {
    start;
    while (T--)
        solve();
    return 0;
}

Measured memory_bytes: 9216
from collections import defaultdict
import sys
def inpl(): return [int(i) for i in input().split()]
H, W, N = inpl()
if not N:
    print(H)
    sys.exit()
A = []
B = defaultdict(lambda: [])
C = defaultdict(lambda: H+1)
for _ in range(N):
    x, y = inpl()
    A.append((x,y))
    B[y].append(x)
T = [0]*(W+1)
T[1] = 2
for i in range(1,W):
    if not B[i+1]:
        T[i+1] = T[i] + 1
        continue
    ctr = T[i]
    while True:
        if ctr in B[i+1]:
            ctr += 1
            continue
        break
    T[i+1] = min(ctr+1, H+1)
for x,y in A:
    if x >= T[y]:
        C[y] = min(C[y], x)
print(min([i-1 for i in C.values()]+[H]))

Measured memory_bytes: 75756
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;

int main(void)
{
  LL n;
  cin >> n;
  vector<LL> a(n*3);
  for(auto &x:a) cin >> x;
  vector<LL> l(n+1),r(n+1);
  priority_queue<LL> lp,rp;
  REP(i,n) {
    l[0]+=a[i];
    lp.push(-a[i]);
    r[n]+=a[i+n*2];
    rp.push(a[i+n*2]);
  }
  REP(i,n) {
    lp.push(-a[n+i]);
    l[i+1]=l[i]+a[n+i]+lp.top();
    lp.pop();
    rp.push(a[n*2-i-1]);
    r[n-i-1]=r[n-i]+a[n*2-i-1]-rp.top();
    rp.pop();
  }
  LL answer=l[0]-r[0];
  REP(i,n+1) {
    answer=max(answer,l[i]-r[i]);
  }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 5996
a=[]
w = gets.to_i
n = gets.to_i
w.times{|i|
  a[i] = i + 1
}
n.times{
  x,y = gets.split(",").map(&:to_i)
  a[x-1],a[y-1] = a[y-1],a[x-1]
}
puts a


Measured memory_bytes: 6868
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
const int N=1e5;
int n;
vector<int> par;
vector<int> sz;
struct edge{int u,v,d;};
vector<edge> es;
int find(int a)
{
	while(a!=par[a])a=par[a];
	return a;
}
bool same(int a,int b)
{
	a=find(a);b=find(b);
	return a==b;
}
void uni(int a,int b)
{
	a=find(a);
	b=find(b);
	if(sz[a]<sz[b])swap(a,b);
	sz[a]+=sz[b];
	par[b]=a;
}
pair<int,int> x[N],y[N];
bool comp(edge a, edge b)
{
	return a.d<b.d;
}
int32_t main()
{
	n=in();
	sz=par=vector<int>(n);
	iota(all(par),0);
	fill(all(sz),1);
	for(int i=0;i<n;i++)
	{
		x[i].first=in();y[i].first=in();
		x[i].second=y[i].second=i;
	}
	sort(x,x+n);sort(y,y+n);
	
	for(int i=1;i<n;i++)
	{
		es.push_back(edge{.u=x[i-1].second,.v=x[i].second,.d=x[i].first-x[i-1].first});
		es.push_back(edge{.u=y[i-1].second,.v=y[i].second,.d=y[i].first-y[i-1].first});
	}
	sort(all(es),comp);
	int ans=0;
	int a,b,w;
	for(auto i:es)
	{
		a=i.u;b=i.v;w=i.d;
		if(same(a,b))continue;
		uni(a,b);
		ans+=w;
	}
	cout<<ans;
	
	
}

Measured memory_bytes: 14320
#include <stdio.h>

/*keyが配列S内にあるかを調べる*/
int Liner_Search(int key , int S[] , int n) {
    int i = 0;
    
    while(S[i] != key) {
        i++;
        /*Sの配列は0〜n-1まで*/
        /*最後まで行った＝一致する要素なし*/
        if(i == n - 1)
            return -1;
    }
    /*whileに入らなかった＝keyとSの要素がイコールだった*/
    return 1;
}

int main(void)
{
    int n , q;
    int i , j , k;
    int count = 0;
    
    scanf("%d" , &n);
    
    int S[n];
    for(i = 0 ; i < n ; i++)
        scanf("%d" , &S[i]);
    
    scanf("%d" , &q);
    
    int T[q];
    for(j = 0 ; j < q ; j++)
        scanf("%d" , &T[j]);
    
    for (k = 0 ; k < q ; k++) {
        if(Liner_Search(T[k] , S , n) == 1)
            count++;
    }
    
    printf("%d\n" , count);
    
    return 0;
}



Measured memory_bytes: 2140
#B
n,m = [int(i) for i in input().split()]
"""
xs = []
ys = []
for _ in range(m):
    x,y = [int(i) for i in input().split()]
    xs.append(x)
    ys.append(y)
"""

counts = [1] * n
possible = [1] + [0]*(n-1)

for _ in range(m):
    x,y = [int(i) for i in input().split()]
    
    counts[x-1] -= 1
    counts[y-1] += 1
    
    if possible[x-1]==1:
        possible[y-1] = 1
    
    if counts[x-1]==0:
        possible[x-1] = 0
        
cnt = 0
for v in possible:
    if v==1:
        cnt += 1

print(cnt)   

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

int main(){
  int N;
  cin >> N;

  int fst= -1;
  int snd= -1;
  bitset<200000> bits;
  int buf;
  for(int i=0; i<N; i++){
    cin >> buf;
    if( buf > fst ){
      snd= fst;
      fst= buf;
      bits.reset();
      bits.set(i);
    }
    else if( buf==fst ){
      snd= fst;
      bits.set(i);
    }
    else if( buf > snd ){
      snd= buf;
    }
  }

  for(int i=0; i<N; i++){
    if( bits.test(i) ){
      cout << snd << endl;
    }
    else{
      cout << fst << endl;
    }
  }
}

Measured memory_bytes: 1664
tab = [list(map(int,input().split())) for _ in range(3)]
a=[0]*3
b=[0]*3
a[0]=0
b[0]=tab[0][0]-a[0]
a[1]=tab[1][0]-b[0]
a[2]=tab[2][0]-b[0]
b[1]=tab[0][1]-a[0]
b[2]=tab[0][2]-a[0]
for i in range(3):
    for j in range(3):
        if tab[i][j]!=a[i]+b[j]:
            print('No')
            break
    else:
        continue
    break
else:
    print('Yes')


Measured memory_bytes: 3064
ary = gets.chomp.split('')
ary_odd = []
ary_even = []
ary.each_with_index do |str, idx|
    if idx.odd?
        ary_odd << str
    else
        ary_even << str
    end
end

if !(ary_even.include?("L") || ary_odd.include?("R"))
    puts "Yes"
else
    puts "No"
end

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(i=0;i<n;i++)
#define rep1(i,n) for(i=1;i<=n;i++)
#define test(a) cout << "*" << a << endl
#define ll long long
int main(){
  int n,m;
  int i;
  ll H[100001];
  ll A[100001];
  ll B[100001];
  ll countGood=0;
  bool existM[100001];
  
    
  cin >> n >> m;
  rep1(i,n){
    cin >> H[i];
  }
  rep1(i,m){
    cin >> A[i] >> B[i];
  }
  rep1(i,n){
   existM[i] = true; 
  }
  
  rep1(i,m){
     if(H[A[i]] > H[B[i]]){
       existM[B[i]] = false;
     }
     else if(H[A[i]] < H[B[i]]){
       existM[A[i]] = false;
     }
     else{
       existM[A[i]] = false;
       existM[B[i]] = false;
     }
   //existM[ min(H[A[i]],H[B[i])]] = false;/*負けた展望台*/
  }
  
  rep1(i,n){
    if(existM[i])
      countGood++;
  }
  cout << countGood << endl;
  
  
}

Measured memory_bytes: 6052
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using PLL = pair<LL,LL>;
using VPI = vector<PII>;
using VPL = vector<PLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
	//i=m -> n-1(昇順)
#define RREP(i,m,n) for(int i=(m);i>=(n);i--)
	//i=m -> n(降順)

int main(){
  LL d,g,ans=1<<30;
  cin >> d >> g;
  VLL p(d+1), c(d+1);
  REP(i,1,d+1){
    cin >> p[i] >> c[i];
  }
  
  REP(i,0,1<<d){
    LL sum = 0;
    LL cnt = 0;
    REP(j,0,d){
      if(((i>>j)&1) == 1){
        sum += p[d-j] * (d-j) * 100 + c[d-j];
        cnt += p[d-j];
      }
    }
    if(sum >= g){
      ans = min(ans,cnt);
      continue;
    }
    REP(k,0,d){
      int out = (i>>k)&1;
      if(((i>>k)&1) == 0){
        LL sum_max = sum + (p[d-k]-1) * (d-k) * 100;
        if(sum_max < g){break;}
        while(sum < g){
          sum += (d-k) * 100;
          cnt++;
        }
        ans = min(ans,cnt);
        break;
      }
    }
  }   
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

vl a(4);
vector<map<ll, ll>> mp;

ll f(ll n, ll r) {
  if(mp[r].count(n)) return mp[r][n];
  ll res = 1e18;
  if(1e18 / a[3] > n) res = n * a[3];
  if(n <= 1) {
    mp[r][n] = res;
    return res;
  }
  vl v = {2, 3, 5};
  rep(i, 3) {
    ll k = v[i];
    ll x = n / k;
    ll now = f(x, r) + a[i] + (n - x * k) * a[3];
    res = min(res, now);
    if(n % k) {
      now = f(x + 1, r) + a[i] + ((x + 1) * k - n) * a[3];
      res = min(res, now);
    }
  }
  mp[r][n] = res;
  return res;
}

int main() {
  ll t;
  cin >> t;
  mp = vector<map<ll, ll>>(t);
  rep(r, t) {
    ll n;
    cin >> n;
    rep(i, 4) cin >> a[i];
    cout << f(n, r) << endl;
  }
}

Measured memory_bytes: 10400
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
using namespace std;

int main()
{
    int antena[5];
    for(int i=0; i<5; i++){
        cin >> antena[i];
    }
    int k;
    cin >> k;
    string ans="Yay!";
    for(int i=0; i<5; i++){
        for(int j=0; j<i-1; j++){
            if(antena[i]-antena[j]>k){
                ans=":(";
            }
        }
    }
    cout << ans;

    return 0;
}

Measured memory_bytes: 888
n,k=map(int,input().split())
mod=10**9+7
lst=[0]*(k+1)
ans=0

for i in range(k,0,-1):
  lst[i]+=pow(k//i,n,mod)
  if k//i==1:
    continue
  else:
    for j in range(2,k//i+1):
      lst[i]-=lst[i*j]
      
for i in range(1,k+1):
  ans+=(i*lst[i])%mod
  ans%=mod
  
print(ans)
  

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

void Main() {
  int K;
  cin >> K;

  if (K <= 9) {
    cout << K << endl;
    return;
  }
  queue<long long> q;
  for (int i = 1; i <= 9; i++) {
    q.push(i);
  }
  int i = 9;
  long long ans = 9;
  while (i < K) {
    long long tmp = q.front(); q.pop();
    //cout << i << ", " << tmp << endl;
    long long a, b, c;
    if (tmp % 10 == 0) {
      a = tmp * 10;
      b = tmp * 10 + 1;
      q.push(a);
      q.push(b);
      if (K - i == 1) {
        ans = a;
        break;
      } else if (K - i == 2) {
        ans = b;
        break;
      }
      i += 2;
    } else if (tmp % 10 == 9) {
      a = tmp * 10 + 8;
      b = tmp * 10 + 9;
      q.push(a);
      q.push(b);
      if (K - i == 1) {
        ans = a;
        break;
      } else if (K - i == 2) {
        ans = b;
        break;
      }
      i += 2;
    } else {
      a = tmp * 10 + (tmp % 10 - 1);
      b = tmp * 10 + (tmp % 10);
      c = tmp * 10 + (tmp % 10 + 1);
      q.push(a);
      q.push(b);
      q.push(c);
      if (K - i == 1) {
        ans = a;
        break;
      } else if (K - i == 2) {
        ans = b;
        break;
      } else if (K - i == 3) {
        ans = c;
        break;
      }
      i += 3;
    }
  }
  cout << ans << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}



Measured memory_bytes: 768
#include<stdio.h>
int gcd(int x,int y){
    if(!y)return x;
    return gcd(y,x%y);
}
int main(){
    int k;scanf("%d",&k);
    int ans=0;
    int x;
    for(int i=1;i<=k;i++){
        for(int j=1;j<=k;j++){
            for(int k1=1;k1<=k;k1++){
                x=gcd(i,j);
                x=gcd(x,k1);
                ans+=x;
            }
        }
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 1736
while True:
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break
    count = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            k = x - (i + j)
            if j < k and k <= n:
                count += 1
    print(count)



Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  string s;
  cin >> s;
  ll n=s.size();
  ll f=0;
  for(ll i=0;i<n;i++) {
    if(f==0) {
      if(s[i]=='C') f=1;
    }
    else if(s[i]=='F') f=2;
  }
  if(f==2) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 384
import collections

n,q=map(int,input().split())
a=sorted(list(list(map(int,input().split())) for i in range(n-1)))
p=collections.defaultdict(int)
for i in range(q):
  k,v=map(int,input().split())
  p[k]+=v

li=[0]*n
li[0]+=p[1]
for i in range(n-1):
  li[a[i][1]-1]+=li[a[i][0]-1]+p[a[i][1]]
print(*li)

Measured memory_bytes: 90116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef vector<pii> vii;
typedef vector<pll> vll;
#define fi first
#define se second
#define pi 3.141592653589793
#define mod 998244353
#define pb push_back
#define all(v) v.begin(),v.end()
#define tc int t;cin>>t;while(t--)
#define pqmax priority_queue<int>
#define pqmin priority_queue<int,vi,greater<int>>
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL)
#define tc_g int tt;cin>>tt;for(int ti=1;ti<=tt;ti++)
#define case_g "Case #"<<ti<<": "
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;

ll modpower(ll x, ll y) {
	if (y == 0)
		return 1;
	ll p = modpower(x, y / 2) % mod;
	p = (p * p) % mod;
	return y & 1 ? (x * p) % mod: p;
}

ll modinverse(ll a)
{
    ll m = mod;
    ll y = 0, x = 1;
    while (a > 1)
    {
        ll q = a / m;
        ll t = m;
        m = a % m;
        a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    return x < 0 ? x + mod : x;
}

vl fact(500005);

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

int main() {
	fast_io;
	ll n, m, k;
	cin >> n >> m >> k;
	fact[0] = 1;
	for (int i = 1;i < 500005;i++)
		fact[i] = fact[i - 1] * i % mod;
	ll ans = m * modpower(m - 1, n - 1) % mod;
	for (int i = 1;i <= k;i++) {
		ans += m * modpower(m - 1, n - i - 1) % mod * ncr(n - 1, i) % mod;
		ans %= mod;
	}
	cout << ans << '\n';
}


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

int A[100000], n;

int Partition(int p, int r){
	int x = A[r - 1], j = 0;
	//printf("%d ", A[r - 1]);
	for(int i = 0;i < n;i++){
		if(A[i] <= x){
			int tmp = A[j];
			A[j++] = A[i];
			A[i] = tmp;
		}
	}
	return j - 1;
}

main(){
    scanf("%d", &n);
    for(int i = 0;i < n;i++)scanf("%d", &A[i]);
	int j = Partition(0, n);
	for(int i = 0;i < n - 1;i++){
		if(i)printf(" ");
		if(i == j)printf("[");
		printf("%d", A[i]);
		if(i == j)printf("]");
	}
	printf(" %d\n", A[n - 1]);
}

Measured memory_bytes: 3524
#include <stdio.h>

int main(void)

{

  char in[1001];


  int out,i;


  for(;;)


  {


    scanf("%s",in);


    if(in[0]=='0')


    {


      return 0;


    }


    out=0;


    for(i=0;in[i]!='\0';i++)


    {


      out +=in[i] - '0';


    }


    printf("%d\n",out);


  }


}

Measured memory_bytes: 536
#include<stdio.h>
#include<stdio.h>

int main(void)
{
  int n,i,ans=0,count,max=0;
  scanf("%d",&n);
  int p[n],index[n];
  for(i=0;i<n;i++)
    {
      scanf("%d",&p[i]);
      index[p[i]-1] = i;
    }
  
  if(n == 1)
    {
      printf("0\n");
      return 0;
    }
  
  count = 1;
  for(i=1;i<n;i++)
    {
      
      if(index[i] > index[i-1])
	{	
	count++;
	}
      else
	{
	  count = 1;
	}
      if(max < count)
	{
	  max = count;
	}
    }
  ans = n - max;
  printf("%d\n",ans);
  return 0;
}



Measured memory_bytes: 1664
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<iomanip>
#include<cassert>

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

	int x[4];
	int y[4];

	std::cin >> x[0] >> y[0] >> x[1] >> y[1];

	x[2] = x[1] + (y[0] - y[1]);
	y[2] = y[1] + (x[1] - x[0]);

	x[3] = x[2] + (y[1] - y[2]);
	y[3] = y[2] + (x[2] - x[1]);

	std::cout << x[2] << ' ' << y[2] << ' ' << x[3] << ' ' << y[3] << '\n';

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;

int main() {
  string s;
  cin >> s;
  deque<int> q(s.begin(), s.end());

  int ans = 0;
  while (q.size() >= 2) {
    if (q.front() == q.back()) {
      q.pop_front();
      q.pop_back();
    } else if (q.front() == 'x') {
      ans++;
      q.push_back('x');
    } else if (q.back() == 'x') {
      ans++;
      q.push_front('x');
    } else {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 768
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,k[20],s[20][20],p[20],sum=0;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>k[i];
		for(int j=1;j<=k[i];j++)
		{
			cin>>s[i][j];
		}
	}
	for(int i=1;i<=m;i++)
	{
		cin>>p[i];
	}
	for(int i=0;i<(1<<n);i++)
	{
		int t=0;
		for(int j=1;j<=m;j++)
		{
			int count=0;
			for(int k=1;k<=n;k++)
			{
				if(i&(1<<(s[j][k]-1)))count++;
			}
			if(count%2==p[j])t++;
			else break;
		}
		if(t==m)sum++;
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
 int N,A[100];
 scanf("%d",&N);
 for(int i=0;i<N;i++){
  scanf("%d",&A[i]);
 }
 int flag = 1,cnt=0;
 while(flag){
  flag = 0;
  for(int j = N-1;j>= 1;j--){
   if( A[j] < A[j-1]){
    int a=A[j];
    A[j] = A[j-1];
    A[j-1]=a;
    flag = 1;
    cnt++;
   }
  }
 }
 for(int i=0;i<N-1;i++){
  printf("%d ",A[i]);
 }
 printf("%d\n%d\n",A[N-1],cnt);
 return 0;
}

Measured memory_bytes: 1028
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

int main() {
	int a;
	string s;
	cin >> a >> s;


	cout << (a >= 3200 ? s : "red") << endl;

	return 0;
}


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

using namespace std;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, a, b;
    cin >> n >> a >> b;

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = i, tt = 0;
        while (t)
            tt += t % 10, t /= 10;
        ans += i * (tt >= a && tt <= b);
    }
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
import queue
n, m = map(int,input().split())

pr = [[] for i in range(n+1)]

for i in range(m):
    x,y,z = map(int,input().split())
    pr[x].append(y)
    pr[y].append(x)

def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n+1)]
    q = queue.Queue()
    for i in range(1,n+1):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

print(len(grouping(n,pr)))


Measured memory_bytes: 39660
using System;
using System.Linq;
using static System.Console;

class P
{
    static void Main()
    {
        while (true)
        {
            var a = ReadLine().Split().Select(int.Parse).ToList();
            int n = a[0], x = a[1], ans = 0;
            if (n + x == 0) break;
            for (int i = 1; i <= n; i++)
            {
                for (int j = -~i; j <= n; j++)
                {
                    var k = x - i - j;
                    if (j < k && k <= n) ans++;
                }
            }
            WriteLine(ans);
        }
    }
}


Measured memory_bytes: 18332
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma comment(linker, "/STACK:16777216")
#pragma warning( disable : 6031)
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <numeric>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <sstream>
#include <functional>
#include <iomanip>
#include <limits>

#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define eps (1e-9)
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<double> vd;
typedef vector< vd > vvd;
typedef vector< ll > vll;
typedef vector< vll > vvll;
typedef vector< string > vs;
typedef pair< int, int > pii;
typedef vector< pii > vpii;
typedef tuple<int, int, int> tiii;
const long long mod = 1000000007;

template<typename T>
void max_self(T& a, T b)
{
	a = max(a, b);
}
template<typename T>
void add_self(T& a, T b)
{
	a += b;
	if (a >= mod)
		a -= mod;
}
template<typename T>
void sub_self(T& a, T b)
{
	a -= b;
	if (a < 0)
		a += mod;
}

// dp[i][j] - number of ways to distribute i candies to j kids

int main()
{ 
#ifdef LOCAL_MACHINE
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
#endif
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << setprecision(18) << fixed;
	int n;
	cin >> n;
	vi a(n);
	for (int& ac : a)
		cin >> ac;
	vvll dp(n + 1, vll(n + 1));
	vll psum(n + 1);
	for (int i = 1; i <= n; i++)
		psum[i] = psum[i - 1] + a[i - 1];
	auto sum = [&](int L, int R)
	{
		return psum[R + 1] - psum[L];
	};
	for (int L = n - 1; L >= 0; L--)
		for (int R = L; R < n; R++)
		{
			if (L == R)
				dp[L][R] = 0;
			else
			{
				dp[L][R] = LLONG_MAX;
				for (int i = L; i <= R - 1; i++)
				{
					dp[L][R] = min(dp[L][R], dp[L][i] + dp[i + 1][R] + sum(L, R));
				}
			}
		}

	cout << dp[0][n - 1];
	return 0;
}

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

int main()
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  rep(i, s.size())
  {
    s[i] += n;
    if (s[i] > 'Z')
      s[i] -= 26;
  }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 3596
N,K=[int(i) for i in input().split()]
R,S,P=[int(i) for i in input().split()]
T=list(input())
M={"r":P,"s":R,"p":S}

done=[]
point=0
for i in range(K):
    temp=T[i]
    point+=M[temp]
    done.append(temp)

# print(T)
# print(done)

for j in range(K,N):
    temp=T[j]
    back=done[j-K]
    # print(temp,back)
    if temp!=back:
        point+=M[temp]
        done.append(temp)
    else:
        done.append('u')

print(point)


Measured memory_bytes: 4792