akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main(){
    map<string, ll> mp;
    ll q, c, x;
    string s;
    cin >> q;
    rep(i, q){
        cin >> c >> s;
        if(c == 0){
            cin >> x;
            auto t = mp.find(s);
            if(t == mp.end()){
                mp.insert(make_pair(s, x));
            }else{
                t->second = x;
            }
        }else{
            cout << mp.at(s) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 27732
/*                  ___
               :                
               ;                
              :                 
              ;                 
             /                  
           o/                   
         ._/\___,                
             \                  
             /                   
             `      
	bug
*/
#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

using namespace std;
#define PI 3.14159265359
#define eps 1e-8
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORN(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,n) FOR(i,0,n)
typedef long long int ll;
const int INF = 1<<29;
typedef long long ll;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

double tick() { 
	static clock_t oldticks;
	clock_t newticks = clock();
	double diff = 1.0 * (newticks - oldticks) / CLOCKS_PER_SEC; 
	oldticks = newticks;
	return diff;
}

inline int toInt(string s){
	return atoi(s.c_str());
}

inline int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

inline int lcm(int a,int b){
	return a*(b/gcd(a,b));
}

inline bool isPrime(int n){
	ll j;
	j=sqrt(n);

	if(n<2)
		return 0;
	for(int i=2;i<=j;i++){
		if(n%i==0)
			return false;
	}
	return true;
}

ll n,m;
map<int,int> M;

int main(){
	ios_base::sync_with_stdio(false); //Fast I/O
	cin.tie(NULL);
	//freopen("in.txt","r",stdin);
	//freopen("output.txt","w",stdout);	

	cin >> n >> m;
	M[0]++;

	int c=0;
	ll res=0;
	
	FORN(i,1,n){
		int x;
		cin >> x;
		c=(c+x)%m;
		res+=M[c]++;
	}

	cout << res << endl;

    //cerr << tick();

	return 0;
	
}


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

struct Edge{
    int to, id;//to:つながっている先 id:辺
};

vector<vector<Edge>> g;
vector<int> ans;

void dfs(int v, int c = -1, int p = -1){
    int k = 1;
    rep(i, g[v].size()){
        int u = g[v][i].to, ei = g[v][i].id;
        if(u == p) continue;
        if(k == c) k++;
        ans[ei] = k; k++;
        dfs(u, ans[ei], v);
    }
}

int main() {
    int n;
    cin >> n;
    g.resize(n);
    // ans = vector<int>(n-1);
    ans.resize(n-1);
    rep(i, n-1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back((Edge){b, i});
        g[b].push_back((Edge){a, i});
    }
    dfs(0);
    int mx = 0;
    rep(i, n) mx = max(mx, int(g[i].size()));
    cout << mx << endl;
    rep(i, n-1){
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 8320
use std::vec::Vec;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
  let v: Vec<T> = read_vec();
  assert_eq!(v.len(), 2);
  (v[0], v[1])
}

fn main() {
    let n: usize = read();
    let mut book = vec![];

    for _ in 0..n {
      let s: String = read();
      book.push(s);
    }

    book.sort();

    let mut count = split_same_element(&book);
    count.sort_by(|a, b| b.1.cmp(&a.1));
    
    let (_, m) = count[0].clone();

    for (s, c) in count {
      if c == m {
         println!("{}", s);
      }
    }
}


fn split_same_element<T: Eq + Clone>(v: &Vec<T>) -> Vec<(T, usize)> {
  let mut res: Vec<(T, usize)> = Vec::new();
  if v.len() == 0 {
    return res;
  }

  let mut now: T = v[0].clone();
  let mut count: usize = 0;
  for x in v {
    let e = x.clone();
    if e == now {
      count += 1;
    }
    else {
      res.push((now, count));
      count = 1;
      now = e;
    }
  }
  res.push((now, count));

  res
}

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

using namespace std;

int a[200001];

int main () {
	int n;
	cin >> n;
	for (int i = 1;i <= n + n;i ++) cin >> a[i];
	sort (a + 1, a + n + n + 1);
	int ans = 0;
	for (int i = 1;i <= n + n;i += 2) ans += a[i];
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define endl "\n"
#define MOD 1000000007
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    
    int n;
    cin >> n;
    int height[n+1];
    height[0]=0;
    for (int i=1;i<=n;i++)
    {
    	cin >> height[i];
    }

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

    return 0;
}

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


int main() {
  int n, t, a;
  cin >> n >> t >> a;
  vector<int> h(n);
  rep(i,n) cin >> h[i];
  int ans = -1;
  int mn = 1000000;
  rep(i,n){
    int d = a*1000-t*1000+h[i]*6;
    if(d<0) d = -d;
    if(d<mn) {
      mn = d;
      ans = i;
    }
  }
  cout << ans+1 << endl;   
  return 0;
}

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

using namespace std;

int main() {
    string weather;

    cin >> weather;

    if (weather == "Sunny") {
        cout << "Cloudy";
    } else if (weather == "Cloudy") {
        cout << "Rainy";
    } else {
        cout << "Sunny";
    }

    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from operator import itemgetter

def main():
	v = input().strip()
	v2 = input().strip()
	ans = 0
	for i in range(3):
		if v[i] == v2[i]:
			ans += 1
	print(ans)

if __name__ == '__main__':
	main()


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

// int/long:            -2,147,483,648 - 2,147,483,648 (-2^31 <= int < 2^31)
// long/long long:      -9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define INF (1<<29)
//536,870,912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

/*
int     gcd(int A, int B) {
        while (0!=B) {
                A %=B;
                swap(A, B);
        }
        return A;
}
*/

#define MOD 1000000007

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


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

const int MAX_N = 1e5 + 10;
const int MAX_Q = 1e5 + 10;

int ac_cnt[MAX_N], ans[MAX_Q];

int main() {
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    for (int i = 0; i < S.length() - 1; i++) {
        if (S[i] == 'A' && S[i + 1] == 'C') ac_cnt[i + 1]++;
        ac_cnt[i + 1] += ac_cnt[i];
    }
    int L, R;
    for (int i = 0; i < Q; i++) {
        cin >> L >> R;
        ans[i] = ac_cnt[R - 1] - ac_cnt[L - 1];
    }
    for (int i = 0; i < Q; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

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

using namespace std;

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
#define ll	long long
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())

int main() {
	string s;
	cin>>s;
	if(s[0] == s[1] && s[0] == s[2])
	{
		cout<<"No";
	}
	else cout<<"Yes";
	return 0;
}


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

int roundup(int init){
	//roundup 1000
	return (init + 999)/1000*1000;
}

//0007
int main(){
	const int initial = 100000;
	const int ratio_numerator = 105;
	const int ratio_denominator = 100;
	int weeks, term;

	cin >> weeks;

	//term = initial*(ratio**n)
	term = initial;
	for(int i=0; i<weeks; ++i){
		term = term * ratio_numerator / ratio_denominator;
		term = roundup(term);
	}

	cout << term << endl;
	return 0;
}

Measured memory_bytes: 0
using System;
class Program
{
    public static int Main()
    {
        string[] imp = Console.ReadLine().Split(' ');
        int h, w, d;
        h = int.Parse(imp[0]);
        w = int.Parse(imp[1]);
        d = int.Parse(imp[2]);
        int[,] a2 = new int[h * w, 2];
        for (int i = 0; i < h; i++)
        {
            imp = Console.ReadLine().Split(' ');
            for (int j = 0; j < w; j++)
            {
                a2[int.Parse(imp[j]) - 1, 0] = i;
                a2[int.Parse(imp[j]) - 1, 1] = j;
            }
        }
        int[] sum = new int[h * w];
        for (int i = 0; i < h * w; i++)
        {
            if (i < d)
                sum[i] = 0;
            else
                sum[i] = sum[i - d] + Math.Abs(a2[i, 0] - a2[i - d, 0]) + Math.Abs(a2[i, 1] - a2[i - d, 1]);
        }
        int q = int.Parse(Console.ReadLine());
        for (int i = 0; i < q; i++)
        {
            imp = Console.ReadLine().Split(' ');
            int l, r;
            l = int.Parse(imp[0]);
            r = int.Parse(imp[1]);
            Console.WriteLine(sum[r - 1] - sum[l - 1]);
        }
        return 0;
    }
}

Measured memory_bytes: 18176
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
t=[]
for i in d:
    t.append(d[i])
t.sort()
print(sum(t[0:-k]))

Measured memory_bytes: 33152
def win_state(arr)
  return false if arr.size % 3 != 0
  return true if arr.size == 0
  arr.permutation.to_a.any?{|k|
    k.each_slice(3).map{|a, b, c|
      (a.succ == c.pred && a.succ == b) || (a == c && a == b)
    }.all?
  }
end

t = gets.to_i
t.times do |i|
  n = gets.split.map(&:to_i)
  c = gets.split.map(&:to_s)
  r, g, b = [], [], []
  n.size.times do |j|
    r << n[j] if c[j] == "R"
    g << n[j] if c[j] == "G"
    b << n[j] if c[j] == "B"
  end
  res = [r, g, b].all?{|arr|
    win_state(arr)
  }
  p res ? 1 : 0
end

Measured memory_bytes: 75848
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

void printVector(vector<int> vec);

int main() {
	int H, A;
	cin >> H >> A;
	cout << ceil(double(H)/A) << endl;
}

void printVector(vector<int> vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> num(N);
  for (int i = 0; i < N; ++i) cin >> num.at(i);
  std::sort(num.begin(),num.end(),std::greater<int>());
  int Alice = 0;
  int Bob = 0;
  for(int i=0;i<N;i++){
    if(i%2==0){
      Alice+=num.at(i);
    }else{
      Bob+=num.at(i);
    }
  }
  int answer = Alice - Bob;
  cout << answer << endl;
}

Measured memory_bytes: 256
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

def main():
    x, y, z = map(int, input().split())
    print(x * y // 2)


main()


Measured memory_bytes: 64620
#include <bits/stdc++.h>
#define sp ' '
#define nyan "(=^・ω・^=)"
#define mkp make_pair
#define lP pair<ll,ll>
#define iP pair<int,int>

typedef long long ll;
using namespace std;
const int mod = 1e9 + 7;

int N, A[100], cnt, s;

int main(){
	cin >> N;
	for (int i = 0; i != N; ++i) {
		cin >> A[i];
		s += A[i];
	}
	if (s % 2 == 0) {
		cout << s / 2 << endl;
		return 0;
	}
	sort(A, A + N);
	for (int i = 0; i != N; ++i) {
		if (A[i] & 1 == 1) {
			cout << (s - A[i]) / 2 << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 3148
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    S = list(input())
    T = list(input())

    t = len(T)
    ans = INF
    for i in range(len(S)):
        s = S[i:i+t]
        if len(s) != t: break

        diff = 0
        for j in range(t):
            diff += s[j] != T[j]
        
        ans = min(ans,diff)

    print(ans)



if __name__ == "__main__":
    main()

Measured memory_bytes: 67160
n,q=map(int, input().split())
s=input()
lr = [list(map(int,input().split())) for _ in range(q)]

cumSum = [0]*(n+1)
pre = s[0]
cnt = 0
for i in range(1,n):
    now = s[i]
    if pre=="A" and now=="C":
        cnt += 1
    cumSum[i+1] = cnt
    pre = now
for l,r in lr:
    print(cumSum[r]-cumSum[l])

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

int main() {
  int a, b;
  cin >> a >> b;
  int ans;
  if (b % a == 0) {
    ans = a + b;
  } else {
    ans = b - a;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3544
import sys
sys.setrecursionlimit(10 ** 5)
def find(parent,i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent,t)
    parent[i] = t
    return t
def unite(parent,i,j):
    i = find(parent,i)
    j = find(parent,j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j
n,m = map(int,input().split())
parent = [-1] * n
ans = n*(n-1)//2
ansl = []
l0 = []
for i in range(m):
    ab = list(map(int,input().split()))
    ab[0] -= 1
    ab[1] -= 1
    l0.append(ab)
l0.reverse()
for i in range(m):
    ansl.append(ans)
    a,b = l0[i]
    if find(parent,a) != find(parent,b):
        ans -= parent[find(parent,a)] * parent[find(parent,b)]
    unite(parent,a,b)
ansl.reverse()
for i in range(m):
    print(ansl[i])

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

#define rep(i,N) for(int i=0;i<(int)(N);++i)
#define rrep(i,N) for(int i=(int)(N)-1;i>=0;--i)
#define debug(x) cout<<#x<<"="<<x<<endl;
constexpr int MOD=1000000007;
constexpr ll INF=(1LL<<61)-1;
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;}
template<typename T> void fail(T v){cout << v << endl;exit(0);}
//template end

void solve(){
    int N;
    while(cin>>N,N){
        ll res=0;
        for(int i=1;i*i<=N;i++){
            if(i*i==N)res++;
            for(int j=i;j*j<=N-i*i;j++){
                if(i*i+j*j==N)res++;
                for(int k=j;k*k<=N-i*i-j*j;k++){
                    if(i*i+j*j+k*k==N)res++;
                    for(int l=k;l*l<=N-i*i-j*j-k*k;l++){
                        if(i*i+j*j+k*k+l*l==N)res++;
                    }
                }
            }
        }
        cout<<res<<endl;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    solve();
    return 0;
}


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

#define fi first
#define se second
#define FO(x, n) for (int x = 0; x < n; ++x)
#define FOR(x, a, b) for (int x = a; x < b; ++x)
#define RFO(x, n) for (int x = n - 1; x >= 0; --x)
#define RFOR(x, a, b) for (int x = b - 1; x >= a; --x)
#define FOR_ITER(x, a) for(auto x = a.begin(); x != a.end(); ++x)

#define pb push_back
#define pf push_front
#define mp make_pair
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)


using namespace std;

typedef complex<double> P;
typedef unsigned char byte;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<string, string> pss;
typedef pair<ll, ll> pll;
inline bool feq(const double& a, const double& b) { return fabs(a - b) < 1e-10; }
inline int gcd(int a, int b) {
    if (b == 0) return a;
    return a < b? gcd(b, a) : gcd(b, a % b);
}
ll mo=1000000007;


int main(){
//    int n, l;
//    cin >> n >> k;
//    vector<bool> dislike(10, false);
//
//    FOR(i, 0, k) {
//        int t;
//        cin >> t;
//        dislike[t] = true;
//    }


    int a, b;

    cin >> a >> b;
    vector<pair<ll, ll> > v1(a);
    vector<pair<ll, ll> > v2(b);

    FO(i, a) {
        cin >> v1.at(i).fi
            >> v1.at(i).se;
    }
    FO(i, b) {
        cin >> v2.at(i).fi
            >> v2.at(i).se;
    }


    FO(i, a) {
        ll minD = 1e11;
        ll idx = -1;
        ll x1 = v1.at(i).fi;
        ll y1 = v1.at(i).se;

        FO(j, b) {
            ll x2 = v2.at(j).fi;
            ll y2 = v2.at(j).se;

            ll dis = abs(x1 - x2) + abs(y1 - y2);
            if (dis < minD) {
                idx = j + 1;
                minD = dis;
            }
        }
        cout << idx << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    int xi[6]={1,2,3,4,5,6};
    int sum;
    char nowcomand[6],comand[6][6]={{"North"},{"East"},{"West"},{"South"},{"Right"},{"Left"}};
    while(1){
        scanf("%d",&n);
        if(n==0)
            break;
        sum=0;
        for(int i=0;i<6;i++)
            xi[i]=i+1;
        for(int i=0;i<n;i++){
            scanf("%s",nowcomand);
            if(!strcmp(nowcomand,comand[0]))
                swap(xi[0],xi[1]),swap(xi[1],xi[5]),swap(xi[5],xi[4]);
            else if(!strcmp(nowcomand,comand[1]))
                swap(xi[0],xi[3]),swap(xi[3],xi[5]),swap(xi[5],xi[2]);
            else if(!strcmp(nowcomand,comand[2]))
                swap(xi[0],xi[2]),swap(xi[2],xi[5]),swap(xi[5],xi[3]);
            else if(!strcmp(nowcomand,comand[3]))
                swap(xi[0],xi[4]),swap(xi[4],xi[5]),swap(xi[5],xi[1]);
            else if(!strcmp(nowcomand,comand[4]))
                swap(xi[1],xi[2]),swap(xi[2],xi[4]),swap(xi[4],xi[3]);
            else
                swap(xi[1],xi[3]),swap(xi[3],xi[4]),swap(xi[4],xi[2]);
            sum+=xi[0];
        }
        printf("%d\n",sum+1);
    }
    return 0;
}

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

int main() {
	int n;
	cin >> n;
	vector<long long int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a.at(i);
	}

	for (int i = 0; i < n; i++) {
		if (a.at(i) == 0) {
			cout << 0 << endl;
			return 0;
		}
	}

	bool x = true;

	long long int ans = 1;
	for (int i = 0; i < n; i++) {
		if (ans > 1000000000000000000 || 1000000000000000000 / ans < a.at(i)) {
			x = false;
			break;
		}
		ans = ans * a.at(i);
	}

	if (x == false) {
		cout << -1 << endl;
	}
	else {
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 4048
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var: ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        x: [i64; n],
    }
    let mut ans = 0;
    for i in 1..n - 1 {
        if (x[i] > x[i - 1] && x[i] < x[i + 1]) || (x[i] < x[i - 1] && x[i] > x[i + 1]) {
            ans += 1;
        }
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 100005;
/* global variables */
vector< vector<pii> > Adj(MAX);
vector<int> d(MAX, -INF);
bool can = true;
/* function */
void bfs(int u);

/* main */
int main() {

    int V, E, v, u, w;
    cin >> V >> E;

    for (int i = 0; i < E; i++) {
        cin >> v >> u >> w;
        Adj[v].push_back(pii(u, w));
        Adj[u].push_back(pii(v, -w));
    }

    for (int u = 0; u < V; u++) if (d[u] == -INF) bfs(u);

    cout << (can ? "Yes" : "No") << '\n';
}

void bfs(int u) {
    queue<int> Q;
    int s, t;
    Q.push(u);
    d[u] = 0;
    while (!Q.empty()) {
        s = Q.front();
        Q.pop();
        for (pii p : Adj[s]) {
            int t = p.first, w = p.second;
            if (d[t] == -INF) {
                d[t] = d[s] + w;
                Q.push(t);
            }
            else if (d[t] != d[s] + w) can = false;
        }
    }
}

Measured memory_bytes: 9344
#include <iostream>

#define N 100005

int main(void){
  int n, t;
  int A[N];

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

  int start=0, end=0, gain=0, count=1;
  for(int i=1; i<n; i++){
    if(gain < A[i] - A[start]){
      end = i;
      gain = A[i] - A[start];
      count = 1;
    }else if(gain == A[i] - A[start]){
      count++;
    }else if(A[i] - A[start] < 0){
      start = i;
    }
  }

  std::cout << count << std::endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main()
{
  long long N;
  cin >> N;
  vector<ll> P(N);
  for (int i = 0; i < N; i++)
  {
    cin >> P.at(i);
  }
  ll ans = 0;
  ll mini = 50000000;
  for (int i = 0; i < N; i++)
  {
    if (P.at(i) <= mini)
    {
      ans++;
      mini = min(mini, P.at(i));
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>


using namespace std;

vector<int> order{ 0,1,2,3 };


int main(){
	long X, t;
	cin >> X >> t;
	if (X <= t) {
		cout << "0" << endl;
	}
	else {
		cout << X - t << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(){
	char r[128],m,s;
	int i,k=0;
	scanf("%s",r);
	m='A';
	for(i=0;i<strlen(r);i++){
		s=r[i];
		if(s-m<=0){
			k++;
		}
		m=s;
	}
	printf("%d\n",k);
    return 0;
}

Measured memory_bytes: 2732
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include<queue>
#include <sstream>
#include <set>
#include<stack>

const long long MOD = 1000000007;
using namespace std;
typedef long long llong;

//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//size()	文字数を返す
//Insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//c_str()変換
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());
//map<type, type> dict;で宣言
//グラフ理論用変数
//vector<vector<llong> > graph(N);

//ソート
//降順sort(v.begin(), v.end(), std::greater<Type>());

//大文字から小文字へんかん
//w[i] = w[i]-'A'+'a';

//vector
//assignメソッド　引数：サイズ、値
//与えられたサイズと値でvectorを初期化する

//queueクラス
//find()次に取り出す値の表示をする。
//pop()値を取り出す。戻り値はなし
//push()キューに値をプッシュする

//priority_queueクラス

//切り上げ
//ceil
//floor

int main(){
    llong N;
    cin >> N;
    for(int i=1; i<=N; i++){
        if(N==floor(i*1.08)){
            cout << i << endl;
            exit(0);
        }
    }
    cout <<  ":(" << endl;
    return 0;
}


Measured memory_bytes: 3172
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, int> LP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h, w;
	cin >> h >> w;
	vector<string> s(h);
	rep(i,h) cin >> s[i];
	rep(j,w+2) cout << "#";
	cout << endl;
	rep(i,h){
		cout << "#" << s[i] << "#" << endl;
	}
	rep(j,w+2) cout << "#";
	cout << endl;
	return 0;
}

Measured memory_bytes: 3664
n,m = map(int, input().split())

sc = [tuple(map(int, input().split())) for _ in range(m)]

for i in range(1000):
    
    k = str(i)
    
    if len(k) == n and all([k[s-1]==str(c) for s,c in sc]):
        print(k)
        exit()

print(-1)

Measured memory_bytes: 3064
n=int(input())
p=list(map(int,input().split()))
count=0
for i in range(1,n-1):
  if(p[i]>p[i-1] and p[i]<p[i+1]):
    count+=1
     
  if(p[i]<p[i-1] and p[i]>p[i+1]):
     count+=1
print(count)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vector<ll>>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double pi=3.14159265358979323846;
bool chmin(auto &a,auto b){if(a>b){a=b;return true;}return false;}
bool chmax(auto &a,auto b){if(a<b){a=b;return true;}return false;}
void outvi(vi v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
void outvvi(vvi v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<endl;}}
int main(){
    ll a,b,k;cin>>a>>b>>k;
    if(k<=a)a-=k;
    else{
        k-=a;
        a=0;
        if(b<=k)b=0;
        else b-=k;
    }
    cout<<a<<' '<<b<<endl;
}

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

int main() {
  int r, c;
  cin >> r >> c;
  vector<vector<int>> table(r + 1, vector<int>(c + 1, 0));
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      cin >> table.at(i).at(j);
    }
  }

  for (int i = 0; i < c; i++) {
    for (int j = 0; j < r; j++) {
      table.at(r).at(i) += table.at(j).at(i);
    }
  }

  for (int i = 0; i < r + 1; i++) {
    table.at(i).at(c) = accumulate(table.at(i).begin(), table.at(i).end(), 0);
  }

  for (size_t i = 0; i < r + 1; i++) {
    for (size_t j = 0; j < c + 1; j++) {
      if (j != c) {
        cout << table.at(i).at(j) << ' ';
      } else {
        cout << table.at(i).at(j);
      }
    }
    cout << endl;
  }
}



Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long  k,a,b; cin>>k>>a>>b;
    long long ans=0;
    if(b-a>2){
        if(k>=a+1){
            if((k-a+1)%2 == 0){
                ans=a+(b-a)*((k-a+1)/2);
            }else{
                ans=a+(b-a)*((k-a+1)/2)+1;
            }
        }else{
            cout<<k+1<<endl; return 0;
        }
    }else{
        cout<<k+1<<endl; return 0;
    }
    if(k+1>=ans)
        cout<<k+1<<endl;
    else cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define mes(a, b) memset(a, b, sizeof a)
#define pb push_back
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 2e6+10;
const double eps = 1e-1;
int n, in[maxn], x;
int main(){
    scanf("%d", &n);
    for(int i =1; i < n; i++)
        scanf("%d", &x), in[x]++;
    for(int i = 1; i <= n; i++)
        printf("%d\n", in[i]);
    return 0;
}


Measured memory_bytes: 3872
use std::fmt;
use std::io::stdin;
use std::io::BufRead;
use std::str;
use std::str::FromStr;
use std::vec::Vec;

fn main() {
    let stdin = stdin();
    let mut scan = InputScanner::new(stdin.lock(),256);

    let _:usize = scan.next();
    let m:usize = scan.next();

    let mut ab:Vec<(usize,usize)> = (0..m).map(|_| (scan.next(),scan.next())).collect::<Vec<(usize,usize)>>();

    ab.sort_by(|a,b| (a.1.cmp(&b.1)));

    let mut count = 0;

    let mut cur = 0;

    for ab in &ab {
        if cur == 0 || cur <= ab.0 {
            count += 1;
            cur = ab.1;
        }
    }

    println!("{}",count);
}
struct InputScanner<R: BufRead> {
	reader: R,
	buf: Vec<u8>, // Should never be empty
	pos: usize,   // Should never be out of bounds as long as the input ends with '\n'
}
impl<R: BufRead> InputScanner<R> {
	fn new(reader: R, capacity: usize) -> Self {
		InputScanner {
			reader: reader,
			buf: Vec::with_capacity(capacity),
			pos: 0,
		}
	}

	#[inline]
	fn next<T: FromStr>(&mut self) -> T
	where
		T::Err: fmt::Debug,
	{
		if self.buf.is_empty() {
			self._read_next_line();
		}
		let mut start = None;
		loop {
			match (self.buf[self.pos], start.is_some()) {
				(b' ', true) | (b'\n', true) | (b'\r', true) => break,
				(_, true) | (b' ', false) => self.pos += 1,
				(b'\n', false) | (b'\r', false) => self._read_next_line(),
				(_, false) => start = Some(self.pos),
			}
		}
		let target = &self.buf[start.unwrap()..self.pos];
		unsafe { str::from_utf8_unchecked(target) }.parse().unwrap()
	}

	#[inline]
	fn _read_next_line(&mut self) {
		self.pos = 0;
		self.buf.clear();
		if self.reader.read_until(b'\n', &mut self.buf).unwrap() == 0 {
			panic!("Reached EOF");
		}
	}
}


Measured memory_bytes: 6396
n = int(input())
ans = n/1.08
# print(ans)
import math
ans1 = math.floor(ans)
ans2 = math.ceil(ans)
# print(ans1,ans2)
if math.floor(ans1*1.08) == n or math.floor(ans2*1.08) == n:
	if math.floor(ans1*1.08) == n:
		print(ans1)
	else:
		print(ans2)
else:
	print(":(")

Measured memory_bytes: 3060
n = int(input())
pyramid = []

sx, sy, sh = 0, 0, 0

for _ in range(n):
    x, y, h = map(int, input().split())
    pyramid.append([x, y, h])
    if h > 0:
        sx, sy, sh = x, y, h

for cx in range(101):
    for cy in range(101):
        candidate = abs(sx-cx) + abs(sy-cy) + sh
        check = True

        for x, y, h in pyramid:
            H = abs(x-cx) + abs(y-cy) + h
            if h > 0:
                if candidate != H:
                    check = False
                    break
            else:
                if candidate > H:
                    check = False
                    break

        if check:
            print(cx, cy, candidate)
            exit()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

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

    ll N;
    cin>>N;

    ll M = 0;
    ll cnt = 0;
    ll cur;
    cin>>cur;
    rep(i, N - 1) {
        ll h;
        cin>>h;

        if (h <= cur) cnt++;
        else {
            M = max(M, cnt);
            cnt = 0;
        }
        cur = h;
    }
    M = max(M, cnt);
    cout<<M<<endl;
}

Measured memory_bytes: 256
from collections import defaultdict
s = input()
cnt = defaultdict(int)
for i in range(len(s)):
    cnt[s[i]] += 1
mean = len(s) // 3
for t in ["a", "b", "c"]:
    if cnt[t] != mean and cnt[t] != mean + 1:
        print("NO")
        exit()

print("YES")

Measured memory_bytes: 3444
N,M,K=map(int,input().split())
P=1000000007
import math
ans=M**2*(N-1)*N*(N+1)//6
ans+=N**2*(M-1)*M*(M+1)//6
print(ans*math.factorial(N*M-2)*pow(math.factorial(K-2),P-2,P)*pow(math.factorial(N*M-K),P-2,P)%P)


Measured memory_bytes: 100968
//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

int A[100];

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

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

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

	int cnt = 0;
	for (int i=0; i<N; i++) {
		if (A[i] * 4 * M >= total) cnt++;
	}

	string ans;

	if (cnt >= M) ans = "Yes";
	else ans = "No";

	cout << ans << endl;

	return 0;
}

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

using namespace std;
int n,q;
int niz[100050];
int bit[100050];
void update(int a, int b)
{
    while(a<=n)
    {
        bit[a]+=b;
        a=a+(a&-a);
    }
}
int query(int a)
{
    int res=0;
    while(a>0)
    {
        res+=bit[a];
        a=a-(a&-a);
    }
    return res;
}
int main()
{
    cin>>n>>q;
    while(q--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a==0)
            update(b,c);
        else
            cout<<query(c)-query(b-1)<<endl;
    }
    return 0;
}

Measured memory_bytes: 3460
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int k, x;
    cin >> k >> x;
    for (int i = x - k + 1; i < x + k; i++) {
        cout << i << " \n"[i + 1 == x + k];
    }
    return 0;
}


Measured memory_bytes: 256
class Segtree
  attr_reader :dat
  def initialize(n)
    @n = 1
    while @n < n
      @n *= 2
    end
    @dat = {}
  
    (@n * 2 - 1).times do |i|
      # @dat[i] = Float::INFINITY
      @dat[i] = 0
    end
  end

  # k番目(0-indexed)の値をaに変更
  # def update(k, a)
  #   k += @n - 1
  #   @dat[k] = a

  #   while k > 0
  #     k = (k - 1) / 2
  #     @dat[k] = [@dat[k * 2 + 1], @dat[k * 2 + 2]].min
  #   end
  # end
  def update(k, a)
    k += @n - 1
    @dat[k] = a

    while k > 0
      k = (k - 1) / 2
      @dat[k] = @dat[k * 2 + 1].gcd(@dat[k * 2 + 2])
    end
  end

  # [a, b)の最小値を求める
  def query(a, b, k = 0,l = 0, r = @n)
    return Float::INFINITY if r <= a || b <= l
    return @dat[k] if a <= l && r <= b
    vl = query(a,b,k * 2 + 1, l, (l + r) / 2)
    vr = query(a,b,k * 2 + 2, (l + r) / 2, r)
    [vl, vr].min
  end
end

n = gets.to_i
as = gets.split.map(&:to_i)
if n.odd?
  s = Segtree.new(n+1)
else
  s = Segtree.new(n)
end

as.each.with_index do |a,i|
  s.update(i,a)
end

ans = 1
as.each.with_index do |a,i|
  s.update(i,0)
  ans = [ans, s.dat[0]].max
  s.update(i,a)
end

puts ans


Measured memory_bytes: 28044
using System;
using System.Linq;

class A
{
	static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
	static void Main() => Console.WriteLine(string.Join("\n", new int[int.Parse(Console.ReadLine())].Select(_ => Solve())));

	static long Solve()
	{
		var h = Read();
		V p0 = new V(h[0], h[1]), p1 = new V(h[2], h[3]), p2 = new V(h[4], h[5]), p3 = new V(h[6], h[7]);
		V s1 = p1 - p0, s2 = p3 - p2;

		return V.IsParallel(s1, s2) ? 2 : V.IsOrthogonal(s1, s2) ? 1 : 0;
	}
}

struct V
{
	public int X, Y;
	public V(int x, int y) { X = x; Y = y; }

	public static V operator -(V v) => new V(-v.X, -v.Y);
	public static V operator +(V v1, V v2) => new V(v1.X + v2.X, v1.Y + v2.Y);
	public static V operator -(V v1, V v2) => new V(v1.X - v2.X, v1.Y - v2.Y);

	public static bool IsParallel(V v1, V v2) => v1.X * v2.Y == v2.X * v1.Y;
	public static bool IsOrthogonal(V v1, V v2) => v1.X * v2.X == -v1.Y * v2.Y;
}



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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 200010;
char A[MC];
bool b[MC][26];
int c[MC];
stack<int> S;

int main(){
	scanf("%s" , A);
	int n = 0;
	for(; A[n] != 0 ; ++n);
	repp(i,0,26) b[n][i] = 0;
	c[n] = 0;
	S.push(n);
	repm(i,n-1,-1){
		c[i] = 26;
		repm(j,25,-1){
			b[i][j] = (b[i+1][j] || A[i] == 'a' + j);
			if(!b[i][j]) c[i] = j;
		}
		if(c[i] == 26){
			S.push(i);
			repp(j,0,26) b[i][j] = 0;
			c[i] = 0;
		}
	}
	printf("%c" , c[0] + 'a');
	S.pop();
	int x = 0;
	char p = c[0] + 'a';
	bool z[26];
	while(!S.empty()){
		while(A[x] != p) ++x;
		int y = S.top(); S.pop();
		fill(z,z+26,0);
		repp(i,x+1,y) z[A[i]-'a'] = 1;
		repp(i,0,26){
			if(z[i]) continue;
			p = 'a' + i;
			break;
		}
		printf("%c" , p);
		x = y;
	}
	printf("\n");
	return 0;
}


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

class Program {
	static void Main() {
		var K = NextLong();
		var S = NextLong();
		var ans = 0;

		for (var x = 0; x <= K; x++) {
			for (var y = 0; y <= K; y++) {
				var z = S - x - y;
				if (0 <= z && z <= K) {
					ans++;
				}
			}
		}
		WriteLine(ans);
	}

	static long NextLong() {
		return long.Parse(NextString());
	}

	static string NextString() {
		var result = new List<char>();
		while (true) {
			int next = Read();
			if (next < 0)
				break;
			var nextChar = (char)next;
			if (!char.IsWhiteSpace(nextChar))
				result.Add(nextChar);
			else if (nextChar != '\r')
				break;
		}
		return string.Join("", result);
	}
}


Measured memory_bytes: 13268
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define INT(x) int x; scanf("%d",&x)
#define INPUT(x) scanf("%d",&x)
#define REP1(x,n) for(int x = 0; x < n; x++)
#define REP2(x,s,e) for(int x = s; x <= e; x++)
#define RREP1(x,n) for(int x = n-1; x >= 0; x--)
#define RREP2(x,s,e) for(int x = s; x >= e; x--)
#define BR printf("\n")
#define INF 2000000000

typedef long long ll;

int pow(int p, int q){//p^q
    int x = 1;
    while (q > 0) {
        if (q&1) x *= p;
        p = p*p;
        q >>= 1;
    }
    return x;
}

int main(){
    INT(n);INT(k);
    int x = k*pow(k-1,n-1);
    cout << x << endl;
}

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

int main()
{
	int n,min,k;
    cin>>n;
    for(int i=1;i<=10;i++)
    {
        k=i*1000;
      if(k>=n)
      {
        min=k-n;
        break;
      }
    }
    cout<<min;
	return 0;
}

Measured memory_bytes: 3624
#include<vector>
#include<string>
#include<algorithm>
#include<iomanip>
#include<map>
#include<cmath>
#include<iostream>
using namespace std;

int main()
{
    int n;
   
    int t;
   
    
    {
        cin>> t;
        int *arr = new int[t];
        for(int i = 0; i < t; i++)
            cin >> arr[i];
        sort(arr,arr+t);

//        for(int i = 0; i < t; i++)
//            cout << " " << arr[i];
//        cout << endl;
        int cnt = 0;
        for(int i = 0; i < t- 2; i++)
        {

            for(int j = i+1; j < t-1; j++)
            {
                int temp = arr[i] +arr[j];
                int k;
                for( k = t-1; k >= j+1; k--)
                {
                    if(arr[k] < temp)
                    {
//                        cout << arr[k] <<" " << arr[i] << " " << arr[j] << " " << k <<"\n";
                        break;
                    }
                }
                cnt += (k - j);
            }
        }

    cout << cnt;
        delete[] arr;
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int array[500000];
int a[200000];

int main(void){
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; ++i) {
		scanf("%d", &a[i]);
	}
	int left=200000;
	int right=left+1;
	for(int i=0; i<n; ++i) {
		if(i%2==(n-1)%2) {
			array[left--]=a[i];
		} else {
			array[right++]=a[i];
		}
	}
	for(int i=left+1; i<right; ++i) {
		printf("%d ", array[i]);
	}
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    ll a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    ll ans[n];
    ll l=-3,r=2*a[0];
    while(true){
        ll mid=(r+l+1)/2;
        if(mid<0)mid=-mid;
        if(mid%2==1){
            mid++;
        }
        ans[0]=mid;
        for(int j=1; j<n; j++){
            ans[j]=a[j-1]-ans[j-1]/2;
            ans[j]*=2;
        }
        if((ans[0]+ans[n-1])/2==a[n-1])break;
        else if((ans[0]+ans[n-1])/2<a[n-1])l=mid;
        else r=mid;
    }
    for(int i=0; i<n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
}

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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

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;}

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
    int n; cin >> n;
    vector<int> lis(n);
    int ans = 0;
    REP(i, 0, n){cin >> lis[i];}
    REP(i, 1, n){
        if(lis[i-1] == lis[i]){
            lis[i] = -1;
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
using System;

class Program
{
    static public void Main(string[] args)
    {
        long ans = 0;
        string[] input = Console.ReadLine().Split(' ');
        int n = int.Parse(input[0]);
        int a = int.Parse(input[1]);
        int b = int.Parse(input[2]);

        int[] x = new int[n];
        input = Console.ReadLine().Split(' ');

        for(int i = 0; i < n; i++)
        {
            x[i] = int.Parse(input[i]);
        }

        for(int i = 1; i < n; i++)
        {
            ans += Math.Min((long)a*(x[i]-x[i-1]),b);
        }

        Console.WriteLine(ans);

    }
}

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

void printArray(int A[], size_t N) {
    for (int i = 0; i < N - 1; i++) {
        cout << A[i] << " ";
    }
    cout << A[N - 1] << endl;
}

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

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

    for (int i = 1; i <= N - 1; i++) {
        printArray(A, N);

        int v = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > v) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = v;

    }

    printArray(A, N);

    return 0;
}


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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i, a, b) for (int i = (a) ; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;

void TimeExecution() {
    cout << "\n\n===>> Time Execution: " << clock() / (double)1000 << " sec(s).";
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    /*
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    */
    int n;
    cin >> n;
    int h[n + 1];
    h[0] = 0;
    FOR(i, 1, n)
        cin >> h[i];
    if(n == 1)
    {
        cout << "Yes";
        return 0;
    }
    bool ok = 1;
    FOR(i, 1, n - 1)
    {
        if(h[i] == h[i - 1] && h[i] <= h[i + 1]) continue;
        if(h[i] - 1 <= h[i + 1] && h[i] - 1 >= h[i - 1]) h[i]--;
        else
        {
           // cout << i << endl;
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, int> Pair;
const int maxn = 2000 + 7;

int n;
vector<Pair> o;
long long f[maxn][maxn];

long long dp(int x, int y) {
    if (x > y) return 0;
    if (f[x][y] != -1) return f[x][y];

    int u = y - x;
    f[x][y] = max(o[u].first * abs(o[u].second - x) + dp(x + 1, y), 
                  o[u].first * abs(o[u].second - y) + dp(x, y - 1));
    return f[x][y];
}

int main() {
    scanf("%d", &n);
    for (int i = 1, v; i <= n; i++) {
        scanf("%d", &v);    
        o.push_back({v, i});
    }

    sort(o.begin(), o.end());
    memset(f, -1, sizeof(f));

    cout << dp(1, n) << endl;
    return 0;
}


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

const int32_t MAX_N = 1000;
const int32_t MAX_M = 1000;
const int32_t MOD = 1e9 + 7;

char board[MAX_N + 5][MAX_M + 5];
int32_t dp[MAX_N + 5][MAX_M + 5];

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

	int32_t n, m;
	std::cin >> n >> m;

	for(int32_t i = 0; i < n; i++) {
		for(int32_t j = 0; j < m; j++) {
			std::cin >> board[i][j];
		}
	}

	dp[0][0] = 1;
	for(int32_t i = 0; i < n; i++) {
		for(int32_t j = 0; j < m; j++) {
			if(i == 0 && j == 0) {
				continue;
			}

			if(i == 0) {
				dp[i][j] = dp[i][j - 1];
			}
			else if(j == 0) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = ((int64_t) dp[i - 1][j] + dp[i][j - 1]) % MOD;
			}

			if(board[i][j] == '#') {
				dp[i][j] = 0;
			}
		}
	}

	std::cout << dp[n - 1][m - 1] << '\n';
}



Measured memory_bytes: 5248
from math import sqrt

def distance(p, q):
    return sqrt((p[0]-q[0])*(p[0]-q[0])+(p[1]-q[1])*(p[1]-q[1]))

def main():
    n = int(input())
    p_array = []
    s = 0
    for i in range(n):
        p = list(map(int, input().split(' ')))
        for q in p_array:
            s += distance(p, q)
        p_array.append(p)
    return 2*s/n

if __name__ == "__main__":
    print(main())

Measured memory_bytes: 3064