akhauriyash/Code-Regression huggingface dataset:
n, k = map(int, input().split())
a = list(map(int, input().split()))

def f(x):
    count = 0
    for ai in a:
        count += (ai // x) - (ai % x == 0)
    return count <= k

left, right = 0, 10 ** 9
while right - left > 1:
    x = (left + right) // 2
    if f(x):
        right = x
    else:
        left = x

print(right)

Measured memory_bytes: 30804
/*by freesteed*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get_be(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
//get_be biger & equal
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const ll oo=1e9+10;
const int Max = 1e6+10;
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 a[Max];
ll n;
void solve(){
	cin>>n;
	ll t,f=1;
	rep(i,0,n){
		cin>>t;
		if(t%2==0&&t%3&&t%5)f=0;
	}
	cout<<(f?"APPROVED":"DENIED");
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//caset{
		solve();
	//}
  	return 0;
}





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

int N, M;
Graph G(100010);
vector<int> indeg(100010, 0), out;
vector<bool> seen(100010, false);


void dfs(int u){
    queue<int> que;
    que.push(u);

    while(!que.empty()){
        int v = que.front();
        que.pop();
        seen[v] = true;
        out.push_back(v);

        rep(i, G[v].size()){
            int v2 = G[v][i];
            // if(seen[v2]) continue;
            indeg[v2]--;
            if(indeg[v2] == 0) que.push(v2);
        }

    }
}

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

    rep(i, M){
        int s, t;
        cin >> s >> t;
        G[s].push_back(t);
        indeg[t]++;
    }

    rep(u, N){
        if(!seen[u] && indeg[u] == 0) dfs(u);
    }

    rep(i, N){
        cout << out[i] << endl;
    }
}


Measured memory_bytes: 6204
a, b, c, d = map(int, input().split())
if b <= c or d <= a:
    ans = 0
else:
    if b <= d and c <= a:
        ans = b - a
    if b <= d and a <= c:
        ans = b - c
    if d <= b and c <= a:
        ans = d - a
    if d <= b and a <= c:
        ans = d - c
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
void solve(){
  int n,m;
  cin >> n >> m;
  vector<int> s(m),c(m);
  for(int i=0;i<m;i++)cin >> s[i] >> c[i];
  for(int i=0;i<1000;i++){
    string x = to_string(i);
    if(x.size()==n){
      bool valid = true;
      for(int j=0;j<m;j++)if(x[s[j]-1]!=('0'+c[j]))valid=false;
      if(valid){cout << i << endl; return;}
    }
  }
  cout << -1 << endl;
}
int main(){
  solve();
  return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}
int main() {
    unsigned long long x;
    cin >> x;
    unsigned long long c = 0LL;
    unsigned long long res = 0LL;
    res += (x / 11) * 2;
    x %= 11;
    c = 0;
    while(c < x) {
        c += 6;
        res++;
        if(c >= x) {
            break;
        }
        c += 5;
        res++;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100
#define NUM 100000000
#define WHITE 0
#define GRAY 2
#define BLACK 1
//dijkstra
int M[MAX][MAX],n,l[MAX],r[MAX],color[MAX];

void init(int num){
    int i;
       for(i=0; i<n; i++){
        l[i] = NUM;
        color[i] = WHITE;
        l[num] = 0;
        r[num] = -1;
      } 
}
 
void calc(int s){
  int i,u,v,min;
  
  init(s);
 
  while(1){
    min = NUM;
    for(i=0; i<n; i++)
        if(color[i] != BLACK && l[i] < min){
          min = l[i];
          u = i;
        }
    
    if(min == NUM) break;
    color[u] = BLACK;
 
    for(v=0; v<n; v++)
      if(color[v] != BLACK && M[u][v] != NUM &&l[u] + M[u][v] < l[v]){
          l[v] = l[u] + M[u][v];
          r[v] = u;
          color[v] = GRAY;
      } 
  }
  
  for(i=0;i<n;i++) (l[i] == NUM) ? printf("%d -1\n",i) : printf("%d %d\n",i,l[i]);
}

void set(int num){
    int i,j;
    for(i=0; i<num; i++)
        for(j=0; j<num; j++) M[i][j] = NUM;
}

void input(int num){
    int i,j,s,t,u,v;
    for(i=0; i<n; i++){
    scanf("%d%d",&s,&t);
    for(j=0; j<t; j++){
      scanf("%d%d",&u,&v);
      M[s][u] = v;
    }
  }
}

int main(){
  scanf("%d",&n);
  
  set(n);

  input(n);
 
  calc(0);
  return 0;
}


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

using namespace std;

const int MAXN=20;
const unsigned SEED=29;
int n;
long long ans;
unsigned long long sd[MAXN];
char s[MAXN<<1];
bool col[MAXN<<1];

map<unsigned long long,int> mp;

inline int chr_idx(char c){return c-'a'+1;}

inline void deal(){
	unsigned long long x=0,y=0;
	for(int i=1,a=0,b=n;i<=n;++i){
		int c=chr_idx(s[i]);
		if(col[i]) x+=c*sd[a++];
		else y+=c*sd[--b];
	}
	++mp[x-y];
}

void DFS1(int cur){
	if(cur>n){
		deal();
		return;
	}
	col[cur]=0;
	DFS1(cur+1);
	col[cur]=1;
	DFS1(cur+1);
}

inline void MIM(){
	unsigned long long x=0,y=0;
	for(int i=n<<1,a=n,b=0;i>n;--i){
		int c=chr_idx(s[i]);
		if(col[i]) x+=c*sd[--a];
		else y+=c*sd[b++];
	}
	ans+=mp[y-x];
}

void DFS2(int cur){
	if(cur>(n<<1)){
		MIM();
		return;
	}
	col[cur]=0;
	DFS2(cur+1);
	col[cur]=1;
	DFS2(cur+1);
}

inline void pre_cal(){
	sd[0]=1;
	for(int i=1;i<n;++i)
		sd[i]=sd[i-1]*SEED;
}

int main(){
	scanf("%d%s",&n,s+1);
	pre_cal();
	DFS1(1),DFS2(n+1);
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 33024
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
 
const int inf = 99999999;
const ll linf = 999999999999999999;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
 
ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

////////////////////////////////////////////////////////////

int main(){
  
  while(1){
    int n;
  
    cin >> n;
    
    if(n == 0)
      break;

    vector<unsigned int> a(n);
  
    rep(i,0,n)
      cin >> a[i];
  
    unsigned int min_sa = abs(a[0] - a[1]);
  
    sort( a.begin() , a.end());

    //cout << "UNKO" << endl;

    rep(i,0,n-1){
      if(min_sa > abs(a[i + 1] - a[i])){
        min_sa = abs(a[i+1] - a[i]);
        //cout << i << endl;
      }
    }   
    
    cout << min_sa << endl;
  }

  return 0;
}

Measured memory_bytes: 3032
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int gcd(int s)
{
	int i;
	for(i=2;i<=26;i++)
	{
		if(s%i==0&&26%i==0)break;
	}
	if(i<=26)return 1;
	else return 0;
}
int main()
{
	int n,a,b,c,i,j;
	cin >> n;
	while(getchar()!='\n');
	char str[257],tmp[257],henkan[26];
	for(i=0;i<n;i++)
	{
		fgets(str,sizeof(str),stdin);
		for(a=1;a<26;a++)
		{
			if(gcd(a))continue;
			for(b=0;b<26;b++)
			{
				memset(tmp,'\0',sizeof(tmp));
				for(c=0;c<26;c++)
				{
					henkan[(c*a+b)%26]=c;
				}
				for(j=0;str[j]!='\0'&&str[j]!='\n';j++)
				{
					if(str[j]>='a'&&str[j]<='z')
					{
						tmp[j] = henkan[str[j]-'a']+'a';
					}
					else
					{
						tmp[j] = str[j];
					}
				}
				if(strstr(tmp,"this")||strstr(tmp,"that"))
				{
					printf("%s\n",tmp);
					a=26;
					break;
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1136
import sys
import numpy as np
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    edge = [[] for _ in range(N)]
    ab = [tuple() for _ in range(N - 1)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)
        ab[i] = (a, b)

    # print(ab)
    # print(edge)

    max_v = 0
    max_v_dim = 0
    for i, e in enumerate(edge):
        if max_v_dim < len(e):
            max_v_dim = len(e)
            max_v = i

    # print(max_v)
    # print(max_v_dim)

    # bfs
    q = deque()
    q.append(max_v)
    ec = np.full(N, -1, dtype='i8')
    ec[max_v] = max_v_dim + 10
    vc = dict()
    # vc = np.full((N, N), -1, dtype='i8')

    while q:
        nv = q.popleft()
        nc = ec[nv]
        tc = 1
        for v in edge[nv]:
            v1, v2 = min(nv, v), max(nv, v)
            if not ((v1, v2) in vc):
                if nc == tc:
                    tc += 1
                ec[v] = tc
                vc[(v1, v2)] = tc
                tc += 1
                q.append(v)

    print(max_v_dim)
    for v1, v2 in ab:
        print(vc[(v1, v2)])


if __name__ == '__main__':
    solve()


Measured memory_bytes: 53064
#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <forward_list>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

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

    string s;
    cin >> s;

    int countLeft = 0;
    for (int i = 0; i + 1 < (int) s.size(); ++i) {
        if (s[i] != s[i + 1]) {
            ++countLeft;
        }
    }

    int countRight = 0;
    for (int i = (int) s.size() - 1; i > 0; --i) {
        if (s[i] != s[i - 1]) {
            ++countRight;
        }
    }

    cout << min(countLeft, countRight) << endl;

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <fstream>
#include <stdio.h>
//#define REP(i, n) for(int i = 0; i < n; i++)
//#define REPR(i, n) for(int i = n; i >= 0; i--)
//#define FOR(i, m, n) for(int i = m; i < n; i++)
//#define INF 1e9
//#define ALL(v) v.begin(), v.end()

using namespace std;
//typedef long long ll;

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

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

    //std::cout << "Hello, World!\n";
    
    int A, B;
    string ans = "";
    cin>>A>>B;

    if (A==B) {
        std::cout << "Yes";
    } else {
        std::cout << "No";
    }       
    
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		A();
	}
	
	public static void A() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		System.out.println(Math.min(A*N, B));
	}
	
	//calc harshad
	public static int calchar(int x) {
		int sum = 0;
		String num = ((Integer) x).toString();
		for(int i=0;i<num.length();i++) {
			sum += Character.getNumericValue(num.charAt(i));
		}
		return sum;
	}
	
	public static void B() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int sum = calchar(n);
		if(n%sum==0) System.out.println("Yes");
		else System.out.println("No");
	}
	/*
	 *  F i,j,k 店iが曜日jの時間帯kに開いているか
	 *  ci 本店と店iが同時に開いている時間帯の数
	 *  店の利益 P_1,c1 + Pncn  利益の最大値を求める
	 *  全部で 2^10通り 1000なので容易に行うことが可能
	 *  というか、時間帯ごとに関係はないので、10こ確かめる　（利益が正ならひらく）
	 *  また、利益が最大の時間帯を保持しておき、どうやっても利益がマイナスならそれを返す
	 *  ではない、何個かぶるかが重要 以下では、2^10
	 */
	public static void C() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int F[][] = new int[N][10];
		int P[][] = new int[N][11];
		for(int i=0;i<N;i++) {
			for(int j=0;j<10;j++) {
				F[i][j] = sc.nextInt();
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<11;j++) {
				P[i][j] = sc.nextInt();
			}
		}
		int counter = 1;
		int ret = Integer.MIN_VALUE;
		for(;counter<1024;counter++) {
			int nowsc = calcscore(counter,F,P);
			//System.out.println(nowsc);
			if(ret < nowsc) ret = nowsc;
		}
		System.out.println(ret);
	}
	// 2進数を受け取り、対応する曜日、時間帯が開催されているとして、スコアを返す 10桁 0001.. ~ 111.. 00000はない
	public static int calcscore(int bin, int[][] F, int [][] P) {
		int score = 0;
		int[] c = new int[F.length]; // 各店と同時に開いている回数
		for(int i=0;i<10;i++) {
			// if open
			if((bin & (1<<i)) != 0) {
				for(int j=0;j<F.length;j++) {
					if(F[j][i] == 1) c[j]++; 
				}
			}
		}
		for(int i=0;i<F.length;i++) {
			score += P[i][c[i]];
		}
		return score;
	}
	
	public static void D() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int C = sc.nextInt();
		List[] lis = new List[C];
		for(int i=0;i<C;i++) {
			lis[i] = new ArrayList<Integer>();
		}
		for(int i=0;i<N;i++) {
			int s = sc.nextInt();
			int t = sc.nextInt();
			int c = sc.nextInt()-1;
			//if(c>C) System.out.println("N");
			lis[c].add(s);
			lis[c].add(t);
		}
		int[] sum = new int[20000];
		for(int i=0;i<C;i++) {
			updatesum(sum,lis[i]);
		}
		int max = 0;
		for(int i=0;i<20000;i++) {
			if(max < sum[i]) max = sum[i];
		}
		System.out.println(max);
		
	}
	//チャネルのsitiのlistを受け取り、sumの配列を更新する
	public static void updatesum(int[] sum, List<Integer> sche) {
		int[] temp = new int[sum.length];
		for(int i=0;i<sche.size();i+=2) {
			int st = sche.get(i)*2-1;
			int ed = sche.get(i+1)*2;
			for(int j=st;j<ed;j++) {
				temp[j] = 1;
			}
		}
		for(int i=0;i<sum.length;i++) {
			sum[i] += temp[i];
		}
	}
}

Measured memory_bytes: 23124
class node():
    def __init__(self, data, child=None):
        self.child = child
        self.data = data

class head():
    def __init__(self, data):
        self.child = None
        self.length = 0
        for i in data:
            self.add(i)

    def add(self, i):
        self.child = node(i, child=self.child)
        self.length += 1
    
    def remove(self):
        idx = self.length
        root = self
        child = self.child
        while child is not None:
            if child.data == idx:
                root.child = child.child
                self.length -= 1
                return child.data
            idx -= 1
            root = child
            child = root.child

        return False

n = int(input())
data = list(map(int, input().split()))
linked = head(data)
ans = []
while True:
    step = linked.remove()
    if step is False:
        break
    ans.append(step)

if len(ans) != n:
    print(-1)
else:
    for a in reversed(ans):
        print(a)

Measured memory_bytes: 3064
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


def main():
    K = int(input())
    S = input().strip()
    if len(S) <= K:
        print(S)
    else:
        print(S[:K] + "...")


if __name__ == "__main__":
    main()



Measured memory_bytes: 9872
#include<iostream>
using namespace std;
 
bool isP(int x){
  if(x==0||x==1)return false;
  for(int i=2;i*i<=x;i++){
    if(x%i==0)return false;
  }
  return true;
}
 
int main(){
  int n,a,cnt=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    cnt+=isP(a);
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 1160
import sys
sys.setrecursionlimit(10**6)

N = int(input())
graph = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append([b, i])
    graph[b].append([a, i])

ans = [None]*(N-1)
def dfs(cur, p_color, p=-1):
    color = 1
    for (to, i) in graph[cur]:
        if to == p: continue
        if color == p_color:
            color = color+1
        ans[i] = color
        dfs(to, color, p=cur)
        color = color+1

dfs(0, -1)
print(max(ans))
[print(a) for a in ans]

Measured memory_bytes: 89324
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N,Usedtime=0,flag=0;
	cin >> N;
	vector<pair<int, int>> Todo(N);
	for (size_t i = 0; i < N; i++)
	{
		cin >> Todo.at(i).second >> Todo.at(i).first;
	}
	sort(Todo.begin(), Todo.end());
	for (size_t i = 0; i < N; i++)
	{
		Usedtime += Todo.at(i).second;
		if (Usedtime>Todo.at(i).first)
		{
			flag = 1;
			break;
		}
	}
	if (flag == 1) {
		cout << "No";
	}
	else {
		cout << "Yes";
	}
}

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

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

range1=[a,min(b,a+k-1)]
range2=[max(a,b-k+1),b]

if range1[1]>=range2[0]:
    for i in range(a,b+1):
        print(i)
else:
    for i in range(range1[0],range1[1]+1):
        print(i)
    for i in range(range2[0],range2[1]+1):
        print(i)


Measured memory_bytes: 3060
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
typedef long long lng;
typedef unsigned long long ulng;

#define pb push_back
#define SZ(a) int((a).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) FOR(i,0,n-1)
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

lng power(lng b, lng e) {lng sol=1; while(e>0) {if(e&1) {sol=sol*b;} e>>=1; b*= b;} return sol;}

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

    int N;
    cin >> N;
    vector<char> vc;
    REP(i, N) {
        char c;
        cin >> c;
        vc.pb(c);
    }
    sort(ALL(vc));
    UNIQUE(vc);
    if(SZ(vc) == 3) cout << "Three" << endl;
    else cout << "Four" << endl;
}


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

int main(){
    int x; cin>>x;
    int hako[101]={0};
    vector<int>d(x);
    for(int i=0;i<x;i++){
        cin>>d.at(i);
        hako[d.at(i)]=1;
        }
        int ans=0;
    for(int i=0;i<101;i++){
        ans+=hako[i];
        }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	
	public static void coloring(final int N, int curr, int parent, int parent_color, ArrayList<HashSet<Edge>> adj, int[] color) {
		int use_color = 0;

		for(final Edge edge : adj.get(curr)) {
			final int next = (edge.from == curr) ? edge.to : edge.from;

			if(next == parent) { continue; }
			if(parent_color == use_color) { use_color++; }
			
			color[edge.index] = use_color;
			coloring(N, next, curr, use_color, adj, color);
			use_color++;
		}
	}
	
	public static class Edge {
		int from, to, index;
		
		public Edge(int from, int to, int index) {
			this.from = from;
			this.to = to;
			this.index = index;
		}
	}
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			
			ArrayList<HashSet<Edge>> adj = new ArrayList<HashSet<Edge>>();
			for(int i = 0; i < N; i++) { adj.add(new HashSet<Edge>()); }
			for(int i = 0; i < N - 1; i++) {
				final int a = sc.nextInt() - 1;
				final int b = sc.nextInt() - 1;
				
				Edge fwd_edge = new Edge(a, b, i);
				Edge rev_edge = new Edge(b, a, i);
				
				adj.get(a).add(fwd_edge);
				adj.get(b).add(rev_edge);
			}
			
			int[] color = new int[N - 1];
			coloring(N, 0, -1, -1, adj, color);
			
			System.out.println(Arrays.stream(color).max().getAsInt() + 1);
			for(int i = 0; i < N - 1; i++) {
				System.out.println(color[i] + 1);
			}
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

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

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 94012
(
  stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map int |> fun x -> (x.[0], x.[1]),
  stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map int64
)
|> fun ((n, k), buildings) ->
  [0..((1 <<< (n - 1)) - 1)]
  |> List.map (
    fun candidates ->
      [0..(n - 2)]
      |> List.fold (
        fun (prev, num, cost) i ->
          buildings.[i + 1]
          |> fun cur ->
            if prev < cur
            then (cur, num + 1, cost)
            else (
              if candidates >>> i &&& 1 = 1
              then (prev + 1L, num + 1, cost + (prev - cur + 1L))
              else (prev, num, cost)
            )
      ) (buildings.[0], 1, 0L)
  )
  |> List.filter (fun (_, num, _) -> num >= k)
  |> List.map (fun (_, _, cost) -> cost)
  |> List.min
|> printfn "%d"


Measured memory_bytes: 20032
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

def main():
    N, X = map(int, input().split())
    x = list(map(int, input().split()))
    y = [abs(X-a) for a in x]
    cnt = set(make_divisors(min(y)))
    for d in y:
        tmp = []
        for c in cnt:
            if d%c == 0:
                tmp.append(c)
        cnt.intersection_update(set(tmp))
        if len(cnt) == 1:
            print(1)
            return
    ans = max(cnt)
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 14480
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        
        Scanner sc = new Scanner(System.in);
        int a=0;
        int b=0;
        int t=0;
        a=sc.nextInt();
        b=sc.nextInt();
        t=sc.nextInt();
        
        System.out.println(((int)(t+0.5)/a)*b);
    }
}


Measured memory_bytes: 25300
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E18;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);



int main(){fastio
    vector<ll> v;
    ll c=0;
    while(c<=10000){
        v.pb(pow(c,5));
        c++;
    }
    ll x;cin>>x;
    rep(i,0,v.size()-1){
        rep(j,0,v.size()-1){
            if(v[i]-v[j]==x){
                cout<<i<<' '<<j<<endl;
                return 0;
            }else if(v[i]+v[j]==x){
                cout<<i<<' '<<-j<<endl;
                return 0;
            }else if(-v[i]-v[j]==x){
                cout<<-i<<' '<<j<<endl;
                return 0;
            }else if(-v[i]+v[j]==x){
                cout<<-i<<' '<<-j<<endl;
                return 0;
            }
        }
    }
    
    return 0;
}


Measured memory_bytes: 4324
#include<bits/stdc++.h>
using namespace std;
#define ll        long long
#define  sci(x)   scanf("%d", &x)
#define  scl(x)   scanf("%lld", &x)
#define  scd(x)   scanf("%lf", &x)
#define l0(i,n)   for(ll i=0; i<n; i++)

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	//CODE TONOY
	int n;
	cin>>n;
	int sum=0;
	for (int i=1;i<=n;i++){
		sum+=i;
	}
	
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
Sin = input()
S = list(Sin)
S2 = list(Sin)
N = len(S)

if S[0] == "0":
    S[0] = "1"
else:
    S[0] = "0"

ans1 = 1    
for i in range(1, N):
    if S[i] == S[i-1]:
        if S[i-1] == "0":
            S[i] = "1"
        else:
            S[i] = "0"
        ans1 += 1

ans2 = 0
for i in range(1, N):
    if S2[i] == S2[i-1]:
        if S2[i-1] == "0":
            S2[i] = "1"
        else:
            S2[i] = "0"
        ans2 += 1

print(min(ans1, ans2))

Measured memory_bytes: 4852
#include<bits/stdc++.h>
#include <boost/rational.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
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; }

using namespace std;

int main(){
    ll N;
    cin >> N;
    ll X[N];

    rep(i, N){
        cin >> X[i];
    }

    ll ans = 100000000000000000;
    rep(i, 101){
        ll tmp = 0;
        rep(j, N){
            tmp += (X[j]-i)*(X[j]-i);
        }
        chmin(ans, tmp);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fst first
#define snd second
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std;
using lint = long long;
using ld = long double;

int main(void) {
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.rbegin(), t.rend());
    if (s < t) cout << "Yes";
    else cout << "No";
}

Measured memory_bytes: 256
import collections

n, k, q = map(int, input().split())

a = [int(input()) for _ in range(q)]

num_ans = collections.Counter(a)
# print(num_ans)

for i in range(1, n + 1):
    if i in num_ans:
        minus_point = q - num_ans[i]
    else:
        minus_point = q
    
    if k - minus_point > 0:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 11900
#include<bits/stdc++.h>
#define LL long long
#define MEM(x,y) memset(x,y,sizeof(x))
#define MOD(x) ((x)%mod)
#define mod 1000000007
#define pb push_back
#define STREAM_FAST ios::sync_with_stdio(false)

using namespace std;
const int maxn = 2e5+7;
struct node {int v,flow,nxt;}e[maxn];
int tot=1,head[maxn],dep[maxn];
// tot starting from 1
void add(int u,int v,int w)
{
    ++tot;
    e[tot].v=v;e[tot].flow=w;e[tot].nxt=head[u];
    head[u]=tot;
}

bool bfs(int S,int T)
{
    MEM(dep,0);
    dep[S]=1;
    queue<int>q;
    q.push(S);
    while (!q.empty())
    {
        int u=q.front();q.pop();
        for (int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if (e[i].flow && !dep[v])
            {
                dep[v]=dep[u]+1;
                q.push(e[i].v);
            }
        }
    }
    return dep[T];
}

int aim;
int dfs(int now,int flow)
{
    if (now==aim) return flow;
    int f=0;
    for (int i=head[now];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if (e[i].flow && dep[v]==dep[now]+1)
        {
            int x=dfs(v,min(flow,e[i].flow));
            e[i].flow-=x;e[i^1].flow+=x;flow-=x;f+=x;
        }
    }
    if (!f) dep[now]=-2;
    return f;
}

int maxflow(int S,int T)
{
    aim=T;int res=0;
    while (bfs(S,T)) res+=dfs(S,1<<30);
    return res;
}

int main()
{
    int n,m;scanf("%d%d",&n,&m);
    int S=1000,T=1001;
    
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            char c;scanf(" %c",&c);
            if (c=='o') 
            {
                add(i,j+n,1);add(j+n,i,1);
            }
            else if (c=='S')
            {
                add(S,i,1e8);add(i,S,0);
                add(S,j+n,1e8);add(j+n,S,0);
            }
            else if (c=='T')
            {
                add(i,T,1e8);add(T,i,0);
                add(j+n,T,1e8);add(T,j+n,0);
            }
        }
    }
    
    int ans=maxflow(S,T);
    printf("%d\n",ans>=1e8?-1:ans);
    
    return 0;
}


Measured memory_bytes: 1280
use std::cmp::*;
use std::collections::BTreeSet;
use std::io::*;
use std::str::FromStr;
//portable utility
#[allow(dead_code)]
fn switch<T>(flag: bool, true_value: T, false_value: T) -> T {
    if flag {
        true_value
    } else {
        false_value
    }
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn read_string() -> Vec<char> {
    read::<String>().chars().collect()
}

#[allow(dead_code)]
fn read_vector<T: FromStr>(number: i32) -> Vec<T> {
    (0..number).map(|_| read()).collect()
}

fn main() {
    let number = read_string();
    if number.iter().any(|c: &char| *c == '7') {
        println!("Yes");
    } else {
        println!("No");
    }
   
}


Measured memory_bytes: 2124
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <stdlib.h>
#include <set>
typedef long long ll;
using namespace std;

int main() {
	int a,b,h;
	cin>>a>>b>>h;
	cout<<(a+b)*h/2<<endl;
	return 0;
}


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

int	main()
{
  int n;
  cin >> n;
  vector<int> x(n);
  rep(i, n) cin >> x[i];
  int min = 100000000;
  rep(i , 100)
  {
    int dis = 0;
    rep(j, n)
    {
      dis += (x[j] - i) * (x[j] - i);
    }
    if(dis < min)
    {
      min = dis;
    }
  }
  cout << min << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <map>
#include <string>
typedef long long ll;
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string, int> s;
    for (int i = 0; i < n; i++) {
        string s1;
        cin >> s1;
        auto s2 = s.count(s1);
        if (s2==1) {
            s[s1] = s[s1] + 1;
        }
        else {
            s[s1] = 0;
        }
    }
    int max = 0;
    for(auto itr = s.begin(); itr!= s.end(); ++itr){
        if (max <= itr->second) {
            max = itr->second;
        }
    }
    for(auto itr = s.begin(); itr!= s.end(); ++itr){
        if (max == itr->second) {
            cout << itr->first << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 17664
N = int(input())
A = list(map(int,input().split()))
cur = [0 for i in range(N)]
ball = []
ball_num = 0
for x in range(N):
	i = N-1 - x
	n = i + 1
	if A[i] != cur[i]:
		ball.append(n)
		ball_num += 1
		for j in range(n // 2 + 1):
			m = j + 1
			if m * m > n:
				break
			if n % m == 0:
				cur[j] = 1 - cur[j]
				if n//m != m:
					cur[n//m - 1] = 1 - cur[n//m - 1]  
print(ball_num)
print(" ".join(list(map(str, ball))))

Measured memory_bytes: 78044
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int l, r, d, ans = 0;
    cin >> l >> r >> d;
    for(int i=l;i<=r;i++){
        if(i%d == 0) ans++;
    }
    cout << ans << "\n";
}

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

int main() {
    float a, b;
    cin >> a >> b;
    float x = (a + b) / 2;
    int integer = floor(x);
    float decimal = x - integer;
    if (decimal != 0) {
      cout << integer + 1 << endl;
    } else {
      cout << integer << endl;
    }
}


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

int main(){
	int n;

	cin >> n;
	int count = 1;
	long long b = 3;

	while(b < n){
		b *= 3;
		count++;
		//if(n <= 1){
		//	count++;
		//	break;
		//}
	}

	cout << count << endl;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (ll i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

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

  ll n;
  cin >> n;

  ll ans = 0;
  FOR(i, 1, n + 1) ans = (ans + i * (n + 1 - i));
  rep(i, n - 1) {
    ll u, v;
    cin >> u >> v;
    if (u > v) swap(u, v);
    ll res = u * (n + 1 - v);
    ans -= res;
  }
  cout << ans << '\n';

  




  
  return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define square(x) pow(x 2.0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define max_queue(x) priority_queue<x>
#define min_queue(x) priority_queue<x, vector<x>, greater<x>>
#define big_sort(v) sort(all(v), [](int a, int b) { return a > b; })//大きい順にソート
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
#define co(x) cout << x << endl;
#define cins(n,v) rep(i,n){cin >> v.at(i);}
#define couts(v) rep(i,v.size()){cout << v.at(i) << endl;}
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
/*
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
*/
int main() {
  srand((unsigned)time(NULL));
  int n;
  cin >> n;
  if(n>=30){
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3552
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define pvec(v) rep(i,v.size()){cout << v[i] << " ";};cout<<endl;
#define pb push_back
#define pf push_front
#define mod 1e9+7
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;

const double pi = acos(-1.0);
 
ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    ll n,k;
    string s;
    cin >> n >> s >> k;
    rep(i,n){
        if(s[i]==s[k-1]) cout << s[k-1];
        else cout << '*';
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
macro_rules! scan {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };

    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
}

fn main() {
    let (s1, s2, s3) = scan!(String, String, String);
    println!(
        "{}{}{}",
        s1.to_uppercase().chars().next().unwrap(),
        s2.to_uppercase().chars().next().unwrap(),
        s3.to_uppercase().chars().next().unwrap()
    )
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
const int N=25010;
const int mod=1e9+7;

int gi() {
	int x=0,o=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*o;
}

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

void inc(int &a,int b) {
	a=a+b>=mod?a+b-mod:a+b;
}

int n,k,m,mx,a[N],f[N][410],g[N][410];
bool vis[410],fl;

int main() {
	cin>>n>>k>>m;
	for(int i=1;i<=m;i++) {
		a[i]=gi();
		if(vis[a[i]]) fl=1;
		else vis[a[i]]=1;
	}
	int ans=1ll*(n-m+1)*qpow(k,n-m)%mod;
	for(int i=1;i+k-1<=m;i++) {
		memset(vis,0,sizeof(vis));
		bool fl2=1;
		for(int j=0;j<k;j++) {
			if(vis[a[i+j]]) { fl2=0;break; }
			vis[a[i+j]]=1;
		}
		if(fl2) return cout<<ans,0;
	}
	if(fl) {
		int fr=0,bk=0;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=m;i++) {
			if(!vis[a[i]]) ++fr,vis[a[i]]=1;
			else break;
		}
		memset(vis,0,sizeof(vis));
		for(int i=m;i;i--) {
			if(!vis[a[i]]) ++bk,vis[a[i]]=1;
			else break;
		}
		f[0][fr]=1,g[0][bk]=1;
		for(int i=1;i<=n;i++) {
			int s1=0,s2=0;
			for(int j=k-1;j;j--) {
				inc(s1,f[i-1][j]),inc(s2,g[i-1][j]);
				f[i][j]=(f[i][j]+1ll*f[i-1][j-1]*(k-j+1)+s1)%mod;
				g[i][j]=(g[i][j]+1ll*g[i-1][j-1]*(k-j+1)+s2)%mod;
			}
		}
		for(int i=0;i<=n-m;i++) {
			int s1=0,s2=0;
			for(int j=1;j<k;j++) inc(s1,f[i][j]),inc(s2,g[n-m-i][j]);
			inc(ans,mod-1ll*s1*s2%mod);
		}
	}
	else {
		f[0][0]=1;
		for(int i=1;i<=n;i++) {
			int s1=0,s2=0;
			for(int j=k-1;j;j--) {
				inc(s1,f[i-1][j]),inc(s2,g[i-1][j]);
				f[i][j]=(f[i][j]+1ll*f[i-1][j-1]*(k-j+1)+s1)%mod;
				g[i][j]=(g[i][j]+1ll*g[i-1][j-1]*(k-j+1)+s2)%mod;
				if(j>=m) inc(g[i][j],f[i][j]);
			}
		}
		int s=0;
		for(int i=1;i<k;i++) inc(s,g[n][i]);
		for(int i=k-m+1;i<=k;i++) s=1ll*s*qpow(i,mod-2)%mod;
		inc(ans,mod-s);
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 80384
#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;
long long mod(long long x){
    return (x%M);
    }
long long add(long long a, long long b){
        return mod(mod(a)+mod(b));
    }
long long mul(long long a, long long b){
        return mod(mod(a)*mod(b));
    }

int main()
{  int n;
cin>>n;
int a[n];
for(int i= 0;i<n;i++) cin>>a[i];
vector<long long> v(n+1);
for(int i = n-1;i>=0;i--){
    v[i] = v[i+1] + a[i];
    
}
long long ans = 0;
for(int i = 0;i<n;i++){
    ans = add(ans,mul(a[i],v[i+1]));
}
cout<<ans<<endl;
     
return 0;
   
}

Measured memory_bytes: 5532
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
#define ar array


int main()
{
	//#ifndef ONLINE_JUDGE
		//freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
	//#endif
	
	//int t;
	//cin>>t;
	//while(t--)
	{
		int n,k;
		cin>>n>>k;
		int a[n];
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
		}
		int dp[n];
		memset(dp,0x3f,sizeof(dp));
		dp[0]=0;
		for(int i=1;i<n;i++)
		{
			for(int j=1;j<=k;j++)
			{
				if(i-j>=0)
				{
					dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
				}
			}
		}
		cout<<dp[n-1]<<'\n';
		 
	}
		
}


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

int main(){
    map<string,int> dict;
    
    int n;
    cin>>n;
    
    rep(i,n){
        string s;
        cin>>s;
        dict[s]++;
    }
    
    int maxv=0;
    
    for(auto iter=dict.begin();iter!=dict.end();iter++){
        maxv=max(maxv,iter->second);
    }
    
    for(auto iter=dict.begin();iter!=dict.end();iter++){
        if(maxv==iter->second)
            cout<< iter->first<<endl;
    }
    
    return 0;
}

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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  //b,a
  ll a, b;
  cin >> a >> b;
  
  cout << (a-1) * (b-1) << "\n";

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cmath>
const int N=100010;
using namespace std;
int main()
{
  int n;
  cin>>n;
  int arr[N];
  int k;
  cin>>k;
  for(int i = 0 ;i < n;i++)
  {
    cin>>arr[i];}
    cout<<ceil((float)(n-1)/(k-1));

}


Measured memory_bytes: 640
#include<stdio.h>

#include<string.h>

int main(void){



 //int i;



 

 char str;



 

 while(1){

   scanf("%c", &str);
//printf("%s",str);
     if(str=='\n') break;

   //for(i=0;i<=strlen(str);i++){

   
      if(str>=97&&str<=122)

      str=str-32;

   

 

      else if(str>=65&&str<=90)

      str=str+32;



   //}

 printf("%c", str);

 

 }
 printf("\n");

 return 0;

}


Measured memory_bytes: 2048
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug1: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug2: "<<x<<" "<<y<<endl;
#define bug3(x, y, z) cout<<"zdongdebug3: "<<x<<" "<<y<<" "<<z<<endl;
using namespace std;
typedef long long ll;
const int maxn = 1005;
const int mod = 1000000007;

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  string a,b;
  cin>>a>>b;
  int ret = 0;
  for(int i=0;i<a.size();i++)if(a[i]!=b[i])ret++;
  cout<<ret<<endl;
  return 0;
}

Measured memory_bytes: 3916
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;

int main() {
#ifdef LOCAL_EXEC
//	freopen("sample.in", "r", stdin);
//	freopen("sample.out", "w", stdout);
#else
  ios_base::sync_with_stdio(false); cin.tie(NULL);
#endif

  int h, n; cin >> h >> n;
  while (n--) {
    int a; cin >> a;
    h -= a;
  }
  cout << (h <= 0 ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
int SelectionSort(vector<int> vi, int n)
{
  int i, min_index, j, flag;
  int times = 0;
  for(i=0; i<n-1; i++)
  {
    flag = 0;
    min_index = i;
    for(j=i+1; j<n; j++)
    {
      if(vi[j] < vi[min_index])
      {
        min_index = j;
        flag = 1;
      }
    }
    if(flag == 1)
      times++;
    swap(vi[i], vi[min_index]);
  }
  for(i=0; i<n; i++)
  {
    if(i) printf(" ");
    printf("%d", vi[i]);
  }
  printf("\n%d\n", times);
  return 0;
}
int main()
{
  int n;
  scanf("%d", &n);
  vector<int> vi;
  for(int i=0; i<n; i++)
  {
    int temp;
    scanf("%d", &temp);
    vi.push_back(temp);
  }
  SelectionSort(vi, n);
  return 0;
}



Measured memory_bytes: 3216