akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef pair<int,int> P;
typedef pair<P,int> P1;

map<P1,int> memo;
string s;

int dfs(int l, int r, int flag){
  
  if( memo.count(P1(P(l,r),flag)) ) return memo[P1(P(l,r),flag)];
  
  int L = l, R = r;
  
  int cnt = 0;
  
  for(int i=L;i<=R;i++){
    if( '0' <= s[i] && s[i] <= '9' ) cnt++;
  }
  
  if( cnt == 1 ){
    if( R - L + 1 == 1 ) return memo[P1(P(L,R),flag)] = s[L] - '0';
    else return memo[P1(P(L,R),flag)] = flag == 0 ? -1e9 : 1e9;
  }
  
  while( s[L] == '(' ) L++;
  
  while( s[R] == ')' ) R--;
  
  int res = flag == 0 ? -1e9 : 1e9;
  
  for(int i=L;i<=R;i++){
    
    if( s[i] == '+' ){
      int A = dfs( L, i - 1, flag );
      int B = dfs( i + 1, R, flag );
      if( flag == 0 ) res = max( res, A + B );
      else res = min( res, A + B );
    }
    
    if( s[i] == '-' ){
      int A = dfs( L, i - 1, flag );
      int B = dfs( i + 1, R, !flag );
      if( flag == 0 ) res = max( res, A - B );
      else res = min( res, A - B );
    }
    
  }
  
  return memo[P1(P(l,r),flag)] = res;
}

signed main(){
  
  cin>>s;
  
  cout<<dfs(0,(int)s.size()-1,0)<<endl;
  
  return 0;
}



Measured memory_bytes: 3936
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}

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

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

int main()
{
    vector<int> a(9);
    bool flag = true;
    for (int i = 0; i < 9; i++)
    {
        cin >> a[i];
    }
    if (a[1] - a[0] == a[4] - a[3] && a[4] - a[3] == a[7] - a[6])
    {
        if (a[2] - a[1] == a[5] - a[4] && a[5] - a[4] == a[8] - a[7])
        {
            cout << "Yes" << endl;
            flag = false;
        }
    }
    if (flag)
    {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef  unsigned long long int ull;
typedef pair<ll,ll> P;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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(){
   ll x,y,z,k;
   cin>>x>>y>>z>>k;
 V<ll> a(x),b(y),c(z);
 for(int i=0;i<x;i++)cin>>a[i];
 for(int i=0;i<y;i++)cin>>b[i];
 for(int i=0;i<z;i++)cin>>c[i];
 V<ll> d(x*y);
 ll cnt=0;
 for(int i=0;i<x;i++)for(int j=0;j<y;j++)d[cnt++]=a[i]+b[j];
 sort(all(d),greater<ll>());
 sort(all(c));
 V<ll> val;
 for(int i=0;i<min(k,cnt);i++){
    for(int j=0;j<z;j++){
       val.emplace_back(d[i]+c[j]);
    }
 }
 sort(all(val),greater<ll>());
 for(int i=0;i<k;i++){
    cout<<val[i]<<"\n";
 }
}
    

Measured memory_bytes: 42984
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)*}
    };
}

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

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, i321) => {
        read_value!($next, i32) - 1
    };

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

//
// # Examples
//
// # integers
// input! { n: i32, m: i32, ... }
//
// # array
// input! { n: i32, v: [i32; n], }
//
// # matrix
// input! { n: i32, m: i32, mat: [[]] }
//
// # string
// input! { s: chars }
//
// 3 4
// ####
// #..#
// .#.#
//
// input!{
//     h: i32,
//     w: i32,
//     board: [chars; h],
// }

// https://practice.contest.atcoder.jp/tasks/practice_1
//fn main() {
//    input!{
//        a: i32, b: i32, c: i32,
//        foo: chars,
//    }
//    let s: String = foo.into_iter().collect();
//    println!("{} {}", a+b+c, s);
//}
fn main() {
    input! { a: usize, b: usize, c: usize, d: usize }
    let l= a+b;
    let r= c+d;
    if l > r {
        println!("Left");
    } else if l < r {
        println!("Right");
    } else {
        println!("Balanced");
    }
}

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

int main(){
  long long N,ans,temp;
  cin >>N;
  long long a[N];
  long long b[N]={0};
  map <long long ,long long> mp;
  for (int i=0;i<N;i++){
    cin>>a[i];
    temp=a[i];
    mp[temp]++;
  }
  long long total=0;
  //トータルの計算
  for(auto itr=mp.begin();itr !=mp.end();itr++){
    total=total+(itr->second)*(itr->second-1)/2;
  }
  
  //for(auto itr=mp.begin();itr !=mp.end();itr++){
  //  for(int i=0;i<N;i++){
  //    if(a[i]==(itr->first)){
  //      b[i]=(itr->second);
  //    }
  //  }
  //}
  ans=0;
  long long ck,mt;
  for(int i=0;i<N;i++){
    ck=mp[a[i]];
    if(ck==1){
      mt=0;
    }
    else if(ck==2){
      mt=1;
    }
    else {
      mt=ck*(ck-1)/2-(ck-1)*(ck-2)/2;
    }
    
    //cout<<"*"<<i<<"#"<<ck<<"$"<<mt<<endl;
    ans=total-mt;
      cout<<ans<<endl;
    }
  //cout<<"#"<<total<<endl;//*
  return 0;
}


 

Measured memory_bytes: 13952
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>


typedef long long ll;

using namespace std;

int main() 
{ 

	int k, n;
	cin >> k >> n;

	vector<int> nums(n);

	for (int i = 0; i < n; i++) cin >> nums[i];

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

	int min = 0;
	int ans = 0;

	for (int i = 0; i < n-1; i++){
		if (nums[i+1] - nums[i] > min){
			min = nums[i+1] - nums[i];
		}
		ans += (nums[i+1] - nums[i]);
	}

	int temp = nums[0] + (k - nums[n-1]);
	ans += temp;

	if (temp > min){
		ans -= temp;
	} else {
		ans -= min;
	}

	cout << ans << endl;

	return 0; 
} 


Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)

int N,W[123];

int main() {

	scanf("%d", &N);
	rep(i, N) scanf("%d", &W[i]);

	int ans = 1234045523;

	int sum = 0;
	rep(i, N) sum += W[i];

	int t = 0;
	rep(i, N-1) {
		t += W[i];
		ans = min(ans, abs((sum - t) - t));
	}

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

	return 0;
}


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

int main() {
int X,N;
  cin >> X >> N;
  vector<int> p(N);
  vector<int> A(100,0);
  int result = 0;
  for(int a = 0;a < N;a++){
    cin >> p[a];
    A[p[a]-1] = 1;
  }
  for(int a = 0;a < 200;a++){
    if(A[a] == 0){
      
      if(abs(X - (a + 1)) < abs(X - result)){
        
       result = a + 1; 
      }
      
    }
    
  }
  cout << result << endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;

int main()
{
  i64 n,i,ans;
  scanf("%lld",&n);
  for(i=1;i*i<=n;i++)
    if(n%i==0)ans=i;
  printf("%lld",ans+n/ans-2);
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define int           long long
#define	pb            push_back
#define all(a)        (a).begin(),(a).end()
#define sz(x)         (int)x.size()
#define F             first
#define S             second
#define endl          "\n"
#define inf           1000000007
#define FOR(i, a, b)  for(int i=a; i<b; i++)
#define bigboi        1e18
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers. 
//int dp[333][2];	

void solve(){
	int arr[3];
	FOR(i, 0, 3) cin>>arr[i];
	sort(arr, arr+3);
	if((arr[0]==arr[1] && arr[1]!=arr[2] ) || (arr[1]==arr[2] && arr[1]!=arr[0])){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); 	
	int t=1;
	//cin>>t;
	FOR(i, 1, t+1){	
	//	cout<<"Case #"<<i<<":"<<endl;
		solve();
	}
	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
 
}

Measured memory_bytes: 256
// ABC162
// a.cs

using System;

class A
{
    public static void Main()
    {
        string[] str = Console.ReadLine().Split(' ');

        if (str[0].IndexOf('7') != -1)
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }
}

Measured memory_bytes: 25740
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define N 300009
#define inf 1e18
//int mod=1e9+7;
int mod=998244353;
#define ll int
#define P pair<int,int>

int MOD(int n){
    if(n>=mod)
    n-=mod;
    return mod;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int i=0;
    while(1){
        if(i%2){
            a-=d;
            if(a<=0){
                cout<<"No\n";
                return 0;
            }
        }
        else{
            c-=b;
            if(c<=0){
                cout<<"Yes\n";
                return 0;
            }
        }
        i++;
    }
    return 0;
}

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

int main()
{
    int n, a[200010];
    cin >> n;

    bool f = n % 2;
    int l = 100005;
    int r = l + 1;
    for(int i = 0; i < n; i++, f = !f){
        if(f) cin >> a[l--];
        else cin >> a[r++];
    }

    for(int i = ++l; i < r; i++) cout << a[i] << " ";
    cout << endl;

    return 0;
}


Measured memory_bytes: 2944
object Main extends App {
	val Array(n, m) = scala.io.StdIn.readLine.split(" ").map(_.toInt)
	val a = scala.io.StdIn.readLine.split(" ").map(_.toInt)
 
	val Asum = a.sum.toDouble/(4*m)
 
	if(a.count(_ >= Asum) >= m) println("Yes")
	else println("No")
}

Measured memory_bytes: 25552
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=100005;
char s[max_n],t[max_n];
int cnts[max_n],cntt[max_n];
int q;
int main(){
    scanf(" %s %s",s+1,t+1);
    int ns=strlen(s+1),nt=strlen(t+1);
    for(int i=1;i<=ns;i++)cnts[i]=cnts[i-1]+(s[i]=='A'?1:2);
    for(int i=1;i<=nt;i++)cntt[i]=cntt[i-1]+(t[i]=='A'?1:2);
    scanf("%d",&q);
    while(q--){
        int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        int x=cntt[r2]-cntt[l2-1]-(cnts[r1]-cnts[l1-1]);
        if(x%3==0)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

long long n, q, k;
#define INF (1UL << 50);
using P = pair<long long, int>;
vector<pair<int, long long>> G[100001];
long long d[100001];
void dijkstra(void) {
  for (int i = 0; i < 100001; i++) d[i] = INF;
  priority_queue<P, vector<P>, greater<P>> que;
  d[k] = 0;
  que.push(P(0, k));
  while (!que.empty()) {
    P p = que.top(); que.pop();
    int v = p.second;
    if (d[v] < p.first) continue;
    for (int i = 0; i < G[v].size(); i++) {
      auto edge = G[v][i];
      if (d[edge.first] > d[v] + edge.second) {
        d[edge.first] = d[v] + edge.second;
        que.push(P(d[edge.first], edge.first));
      }
    }
  }
}
int main(void) {
  cin >> n;
  for (int i = 0; i < n; i++) G[i] = vector<pair<int, long long>>();
  for (long long i = 0; i < n-1; i++) {
    int a, b;
    long long c;
    cin >> a >> b >> c;
    G[a].push_back({b, c});
    G[b].push_back({a, c});
  }
  cin >> q >> k;
  dijkstra();
  for (long long i = 0; i < q; i++) {
    long long x, y;
    cin >> x >> y;
    cout << d[x] + d[y] << endl;
  }
  return 0;
}


Measured memory_bytes: 11120
x,n =map(int,input().split(" "))

if n!=0:
    a=list(map(int,input().split()))
    a.sort
    x_p=x
    x_n=x
    
    while True:
        if all(elem != x_p for elem in a) and all(elem != x_n for elem in a):
            print(x_n)
            break;
        elif all(elem != x_p for elem in a):
            print(x_p)
            break;
        elif all(elem != x_n for elem in a):
            print(x_n)
            break;
        x_n-=1
        x_p+=1
            
else:
  print(x)  

Measured memory_bytes: 9152
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
using namespace std;

int main() {
  int n, a, b;
  cin >> n >> a >> b;
  int y = a + b - n;
  if (y < 0) y = 0;
  cout << min(a, b) << " " << y << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x,a,b;
  cin >> x >>a >>b;
  if(b - a <= 0){
    cout <<"delicious" <<endl;
  }
  else if(b - a > 0 && b -a <= x){
    cout <<"safe" <<endl;
  }
  else if( b-a >0){
    cout << "dangerous" <<endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

string solve(pii f,vector<pii> w)
{
	int di[]={-2,-2,-2,2,2,2,-1,0,1,-1,0,1};
	int dj[]={-1,0,1,-1,0,1,-2,-2,-2,2,2,2};
	int n=w.size();
	queue<pair<int,pii> > q;
	rep(i,12)
		q.push(mp(0,mp(f.first+di[i],f.second+dj[i])));
	while(q.size()){
		int cur=q.front().first;
		pii curp=q.front().second;
		q.pop();
		if(cur==n)
			return "OK";
		int curi=curp.first,curj=curp.second;
		if(curi<0 || 10<=curi || curj<0 || 10<=curj)
			continue;
		if(max(abs(curi-w[cur].first),abs(curj-w[cur].second))>1)
			continue;
		rep(i,12)
			q.push(mp(cur+1,mp(curi+di[i],curj+dj[i])));
	}
	return "NA";
}

int main()
{
	for(pii f;cin>>f.first>>f.second,f.first|f.second;){
		int n;
		cin>>n;
		vector<pii> w(n);
		rep(i,n)
			cin>>w[i].first>>w[i].second;
		cout<<solve(f,w)<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int main(){
  int A,B;
  cin>>A>>B;
  if(A==1){
    if(B==2)cout<<3<<endl;
    else cout<<2<<endl;
  }
  if(A==2){
    if(B==1)cout<<3<<endl;
    else cout<<1<<endl;
  }
  if(A==3){
    if(B==1)cout<<2<<endl;
    else cout<<1<<endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <string>
#include <stack>
#include <regex>
#include <cctype>

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<long long>
#define vvl vector<vector<long long>>

using namespace std;

typedef long long ll;

int main()
{
  int n;
  cin >> n;
  for (int i = n; i <= 999; i++)
  {
    if (i % 111 == 0)
    {
      cout << i << endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define gc getchar
#define rint register int
#define rep(i,u,z) for(rint i=u;i<=z;++i)
#define reb(i,u,z) for(rint i=u;i>=z;--i)
#define inf 0x7fffffff

using namespace std;
typedef long long ll;

const int N=1e5+10;
int n,m;
ll ans;
struct node{
	int a,b;
	inline bool operator < (const node ano) const{
		return a<ano.a;
	}
}d[N];

inline int readint(){
	int rt=0,sign=1;
	char ch=gc();
	while(ch<'0'||ch>'9'){
		if(ch=='-')sign=-1;
	    ch=gc();
	}
	while(ch>='0'&&ch<='9'){
		rt=(rt<<3)+(rt<<1)+(ch&15);
		ch=gc();
	}
	return rt*sign;
}
int main(){
	n=readint(),m=readint();
	rep(i,1,n)d[i].a=readint(),d[i].b=readint();
	sort(d+1,d+1+n);
	rep(i,1,n){
		if(m>d[i].b){
			ans+=1ll*d[i].b*d[i].a;
			m-=d[i].b;
		}
		else{
			ans+=1ll*m*d[i].a;
			break;
		}
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<utility>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
 
using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 1e+9
#define EPS 1e-9
#define P pair<int,int>
#define rep(i,j) for(int i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = j; i < (k); i++)
typedef long long ll;
priority_queue<P> PQ;
int main(){
    int icicle[100010]={0};
    int N,L;
    scanf("%d%d",&N,&L);
    int x;
    rep(i,N){
        scanf("%d",&x);
        PQ.push(P(x,i+1));
    }
    while( !PQ.empty() ){
        int l = PQ.top().first;
        int m = PQ.top().second;
        PQ.pop();
        int t = icicle[m] + L - l;
        icicle[m-1] = max(t,icicle[m-1]);
        icicle[m+1] = max(t,icicle[m+1]);
    }
    int res = 0;
    rep(i,N){
        res = max(res,icicle[i+1]);
    }
    printf("%d\n",res);
    return 0;
}

Measured memory_bytes: 2440
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <math.h>

using namespace std;

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

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

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <sstream>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SZ(x) (int)(x.size())
#define F0(i,n) for(int i=0;i<n;i++)
#define F1(i,n) for(int i=1;i<=n;i++)
#define CL(a,x) memset(x, a, sizeof(x));
const int MOD = 1000000007;
const double pi = atan(1.0)*4.0;
const double eps = 1e-8;
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
int bc(int n) { return n ? bc((n-1)&n)+1 : 0; }

int i, j, k, m, n, l;
int p[400][400], at[400], cnt[400], sport[400];

int ok(int R) {
    F1(i, m) { sport[i] = 1; cnt[i] = 0; }
    F1(i, n) {
        at[i] = 1;
        cnt[p[i][1]]++;
    }
    while (1) {
        int good = 1;
        F1(i, m) if (cnt[i] > R) {
            good = 0;
            sport[i] = 0;
            break;
        }
        F1(i, n) while (!sport[p[i][at[i]]]) {
            cnt[p[i][at[i]]]--;
            at[i]++;
            if (at[i] > m) return 0;
            cnt[p[i][at[i]]]++;
        }
        if (good) break;
    }
    return 1;
}

int main() {
    cin >> n >> m;
    F1(i, n) F1(j, m) scanf("%d", &p[i][j]);
    
    int P = 1, Q = n;
    while (P < Q) {
        int R = (P + Q) / 2;
        if (ok(R)) Q = R; else P = R + 1;
    }
    cout << P << endl;
    
    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define INF 1e7
#define mod 1000000007

using namespace std;
typedef long long int ll;
typedef tuple<int,int,int> tii;
typedef tuple<long long int,long long int,long long int> tll;
typedef tuple<double,double,double> tdd;


int main()
{
    ll S; cin >> S;
    vector<ll>dp(S+1,0);
    for(ll i = 3; i <= S; i++) dp[i] = 1;
    for(ll i = 3; i <= S; i++)
    {
        if(i-3 < 3) continue;
        for(ll j = 3; j <= i-3; j++)
        {
            dp[i] += dp[j];
            dp[i] %= mod;
        }
    }
    cout << dp[S] << endl;
}

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

int main() {
 	
  int n,m; cin >> n >> m;
  vector<int> p(n+1);
  
  for(int i=0; i<m; i++) {
    int a,b; cin >> a >> b;
  	p[a]++;
    p[b]++;
  }
  for(int i=1; i<=n; i++){
    cout << p[i] << endl;
  }
     
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(a) sort(a.begin(), a.end())
#define fin(ans) cout << (ans) << endl
const int INF = 1<<30;
const ll MOD = 1000000007;

int main() {
    ll N,K,ans=0;
    cin >> N >> K;

    vector<ll> A(N+1);

    for (int i = 1; i < K+1; i++) {
        ll d; cin >> d;
        for (int j = 0; j < d; j++) {
          ll n; cin >> n;
          A[n]++;
        }
    }
    
    for (int i = 1; i < N+1; i++) {
        if(A[i] == 0) ans++;
    }
    
    cout << ans << endl;
}

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

#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define ALL(x) (x).begin(), (x).end()
#define BIT(n) (1LL<<(n))
#define SZ(x) ((int)(x).size())
#define fst first
#define snd second
typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> pii;typedef vector<pii> vpii;
typedef long long ll;

void Main() {
  int N, M;
  scanf("%d%d", &N, &M);

  vi B(N, 1);
  vector<bool> P(N);
  P[0] = 1;

  rep(i,M) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--; y--;

    if (P[x]) {
      if (B[x] == 1) {
        P[x] = 0;
      }
      P[y] = 1;
    }
    B[x]--;
    B[y]++;
  }

  int ans = accumulate(ALL(P), 0);
  _p("%d\n", ans);
}
int main() { cin.tie(0); ios::sync_with_stdio(false); Main(); return 0; }


Measured memory_bytes: 640
#include <stdio.h>

int main(void) {
	float mountain;
	float max, min, dif;
	
	scanf("%f", &mountain);
	max = mountain; min = mountain;
	while(scanf("%f", &mountain) != EOF){
		if(max < mountain) max = mountain;
		if(min > mountain) min = mountain;
	}
	
	dif = max - min;
	printf("%f\n", dif);
	
	return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    static int ans;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == 0)
                break;
            ans = 0;
            slove(n, 0, 1);
            System.out.println(ans);
        }
    }

    public static void slove(int n, int c, int prev) {
        //System.out.println(c+" : "+n);
        if (n == 0) {
            ans++;
            return;
        }
        if (c == 4) {
            return;
        }
        for (int i = prev; i * i <= n; i++) {
            if (n - i * i >= 0)
                slove(n - i*i, c + 1, i);
        }
    }
}

Measured memory_bytes: 12000
a = gets.to_s

b = a.match(/^keyence\w*/)
c = a.match(/^\w+keyence$/)
d = a.match(/^k\w+eyence$/)
e = a.match(/^ke\w+yence$/)
f = a.match(/^key\w+ence$/)
g = a.match(/^keye\w+nce$/)
h = a.match(/^keyen\w+ce$/)
i = a.match(/^keyenc\w+e$/)

case when b,c,d,e,f,g,h,i
 puts "YES"
else
 puts "NO"
end

Measured memory_bytes: 1788
#include <cmath>
#include <cstdio>
#include <cstring>

const int mod = 1e9 + 7;
const int MAXN = 1e5 + 5, MAXS = 4e4;

template<typename _T>
void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}

int inv( const int );
int qkpow( int, int );
void add( int &x, const int v );

struct matrix
{
	int mat[4][4];
	int n, m;
	
	matrix() { n = m = 0, clr(); }
	matrix( const int N ) { n = m = N, clr(); }
	matrix( const int N, const int M ) { n = N, m = M, clr(); }
	void clr() { memset( mat, 0, sizeof mat ); }
	
	int* operator [] ( const int indx ) { return mat[indx]; }
	
	matrix operator * ( matrix b ) const 
	{
		matrix ret( n, b.m );
		for( int i = 1 ; i <= n ; i ++ )
			for( int k = 1 ; k <= m ; k ++ )
				if( mat[i][k] )
					for( int j = 1 ; j <= b.m ; j ++ )
						add( ret[i][j], 1ll * mat[i][k] * b[k][j] % mod );
		return ret;
	}
	
	void operator *= ( matrix b ) { *this = *this * b; }
};

matrix A[MAXS], Art[MAXS], B;

int N, M, rt;

int inv( const int a ) { return qkpow( a, mod - 2 ); }
matrix qkpow( const int n ) { return Art[n / rt] * A[n % rt]; }
void add( int &x, const int v ) { x = ( x + v >= mod ? x + v - mod : x + v ); }

matrix I( const int n )
{
	matrix ret( n );
	for( int i = 1 ; i <= n ; i ++ )
		ret[i][i] = 1;
	return ret;
}

void init()
{
	Art[0] = A[0] = I( 3 );
	A[1] = B = matrix( 3, 3 );
	A[1][1][1] = 1, A[1][1][2] = 2, A[1][1][3] = 1;
	A[1][2][2] = 1, A[1][2][3] = 1;
	A[1][3][1] = 1, A[1][3][2] = 2, A[1][3][3] = 2;
	B[1][1] = 1, B[1][2] = 2, B[1][3] = 1;
	B[2][2] = 1, B[2][3] = 1;
	B[3][3] = 1;
	
	rt = ceil( sqrt( N ) );
	for( int i = 2 ; i < rt ; i ++ ) A[i] = A[i - 1] * A[1];
	Art[1] = A[rt - 1] * A[1];
	for( int i = 2 ; i < rt ; i ++ ) Art[i] = Art[i - 1] * Art[1];
}

int qkpow( int base, int indx )
{
	int ret = 1;
	while( indx )
	{
		if( indx & 1 ) ret = 1ll * ret * base % mod;
		base = 1ll * base * base % mod, indx >>= 1;
	}
	return ret;
}

int main()
{
	read( N ), read( M ), init();
	
	matrix beg( 1, 3 );
	beg[1][1] = 1;
	
	int lst = 0;
	for( int i = 1, p ; i <= M ; i ++ )
	{
		read( p );
		beg *= qkpow( p - lst );
		beg *= B, lst = p + 1;
	}
	beg *= qkpow( N - lst );
	write( beg[1][3] ), putchar( '\n' );
	return 0;
}

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

int main() {
    int a, b;
    cin >> a >> b;
    string str = "";
    str += to_string(a);
    str += to_string(b);
    int c = atoi(str.c_str());
    for (int i = 0; i < sqrt(c) + 1; i++) {
        if (i * i == c) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
sa = input()
sb = input()
sc = input()
head = sa[0]
sa = sa[1:]
while True:
    if head == 'a':
        if sa == '':
            ans = 'A'
            break
        head = sa[0]
        sa = sa[1:]
    elif head == 'b':
        if sb == '':
            ans = 'B'
            break
        head = sb[0]
        sb = sb[1:]
    elif head == 'c':
        if sc == '':
            ans = 'C'
            break
        head = sc[0]
        sc =sc[1:]
print(ans)

Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(10**5)
def GCM(a, b):
  a, b = max(a,b), min(a, b)
  r = a % b
  if r == 0:
    return b
  else:
    return GCM(b, r)

def LCD(a, b):
  g = GCM(a, b)
  return (a//g)*b

N, M = map(int, input().split())
A = list(map(int, input().split()))
X = A[0]//2
for a in A[1:]:
  b = a//2
  newX = LCD(X, a//2)
  if (newX // b)%2 == 0:
    print(0)
    sys.exit(0)
  else:
    X = newX
X_2 = X*2
print(M//X-M//X_2)

Measured memory_bytes: 15060
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int w,h,n,ans;
const int MAXN=1000+10;
int x1[MAXN],x2[MAXN],y1[MAXN],y2[MAXN];
int hashx[MAXN*2],hashy[MAXN*2];
int fld[MAXN*2][MAXN*2];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void compress()
{
    int tx=0,ty=0;
    for (int i=1;i<=n;i++)
    {
        hashx[++tx]=x1[i];hashx[++tx]=x2[i];
        hashy[++ty]=y1[i];hashy[++ty]=y2[i];
    }
    hashx[++tx]=0;hashx[++tx]=w;
    hashy[++ty]=0;hashy[++ty]=h;
    sort(hashx+1,hashx+tx+1);
    sort(hashy+1,hashy+ty+1);
    w=unique(hashx+1,hashx+tx+1)-(hashx+1);
    h=unique(hashy+1,hashy+ty+1)-(hashy+1);
    for (int i=1;i<=n;i++)
    {
        x1[i]=lower_bound(hashx+1,hashx+w+1,x1[i])-hashx-1;
        x2[i]=lower_bound(hashx+1,hashx+w+1,x2[i])-hashx-1;
        y1[i]=lower_bound(hashy+1,hashy+h+1,y1[i])-hashy-1;
        y2[i]=lower_bound(hashy+1,hashy+h+1,y2[i])-hashy-1;
    }
    w--;h--;
}

void init()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
    compress();
}

void imos()    /*imos?*/
{
    memset(fld,0,sizeof(fld));
    for (int i=1;i<=n;i++)
    {
        fld[x1[i]][y1[i]]++;
        fld[x2[i]][y2[i]]++;
        fld[x1[i]][y2[i]]--;
        fld[x2[i]][y1[i]]--;
    }

    for (int i=0;i<w;i++)
        for (int j=1;j<h;j++)
            fld[i][j]+=fld[i][j-1];

    for (int j=0;j<h;j++)
        for (int i=1;i<w;i++)
            fld[i][j]+=fld[i-1][j];
}

void bfs(int x,int y)
{
    ans++;
    queue<int> qx,qy;
    qx.push(x);
    qy.push(y);
    fld[x][y]=1;
    while (!qx.empty())
    {
        int xx=qx.front();qx.pop();
        int yy=qy.front();qy.pop();
        for (int i=0;i<4;i++)
        {
             int nx=xx+dx[i],ny=yy+dy[i];
             if (nx<0 || ny<0 || nx>w || ny>h || fld[nx][ny]>0) continue;
             qx.push(nx);
             qy.push(ny);
             fld[nx][ny]=1;
        }
    }
}

void solve()
{
    ans=0;
    for (int i=0;i<w;i++)
        for (int j=0;j<h;j++)
            if (fld[i][j]==0) bfs(i,j);
    printf("%d\n",ans);
}

int main()
{
    // freopen("in.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    while (~scanf("%d%d",&w,&h)&&w&&h)
    {
        init();
        imos();
        solve();
    }
    return 0;
}


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

int main(){
    int a,b;
    cin >> a >> b;
    if (a == b){
        cout << "a == b" << endl;
    }
    else if (a > b){
        cout << "a > b" << endl;
    }
    else{
        cout << "a < b" << endl;
    }
    return 0;
}


Measured memory_bytes: 3112
#include<stdio.h>

#define N 8

#define F -1
#define NF 1

int str[N][N];

int row[N],col[N];
int dpos[2*N-1],dneg[2*N-1];

void initialize(void);
void judge(int i);
void print(void);


int main(void){
  int i,j;
  int k;
  int r,c;
  
  initialize();

  for(i = 0;i < N;i++){
    for(j = 0;j < N;j++){
      str[i][j] = 0;
    }
  }

  scanf("%d",&k);
  for(i = 0;i < k;i++){
    scanf("%d %d",&r,&c);
    str[r][c] = 1;
  }

  judge(0);

  return 0;
}
	
	


void initialize(void){
  int i;

  for(i = 0;i < N;i++){
    row[i] = F;
    col[i] = F;
  }

  for(i = 0;i < 2*N-1;i++){
    dpos[i] = F;
    dneg[i] = F;
  }

}



void print(void){
  int i,j;

  for(i = 0;i < N;i++){
    for(j = 0;j < N;j++){
      if(str[i][j]){
	if(row[i] != j){
	  return;
	}
      }
      
    }
  }


  
  for(i = 0;i < N;i++){
    for(j = 0;j < N;j++){
      if(row[i] == j){
	putchar('Q');
      } else {
	putchar('.');
      }
      
    }
    puts("");
  }
}



void judge(int i){
  int j;
  
  if(i == N){
    print();
    return;
  }

  for(j = 0;j < N;j++){
    if(col[j] == NF || dpos[i+j] == NF || dneg[i-j+N-1] == NF){
      continue;
    }

    row[i] = j;
    
    dneg[i-j+N-1] = NF;
    dpos[i+j] = NF;
    col[j] = NF;

    judge(i+1);

    dneg[i-j+N-1] = F;
    dpos[i+j] = F;
    col[j] = F;
    row[i] = F;
  }

}




Measured memory_bytes: 2108
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
const int md = 998244353;
const int mx = 4005;
int n, k;
using ll = long long;
ll exp(ll b, ll n){
	ll res = 1;
	for(; n; n/=2,(b*=b)%=md) if(n%2) (res *= b) %= md;
	return res;
}
ll fact[mx] = {1}, invf[mx];
void setcomb(int n){
	for(int i = 1; i <= n; i++) fact[i] = (fact[i-1] * i) % md;
	invf[n] =  exp(fact[n] ,md-2);
	for(int i = n; i > 0; i--) invf[i-1] = (invf[i] * i) % md;
}
inline ll comb(int a, int b){return fact[a] * invf[a-b] % md * invf[b] % md;}
inline ll nkcom(int n, int k){return comb(n+k-1, n);}
inline ll calc(int n, int k, int t){
	ll ret = 0;
	rep(i,t+1) ret = (ret + nkcom(n-i,k-t*2+i) * comb(t,i) % md * exp(2,i)) % md;
	return ret;
}
int main(){
	scanf("%d%d", &k, &n);
	setcomb(k+n);
	for(int i = 1; i < 2*k; i++){
		int t = min(i,2*k-i);
		printf("%lld\n", t%2 ? (calc(n-1,k-1,t/2) + calc(n,k-1,t/2)) % md : calc(n,k,t/2));
	}
}

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

int main() {
	int a[2]; cin >> a[0] >> a[1];
	for(int i=0; i<2; ++i){
	    if(a[i]==2) a[i]=3;
	    else if(a[i]<8){
	        if(a[i]%2) a[i]=1;
	        else a[i]=2;
	    }
	    else if(a[i]%2) a[i]=2;
	    else a[i]=1;
	}
	if(a[0]==a[1]) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


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

using namespace std;

int n;
string s, t[2] = {"S", "W"};

string solve(){
	for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++){
		string res = t[i] + t[j];
		for(int k = 1; k < n - 1; k++){
			if(res[k] == 'S' && s[k] == 'o' || res[k] == 'W' && s[k] == 'x') res += res[k - 1];
			else res += (res[k - 1] == 'S' ? 'W' : 'S');
		}
		if(res[0] == 'S' && s[0] == 'o' || res[0] == 'W' && s[0] == 'x'){ if(res[1] != res[n - 1]) continue; }
		else{ if(res[1] == res[n - 1]) continue; }
		if(res[n - 1] == 'S' && s[n - 1] == 'o' || res[n - 1] == 'W' && s[n - 1] == 'x'){ if(res[0] != res[n - 2]) continue; }
		else{ if(res[0] == res[n - 2]) continue; }
		return res;
	}
	return "-1";
}

int main(){
	cin >> n >> s;
	cout << solve() << endl;
	return 0;
}

Measured memory_bytes: 640
N, K = gets.split.map(&:to_i)
MOD = 10**9 + 7

rn = Math.sqrt(N).to_i
a = [1] * rn
i = rn + 1
while i <= N
  j = N/(N/i) + 1
  a << j - i
  i = j
end
c = a.size
dp = Array.new(K + 1){Array.new(c + 1, 0)}
dp[0][0] = 1
(0 ... K).each do |k|
  s = [0]
  (0 ... c).each{|l| s[l + 1] = s[l] + dp[k][l]}
  (0 ... c).each{|l| dp[k + 1][l] = (s[c - l] * a[l]) % MOD}
end
puts dp[K].inject(:+) % MOD

Measured memory_bytes: 79224
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const double EPS = 1e-10;

int main() {
	int D;
	cin >> D;
	cout << "Christmas";
	for (int i = 0; i < 25 - D; i++) cout << " Eve";
	cout << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
const int MaxN = 1e6;
using namespace std;
typedef long long ll;
int n;
ll a[MaxN + 5];
int cmp(ll x,ll y){
	return x > y;
}

int main()
{
	scanf("%d",&n);
	for(int i = 1; i <= 3 * n; i++) scanf("%lld",&a[i]);
	sort(a + 1,a + 3 * n + 1,cmp);
	ll ans = 0;
	for(int i = 2; i <= 2 * n;)
	{
		ans += a[i];
		i += 2;
	}
	printf("%lld\n",ans);
	return 0;
}



	

Measured memory_bytes: 4224
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

string S,T;

signed main(){
	cin>>S>>T;
	int ans=0;
	REP(i,S.size()){
		if(S[i]!=T[i]){
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef std::vector<int> vi;
typedef std::vector<long long> vll;

#define pub push_back
#define pob pop_back
#define mp make_pair
#define ff first
#define ss second
#define umap unordered_map
#define uset unordered_set

#define forn(i, n)     for(ll i = 0; i< (ll)n; i++)
#define forf(i, x, y)  for(ll i=(x); i<=(ll)y; i++)
#define forb(i, x, y)  for(ll i=(x); i>=(ll)y; i--)
#define lpt() 		   ll T; std::cin>>T; while(T--)

#define nl "\n"
#define newl std::cout<<"\n";
#define bug(x) std::cerr<<"debug "<<#x<<" : "<<x<<"\n";
#define all(x) x.begin(),x.end()
#define fastio() ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

template<typename X> std::ostream& operator<< (std::ostream& out, std::vector<X> v)
{ for(auto &i : v) out<<i<<" "; return out; }
template<typename X, typename Y> std::ostream& operator<< (std::ostream& out, std::pair<X,Y> p)
{ out<<p.first<<" "<<p.second; return out; }

static const long long mod = 1000000007;

using namespace std;

int main()
{fastio();
	

	ll n,k;
	cin>>n>>k;
	ll h[n];
	forn(i,n)
		cin>>h[i];
	ll dp[n];
	memset(dp,-1,sizeof dp);
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);
	if(n==2)
	{
		cout<<dp[n-1]<<nl;
		return 0;
	}
	forf(i,2,n-1)
	{	
		ll t;
		(i>k-1)? t = k:t = i;
		ll mi = LLONG_MAX;
		while(t)
		{
			mi = min(mi, abs(h[i]-h[i-t]) + dp[i-t]);
			t--;
		}
		dp[i] = mi;
	}
	cout<<dp[n-1]<<nl;
	
return 0;}


Measured memory_bytes: 1792
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b , a % b);
}

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

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

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll a,b,c,k; cin >> a >> b >> c >> k;
  if(k % 2 == 0) cout << a-b << endl;
  else cout << b-a << endl;

  
}

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

int N;
ll Z, W;
int a[2000];
ll dp[2010][2010][2];

ll f(int n, int last, int turn){
	ll& d = dp[n][last][turn];
	if(d >= 0) return d;
	ll myNum = a[n];
	if(turn == 0){
		d = -1e9;
		ll oppNum = last == N ? W : a[last];
		// ゲーム終了
		if(n == N - 1){
			d = max(d, abs(myNum - oppNum));
		}
		else{
			// 引く
			d = max(d, f(n + 1, last, turn));
			// 引かない
			d = max(d, f(n + 1, n, 1 - turn));
		}
	}
	else{
		d = 1e9;
		ll oppNum = last == N ? Z : a[last];
		// ゲーム終了
		if(n == N - 1){
			d = min(d, abs(myNum - oppNum));
		}
		else{
			// 引く
			d = min(d, f(n + 1, last, turn));
			// 引かない
			d = min(d, f(n + 1, n, 1 - turn));
		}
	}
	return d;
}


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	cin >> N >> Z >> W;
	for(int i = 0; i < N; i++){
		cin >> a[i];
	}
	memset(dp, -1, sizeof dp);
	cout << f(0, N, 0) << endl;
}


Measured memory_bytes: 63488
def solve(inp):
    N = int(inp.readline().strip())

    return str(N * N * N)


def test(s):
    from io import StringIO
    print(solve(StringIO(s)))


def main():
    import sys
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    # test('')
    main()


Measured memory_bytes: 2940
#include "bits/stdc++.h"
using namespace std;
using ll = int64_t; using pii = pair<int, int>;
const int MOD = (int)1e9 + 7, INF = (1 << 27); const ll INFLL = (1LL << 55);
#define FOR(i,a,b) for(int (i)=(a);(i)<(int)(b);(i)++)
#define rep(i,n) FOR(i,0,n)
template<typename T, typename U> inline void chmax(T &x, U y) { if (x < y) x = y; }
template<typename T, typename U> inline void chmin(T &x, U y) { if (x > y) x = y; }


int main() {
	int n; cin >> n;
	string a, b, c;
	cin >> a >> b >> c;
	int ans = 0;
	rep(i, n) {
		set<char> s;
		s.insert(a[i]);
		s.insert(b[i]);
		s.insert(c[i]);
		int n = s.size();
		ans += n - 1;
	}
	cout << ans << endl;
}

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


int main() {
	long long ans = 0;
	int n; cin >> n;
	int mx = 0;
	for(int i = 1; i <= n; ++i) {
		int x; cin >> x;
		if(x >= mx) {
			mx = x; 
		} else {
			ans += (mx - x);
		}
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
 
using namespace std;
 
typedef long long int ll;
typedef vector<long long int> VL;
typedef vector<VL> VVL;
 
int main() {
    int res[26];
    for(int i=0; i<26; i++) {
        res[i] = 0;
    }
    
    string s;
    char buf[256];
    while(cin.read(buf, sizeof(buf))) {
        s.append(buf, sizeof(buf));
    }
    s.append(buf, cin.gcount());
    
    for(int i=0; i<s.length(); i++) {
        for(int j=0; j<26; j++) {
            if(s[i] == 'A' + j || s[i] == 'a' + j) {
                res[j] += 1;
                break;
            }
        }
    }
    
    for(int i=0; i<26; i++) {
        char c = 'a' + i;
        cout << c << " : " << res[i] << endl;
    }
    
    return 0;
}



Measured memory_bytes: 3180
s=list(input())
k=int(input())
test=s*3
for i in range(len(s)*3-1):
    if test[i]==test[i+1]:
        test[i+1]="A"
A=test[:len(s)].count("A")
B=test[len(s):len(s)*2].count("A")
C=test[len(s)*2:len(s)*3].count("A")

if s.count(s[0])==len(s):
    print((len(s)*k)//2)
else:
    if k==1:print(A)
    elif k==2:print(A+B)
    else:print(A+B*(k-2)+C)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;

/* --------------------------------------------------- */

int main() {
    int x, y;
    cin >> x >> y;
    int ans = 0;
    if(x == 1) ans += 300000;
    if(x == 2) ans += 200000;
    if(x == 3) ans += 100000;
    if(y == 1) ans += 300000;
    if(y == 2) ans += 200000;
    if(y == 3) ans += 100000;
    if(x == 1 && y == 1) ans += 400000;

    cout << ans << endl;

    return 0;
}

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

int main(){
  int n;
  cin >> n;
  cout << n*(n+1)/2 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <ctime>
using namespace std;

#define rep(i,a,n) for(int i=a; i<n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 999999999

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long int ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

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

namespace std {
    bool operator<(const P a, const P b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

int main() {
    string s;
    while(cin >> s) {
        string ans;
        int i = 0;
        while(i < s.length()) {
            if(s[i] != '@') ans += s[i++];
            else {
                int n = (int)s[++i] - 48;
                i++;
                rep(j,0,n) {
                    ans += s[i];
                }
                i++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using namespace std;
 
int main()
{
    ll n;
    cin >> n;
 
    string ans = "";
 
    ll digit = 1;
    ll exp26 = 26;
    while(true)
    {
        if(n <= exp26)
        {
            break;
        }
        n -= exp26;
        digit++;
        exp26 *= 26;
    }
 
    n--;
    while(n >= 26)
    {
        ll r = n % 26;
        ans += 'a' + r;
        n /= 26;
    }
    ans += 'a' + n;
 
    while(ans.size() < digit)
    {
        ans += 'a';
    }
 
    reverse(ans.begin(), ans.end());
 
    cout << ans << endl;
 
    return 0;
}

Measured memory_bytes: 3544
n=int(input())
Xs=list(map(int,input().split()))
Xs.sort()
a=Xs[0]
b=Xs[-1]
ans=float("inf")
for p in range(a,b+1):
    m=0
    for x in Xs:
        m+=(x-p)**2
    if m<ans:
        ans=m
print(ans)

Measured memory_bytes: 3064