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

ll max(ll a, ll b) { return (a > b) ? a : b; }

int main() {
    int n, weight;
    cin >> n >> weight;
    int *w = new int[n + 10];
    int *v = new int[n + 10];
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }

    ll **dp = new ll *[n + 10];
    for (int i = 0; i < n + 10; i++) {
        dp[i] = new ll[weight + 10];
    }

    for (int i = 0; i < n + 10; i++) {
        for (int j = 0; j < weight + 10; j++) {
            dp[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= weight; j++) {
            if (j >= w[i]) {
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
            }
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
        }
    }
    cout << dp[n][weight] << endl;
    return 0;
}

Measured memory_bytes: 89848
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define fr first
#define se second
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define FILL(x,filler) memset(x,filler,sizeof(x))
#define dbg(x) cout << "#debug " << x <<"\n"
const ll mod = ll(1e9) + 7;
typedef unsigned long long ull;
void show(std::vector<ll> v) {
	for (auto x : v) {
		cout << x << " ";
	}
	cout << endl;
}





int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	map<string , int> m;
	int tme = 0;
	for(int i=0 ; i<n ; i++) {
		string s;
		cin >> s;
		int t;
		cin >> t;
		tme += t;
		m[s] = tme;
	}
	string x;
	cin >> x;
	cout << tme - m[x] << "\n";

}			



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

template <typename T>
void printlnVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << endl;
  }
}

template <typename T>
void printVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << " ";
  }
  cout << endl;
}

int main()
{
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i, N)
  {
    cin >> a[i];
    a[i]--;
  }
  int ans = 0;
  rep(i, N)
  {
    int rabbitA = i;
    int rabbitB = a[i];
    if (a[rabbitA] == rabbitB && a[rabbitB] == rabbitA)
      ans++;
  }
  cout << ans / 2 << endl;
  return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(int argc, char* argv[])
{
	//ABC159 A
	int n, m, x;
	int cnt = 0;

	//N M 偶数奇数
	scanf("%d %d", &n, &m);
	x = n + m;
	for (int i = 0; i < x; i++) {
		for (int j = i + 1; j < x; j++){
			int flg = 0;
			if (i >= n) {
				flg = 1;
			}
			if (j >= n) {
				flg ^= 1;
			}
			if (flg == 0) {
				cnt++;
			}
		}
	}
	printf("%d", cnt);

	return 0;
}

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

int main() {
  int N,A;
  cin >> N;
  cin >> A;
  if (N%500==0)
    cout << "Yes" << endl;
  else if(N%500 <= A)
    cout << "Yes" << endl;
  else 
    cout << "No" << endl;
  return 0;
}

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

int main(){
    int n,d;
    cin>>n>>d;
    int x[n][d];
    for(int i=0;i<n;i++){
        for(int j=0;j<d;j++) cin>>x[i][j];
    }
    int count=0;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            double ans=0;
            for(int k=0;k<d;k++){
                ans+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
            }
            if(sqrt(ans)-(int)(sqrt(ans))==0) count++;
        }
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define                MXX 1000006
#define                FAST_IO ios_base::sync_with_stdio(false),cin.tie(NULL)
#define                exit() return 0
#define                mpii map<int, int>
#define                mpit map<int, int>::iterator it
#define                si set<int>
#define                sit set<int>::iterator it;
#define                ll long long int
//#define                endl "\n";
const                  ll INF = 2000000000000000000LL;
const                  int MOD = 10000007;

int a[MXX];
int main()
{
    FAST_IO;
    double a, b;
    cin>>a>>b;
    printf("%0.10f\n", a/b);
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;



int main() {
	int a, b;
	cin >> a >> b;
	int p = 1;
	int t = 0;
	while(p < b) {
		t++;
		p += a - 1;
	}
	cout << t << endl;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int v[50];
double ans;

int main(){
	ios::sync_with_stdio(0);
	cout << setprecision(10) << fixed;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> v[i];
	}
	sort(v , v + n);
	ans = (double) (v[0] + v[1]) / 2;
	for (int i = 2; i < n; i++){
		ans += (double)v[i];
		ans /= 2.0;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; ++i)
#define rep1(i, n) for (int i=1; i<=n; ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr ll  MOD = (1e9+7);
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; }

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 factorial(ll n, ll m=2) {
    // calculate n!
    m = max(2LL, m);
    ll rtn = 1;
    for (ll i=m; i<=n; i++) {
        rtn = (rtn * i) % MOD;
    }
    return rtn;
}
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<P> xs(n);
    rep(i, n) {
        cin >> xs[i].first;
        xs[i].second = i;
    }
    sort(ALL(xs));
    vector<ll> ans(n);
    rep(i, n) {
        if (i < n/2) ans[xs[i].second] = xs[n/2].first;
        else ans[xs[i].second] = xs[n/2-1].first;
    }
    rep(i, n) cout << ans[i] << endl;
    return 0;
}

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

#define pb push_back
#define all(a) a.begin(), a.end()

using ll = long long;
using pii = pair<int, int>;

const int N = 1e5 + 5;
bool make[N];

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int X; cin >> X;
    make[0] = true;
    for (int i = 100; i <= 105; ++i) {
        for (int j = i; j < N; ++j)
            make[j] |= make[j - i];
    }
    cout << make[X] << "\n";
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i, n) for (int i=0, i##_len=(n); i<i##_len; ++i)
#define FOR(i, a, b) for (int i=(a); i<(b); ++i)
using ll = long long;
using namespace std;

int gcd(int b, int a)
{
    if (a == 0) return b;
    if (b == 0) return a;

    int r = a % b;
    while (r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

int main()
{
    int N;
    cin >> N;
    int A[N];
    REP(i, N) cin >> A[i];
    sort(A, A+N);

    int L[N];
    L[0] = 0;
    FOR(i, 1, N) L[i] = gcd(L[i-1], A[i-1]);

    int R[N];
    R[N-1] = 0;
    FOR(i, 1, N) R[N-i-1] = gcd(R[N-i], A[N-i]);

    int ret = 1;
    REP(i, N)
    {
        ret = max(ret, gcd(L[i], R[i]));
    }

    cout << ret << endl;
    return 0;
}


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

using namespace std;

int main() {

    int a,b,c,d;
    cin>>a>>b>>c>>d;

    if(abs(a-c)<=d || (abs(a-b)<=d && abs(b-c)<=d)){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;

 
    
    
int main(){
    int n,m,x=0,y=0;
    cin>>n>>m;
    int a[n];
    for (int i = 0; i < n; i++)
    {
      cin>>a[i];
    }
    
    for (int i = 0; i < n; i++)
    {
      y=y+a[i];
    }
   
    for (int i = 0; i < n; i++)
    {
      if (a[i]*4*m>=y)
      {
        x=x+1;
      }
      
    }
    
    if (x<m)
    {
      cout<<"No"<<endl;
    }
    else
    {
      cout<<"Yes"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <functional>

using namespace std;

const int N = 100000 + 1;

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

	ios::sync_with_stdio(false);

	int n;

	cin >> n;

	int ans = 0;

	vector<int> a(N,0);

	while (n--) {
		int x;
		cin >> x;
        if (x >= N) {
			ans++;
			continue;
		}
		a[x]++;
	}
	for (int i = 1; i < N; i++) {
		if (a[i] < i)
			ans += a[i];
		else
			ans += a[i] - i;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const long long mod = pow(10, 9) + 7;
const long long MOD = 998244353;
const long long INF = 1LL << 60;
const int inf = pow(10, 9) + 7;
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, int B) {return (A + (B - 1)) / B;}
long long divCeil(int A, long long B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, long long B) {return (A + (B - 1)) / B;}

int main()
{
  int n;
  cin >> n;
  vector<string> S(n);
  for (int i = 0; i < n; i++) cin >> S.at(i);
  
  string abc = "abcdefghijklmnopqrstuvwxyz";
  vector<vector<int>> abcN(n, vector<int>(abc.size(), 0));
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < S.at(i).size(); j++)
    {
      for (int k = 0; k < abc.size(); k++)
      {
        if (S.at(i).at(j) == abc.at(k))
        {
          abcN.at(i).at(k)++;
          break;
        }
      }
    }
  }
  
  for (int i = 0; i < abc.size(); i++)
  {
    int num = inf;
    for (int j = 0; j < n; j++)
    {
      chmin(num, abcN.at(j).at(i));
    }
    
    for (int j = 0; j < num; j++)
    {
      cout << abc.at(i);
    }
  }
  
  cout << endl;
}

Measured memory_bytes: 256
from heapq import heappop, heappush, heapify

N, M = map(int,input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))
heapify(A)

for i in range(M):
    temp = int(heappop(A)/2)
    heappush(A, temp)

print(-sum(A))

Measured memory_bytes: 20224
// AtCode ABC 122 A
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	a := readInt()
	b := readInt()
	c := readInt()
	can := b / a
	if can <= c {
		fmt.Println(can)
	} else {
		fmt.Println(c)
	}
}

func read() string {
	sc.Scan()
	return sc.Text()
}

func readInt() int {
	i, e := strconv.Atoi(read())
	if e != nil {
		panic(e)
	}
	return i
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;using ll=long long;using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;using vvl=vector<vl>;using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;using vpl=vector<PL>;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/2;constexpr int INF=inf<int>,MOD=1000000007;constexpr ll LINF=inf<ll>;
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...)_ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n)for(int i=n-1;i>=0;--i)
#define REPA(i,v)REP(i,(v).size())
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define bit(n)(1ll<<(n))
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b)cout<<((n)?a:b)<<endl
void YES(int n){cho(n,"YES","NO");}void Yes(int n){cho(n,"Yes","No");}void Poss(int n){cho(n,"Possible","Impossible");}
void _print(ostream&){}template<class T,class...U>void _print(ostream&s,const T&t,const U&...u){s<<t<<(sizeof...(u)?' ':'\n');_print(s,u...);}
template<class...T>void print(const T&...t){_print(cout,t...);}template<class...T>void dprint(const T&...t){_print(cerr,t...);}
#ifndef LOCAL
struct osd{template<class T>osd&operator<<(const T&t){return*this;}};osd cer_;
#define dprint(...)
#define cerr cer_
#endif
template<class T>bool chmax(T&a,const T&b){bool x=a<b;x?a=b:b;return x;}template<class T>bool chmin(T&a,const T&b){bool x=a>b;x?a=b:b;return x;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>class iterable{static false_type c(string v);template<class U>static auto c(U v)->decltype(all(v),true_type());static false_type c(...);public:const static bool value=decltype(c(declval<T>()))::value;};
template<class T,typename=enable_if_t<iterable<T>::value>>ostream&operator<<(ostream&o,const T&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T>vector<T>&operator<<(vector<T>&v,const T&t){v.push_back(t);return v;}
template<class T>set<T>&operator<<(set<T>&v,const T&t){v.insert(t);return v;}
template<class T>multiset<T>&operator<<(multiset<T>&v,const T&t){v.insert(t);return v;}

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    cout<<setprecision(10);
    string s;
    cin>>s;
    const int n=s.size()+1;
    vi a(n, -1);
    REP(i,n){
        if((!i || s[i-1]=='>')&&
           (i==n-1 || s[i]=='<'))a[i]=0;
    }
    dprint(a);
    REP(i,n-1){
        if(s[i]=='<' && a[i]!=-1)chmax(a[i+1], a[i]+1);
    }
    dprint(a);
    REPR(i,n-1){
        if(s[i]=='>' && a[i+1]!=-1)chmax(a[i], a[i+1]+1);
    }
    dprint(a);
    cout<<accumulate(all(a), 0ll)<<endl;
}


Measured memory_bytes: 2844
#include <bits/stdc++.h>
#define TASK "task"

using namespace std;

void rwFile() {
    freopen(TASK ".in", "r", stdin);
    freopen(TASK ".out", "w", stdout);
}

void solveA() {
    int arr[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k; cin >> k;
    cout << arr[k - 1];
}

void solveB() {
    long long h, w; cin >> h >> w;
    if (h == 1 || w == 1) {
        cout << 1;
        return;
    }
    long long res = 0;
    if (h % 2 == 0 || w % 2 == 0) res = 1LL * h * w / 2;
    else res = (1LL * h * w + 1) / 2;
    cout << res;
}

string res = "";

void recSolveD(int n, int state) {
    if (n == 0) {
        cout << res << '\n';
        return;
    }
    for (int i = 0; i <= state; i++) {
        res += char('a' + i);
        if (i == state) recSolveD(n - 1, state + 1);
        else recSolveD(n - 1, state);
        res.pop_back();
    }
}

void solveD() {
    int n; cin >> n;
    recSolveD(n, 0);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
   // rwFile();
    solveD();
}


Measured memory_bytes: 1536
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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


	ll N;
	cin >> N;

	if (N % 2) {
		co(0);
	}
	else {
		ll kotae = 0;
		rep(i, 100) {
			ll kazu = 10;
			rep(j, i) kazu *= 5;
			if (kazu > N) break;
			kotae += N / kazu;
		}
		co(kotae);
	}



	Would you please return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;

int main() {
	long long int n=700,m,a,b,c,d,e;
	long double z,w;
	string str,str2,str3;
	char ch;
	long long int x[130]={};
	cout << fixed << setprecision(10);
	cin>>a>>b>>c;
	a-=b;
	cout<<a%c;






	cout<<endl;
} 


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

int main() {
    int n;
    scanf("%d", &n);
    if (n % 1000 == 0)
        printf("0\n");
    else 
        printf("%d\n", 1000-(n%1000));
    return 0;
}

Measured memory_bytes: 3788
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
int main(){
  int N, M, R;
  cin >> N >> M >> R;
  vector<int> r(R);
  rep(i, R) {
    cin >> r[i];
    r[i]--;
  }
  vector<int> A(M), B(M), C(M);
  rep(i, M) {
    cin >> A[i] >> B[i] >> C[i];
    A[i]--;
    B[i]--;
  }
  vector<vector<int>> to(N, vector<int>(N, 1e9));
  rep(i, N) to[i][i] = 0;
  rep(i, M) {
    to[A[i]][B[i]] = C[i];
    to[B[i]][A[i]] = C[i];
  }
  rep(i, N) rep(j, N) rep(k, N)
    chmin(to[j][k], to[j][i]+to[i][k]);
  sort(r.begin(), r.end());
  int ans = 1e9;
  do {
    int tmp = 0;
    rep(i, R-1)
      tmp += to[r[i]][r[i+1]];
    chmin(ans, tmp);
  } while(next_permutation(r.begin(), r.end()));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;

vector<int> s;

int binarysearch(int x, int mini, int maxi) {
  if (mini >= maxi) return 0;
  int i = mini + (maxi - mini) / 2;
  if (x == s[i]) return 1;
  else if (x < s[i]) binarysearch(x, mini, i);
  else binarysearch(x, i+1, maxi);
}

int main() {
  int n, q;
  cin >> n;
  rep(i, n) {
    int m;
    cin >> m;
    s.push_back(m);
  }
  sort(s.begin(), s.end());
  cin >> q;
  int ans = 0;
  rep(i, q) {
    int t;
    cin >> t;
    ans += binarysearch(t, 0, n);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3440
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef std::pair<int, int> ii;
typedef tuple<int,int,int> i3;
typedef std::pair<int, ii> iii;
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
typedef std::vector<ii> vii;
typedef std::vector<iii> viii;
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define all(x) (x).begin(), (x).end()

ll g(ll a, ll k){
  if (a<k) return 0;
  else if (a%k==0) return a/k;
  else {
    ll floor=a/k;
    ll l=1;
    ll r=1000000000;
    while (r-l>1){
      ll mid=(r+l)/2;
      if ((a-mid*(floor+1))/k==floor) l=mid;
      else r=mid;
    }
    return g(a-l*(floor+1),k);
  }
}


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  ll N, a, k;
  cin >> N;
  ll ans=0;
  for (int i=0; i<N; i++){
    cin >> a >> k;
    ans=ans^g(a,k);
  }  
  if (ans==0) cout<<"Aoki"<<endl;
  else cout<<"Takahashi"<<endl;



  




}


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


int main()
{
 ll n;
  cin>>n;
  ll arr[n];
  for(ll i=0;i<n;i++)
  {
   cin>>arr[i];
  }
  ll count=0;
  for(ll i=0;i<(n-2);i++)
  {
   for(ll j=i+1;j<(n-1);j++)
   {
     for(ll k=j+1;k<n;k++)
     {
      ll a=arr[i],b=arr[j],c=arr[k];
      //cout<<"in for"<<" "<<"a="<<a<<" "<<"b="<<b<<" "<<"c="<<c<<endl;
       if(a!=c && a!=b && b!=c && (a+b)>c && (a+c)>b && (b+c)>a)
       {
         count++;
         //cout<<"count="<<count<<endl;
       }
     }
   }
  }
  cout<<count<<endl;
  return 0;

}


Measured memory_bytes: 3616
#include <iostream>
#include <cmath>
#include <iomanip>
const double pi (3.14159265358979323846264338327);
using namespace std;
double angle(int hour,int min);

int main()
{
    double a,b,h,m;
    cin>>a>>b>>h>>m;
    double angle_h=angle(h,m);
    double s;
    //cout<<angle<<endl;
    //cout<<cos(angle*pi/180.0)<<endl;
    s=a*a+b*b-2*a*b*cos(angle_h*pi/180.0);
    cout<<fixed<<setprecision(20)<<sqrt(s)<<endl;
    return 0;
}
double angle(int hour,int min)
{
	double h,m,ret;
	h = (hour+min/60.0)*30;//时针的角度复，制每小时30度
	m = 6*min;//分针的角度，每分钟知6度
	ret = fabs(h-m);
	ret = ret>180?360-ret:ret;
	return ret;
}


Measured memory_bytes: 4220
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

constexpr int atcoder_mod = 1e9+7;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

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

	int N=in(),M=in();
	if(N>=M){
		cout << 0 << endl;
		return 0;
	}
	vector<int> X(M);
	vector<ll> S(M-1);
	REP(i,M){
		X[i]=in();
	}
	sort(ALL(X));
	REP(i,M-1){
		S[i] = X[i+1]-X[i];
	}
	sort(ALL(S),greater<ll>());
	REP(i,N-1){
		S[i] = 0;
	}
	
	cout << accumulate(ALL(S),0LL) << endl;
	return 0;
}


Measured memory_bytes: 1408
//Be Name Khoda
//man az biganegan  hargez  nanalam
//ke harche kard ba man ashena kard
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma optimize O3
using namespace __gnu_pbds;
using namespace std;
template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using ordered_multiset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long int LL;
typedef LL ll;
typedef long double ld;
typedef string str;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef stringstream strs;
 
#define X first
#define Y second
#define PB push_back
#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 smax(a,b) a=max(a,b)
#define smin(a,b) a=min(a,b)
#define SZ(a) ((ll)a.size())
#define ER(a) cout << #a << ' ' << a << endl
#define LB(a,n,x) (lower_bound(a,(a)+(n),x)-(a))
#define RET(x) { cout << x; exit(0); }
#define MKP make_pair
#define RETD(x) { cout << fixed << setprecision(15) << x; exit(0); }
#define GEI(x) scanf("%d",&x)
#define GEL(x) scanf("%lld",&x)
#define ALL(x) x.begin(),x.end()
const ll M=4e6+5,LG=32,SM=600+5,inf=1e18+5;
ll mod=1e9+7;

bitset<M> kle;
ll su,n;

int main()
{
    cin >> n;
    kle[0]=1;
    For(i,0,n)
    {
        ll x;
        GEL(x);
        su+=x;
        kle=kle|(kle<<x);        
    }
    su=su/2+su%2;
    while (1)
    {
        if (kle[su]) RET(su);
        su++;
    }
}

Measured memory_bytes: 2304
#include<bits/stdc++.h>
#define ll long long
#define lb long double
using namespace std;


int main()
{
	string s;
	cin >> s;
	ll a[4];
	for(int i=0;i<4;i++)
		{
			a[i]=count(s.begin(),s.end(),s[i]);
		}
	bool ans=true;
	for(int i=0;i<4;i++)
		{
			if(a[i]!=2){ans=false;break;
			}
		}
	cout<<(ans?"Yes":"No");
	return 0;
}

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

#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

constexpr int mod = 1e9 + 7;
constexpr int32_t inf = 1001001001;
constexpr int64_t infll = 1001001001001001001ll;
constexpr int dx[] = {0, -1, 1, 0, -1, 1, -1, 1}, dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const string YES = "YES", NO = "NO", Yes = "Yes", No = "No", yes = "yes", no = "no";

// clang-format off
// ostream &operator<<(ostream &os, __int128_t value) { if (ostream::sentry(os)) { __uint128_t tmp = value < 0 ? -value : value; char buffer[64]; char *d = end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); }} return os; }
// istream &operator>>(istream &is, __int128_t &value) { string in; is >> in; value = 0; for (const char &c : in) { if ('0' <= c && c <= '9') value = 10 * value + (c - '0'); } if (in[0] == '-') value *= -1; return is; }
// ostream &operator<<(ostream &os, __uint128_t value) { if (ostream::sentry(os)) { char buffer[64]; char *d = end(buffer); do { --d; *d = "0123456789"[value % 10]; value /= 10; } while (value != 0); int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); }} return os; }
// istream &operator>>(istream &is, __uint128_t &value) { string in; is >> in; value = 0; for (const char &c : in) { if ('0' <= c && c <= '9') value = 10 * value + (c - '0'); } return is; }
template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { os << v[0]; for (int i = 1; i < v.size(); ++i) os << " " << v[i]; return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.fs << " " << p.sc; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.fs >> p.sc; return is; }

struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup;

inline int64_t in() { int64_t x = 0; cin >> x; return x; }

template <typename T> void sort(vector<T> &v) { sort(all(v)); }
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 T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// clang-format on

bool ukunichia(int n) {}

signed main(int argc, char *argv[]) {
  int a = in(), b = in();

  int ans = 0;
  for (int i = a; i <= b; ++i) {
    if (i % 10 == 0) continue;
    string s = to_string(i), t = s;
    reverse(all(t));

    ans += s == t;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))

tab_sum = [0]
sum_tmp = 0
for Ai in A:
    sum_tmp += Ai
    tab_sum.append(sum_tmp)

cnt = {}
for item in tab_sum:
    key = str(item % M)
    cnt.setdefault(key, 0)
    cnt[key] += 1

    
ans = 0
for key, val in cnt.items():
    ans += val * (val - 1) // 2

print(ans)

Measured memory_bytes: 19244
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <iostream>
#include <climits>
#include <cstring>
#include <functional>
#include <iomanip>

using namespace std;

//using ll = long long;
#define rep(i, N) for(int i = 0;i < (int)N;i++)
#define LARGE INT_MAX / 2
#define PI 3.1415926535897932384626433832795

int n, m, x, y;

int a[100];
int b[100];

int main() {
	cin >> n >> m >> x >> y;
	rep(i, n) {
		cin >> a[i];
	}
	rep(i, m) {
		cin >> b[i];
	}
	sort(a, a + n);
	sort(b, b + m);
	if (min(y, b[0]) > max(x, a[n - 1])) {
		cout << "No War" << endl;
	}
	else {
		cout << "War" << endl;
	}


	return 0;
}

Measured memory_bytes: 256
<?php
define("MOD", 10**9+7);
define("MAX", 10**5);
fscanf(STDIN, "%d%d", $n, $k);
$A = array_map("intval", explode(" ", fgets(STDIN)));
sort($A);

$f[0] = $invf[0] = $invf[1] = 1;
for($i = 1; $i <= $n; $i++)$f[$i] = $f[$i-1]*$i%MOD;
for($i = 2; $i <= $n; $i++)$invf[$i] = (MOD - intdiv(MOD, $i))*$invf[MOD%$i]%MOD;
for($i = 2; $i <= $n; $i++)$invf[$i] = $invf[$i]*$invf[$i-1]%MOD;;
$ans = 0;
foreach($A as $i => $a){
    if($n-$i-1 >= $k-1){
        $ans = ($ans - $a * nCm($n-$i-1, $k-1))%MOD;
    }
}
$A = array_reverse($A);
foreach($A as $i => $a){
    if($n-$i-1 >= $k-1){
        $ans = ($ans + $a * nCm($n-$i-1, $k-1))%MOD;
    }
}
echo (($ans%MOD)+MOD)%MOD;
function nCm($n, $m){
    global $f, $invf;
    return $f[$n] * $invf[$n-$m] % MOD * $invf[$m] % MOD;
}


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

#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 reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

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

template <int mod>
struct ModInt {
  int x;
  ModInt(): x(0) {}
  ModInt(long long a) { x = a % mod; if (x < 0) x += mod; }
  ModInt &operator+=(ModInt that) { x = (x + that.x) % mod; return *this; }
  ModInt &operator-=(ModInt that) { x = (x + mod - that.x) % mod; return *this; }
  ModInt &operator*=(ModInt that) { x = (long long) x * that.x % mod; return *this; }
  ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
  ModInt inverse() {
    int a = x, b = mod, u = 1, v = 0;
    while (b) { int t = a / b; a -= t * b; u -= t * v; swap(a, b); swap(u, v); }
    return ModInt(u);
  }
  #define op(o, p) ModInt operator o(ModInt that) { return ModInt(*this) p that; }
    op(+, +=) op(-, -=) op(*, *=) op(/, /=)
  #undef op
  friend ostream& operator<<(ostream &os, ModInt m) { return os << m.x; }
};

using mint = ModInt<998244353>;

mint dp[3001][3001];

void solve() {
  int n, s;
  cin >> n >> s;
  vi32 a(n);
  cin >> a;
  dp[0][0] = 1;
  rep(i, n) repc(j, s) {
    dp[i+1][j] += dp[i][j] * 2;
    if (j+a[i]<=s) dp[i+1][j+a[i]]+=dp[i][j];
  }
  cout << dp[n][s] << endl;
}


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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    rep(i, N) {
        cin >> A[i];
        B[i] = A[i];
    }
    sort(B.begin(), B.end());
    int can1 = B[N / 2 - 1];
    int can2 = B[N / 2];
    rep(i, N) {
        if (A[i] <= can1)
            cout << can2 << endl;
        else if (A[i] >= can2)
            cout << can1 << endl;
    }
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
# define ll long long int
									//nestedcode
vector<ll> adj[100000];				
ll vis[100000];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,i,a,c,t,r,aaa=0,mx=LLONG_MIN;
	cin>>n;
	ll aa[n+5];
	queue<ll> q;
	map<ll,ll> m;
	for(i=0;i<n-1;i++){
		cin>>a>>c;
		
		adj[a].push_back(c);
		adj[c].push_back(a);
	}
	for(i=1;i<=n;i++){
		cin>>aa[i];
		aaa+=aa[i];
		mx=max(mx,aa[i]);
	}
	sort(aa+1,aa+n+1);
	reverse(aa+1,aa+n+1);
	q.push(1);
	
	vis[1] = 1;
	t=1;
	m[1] = aa[t];
	t++;
	while(!q.empty()){
		r=q.front();
		q.pop();
		for(i=0;i<(ll)adj[r].size();i++){
			if(vis[adj[r][i]]==0){
				vis[adj[r][i]]=1;
				q.push(adj[r][i]);
				m[adj[r][i]] = aa[t];
				t++;
			}
		}
	}
	cout<<aaa-mx<<endl;
	for(i=1;i<=n;i++){
		cout<<m[i]<<" ";
	}
}
	
	

Measured memory_bytes: 3968
gcm :: Int -> Int -> Int
gcm a b | a < b     = gcm b a
        | b == 0    = a
        | otherwise = gcm b (a`mod`b)

lcm' :: Int -> Int -> Int
lcm' a b = (a * b) `div` (gcm a b)

solv :: String -> String
solv s = (show $ gcm a b) ++ " " ++ (show $ lcm' a b)
  where (a:b:_) = map read . words $ s

main = interact (unlines.map solv.lines)

Measured memory_bytes: 4076
a = int(input())
b = int(input())
c = int(input())
x = int(input())

cnt = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i*500 + j*100 + k*50 == x:
                cnt += 1

print(cnt)

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

using namespace std;

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

int N, Q;
string table;
vector<pair<char, char>> qs;

bool check(int x) {
  int now = x;
  REP(i,Q) if (qs[i].first == table[now]) {
    char dir = qs[i].second;
    if (dir == 'L') {
      now--;
      if (now < 0) return true;
    } else {
      now++;
      if (N <= now) return false;
    }
  }
  return false;
}

// (lb, ub]
int search() {
  int low = -1, high = N;
  while (high - low > 1) {
    int mid = (high + low) / 2;
    if (check(mid)) low = mid; else high = mid;
  }
  return high;
}

bool rcheck(int x) {
  int now = x;
  REP(i,Q) if (qs[i].first == table[now]) {
    char dir = qs[i].second;
    if (dir == 'L') {
      now--;
      if (now < 0) return false;
    } else {
      now++;
      if (N <= now) return true;
    }
  }
  return false;
}

// (lb, ub]
int rsearch() {
  int low = -1, high = N;
  while (high - low > 1) {
    int mid = (high + low) / 2;
    if (rcheck(mid)) high = mid; else low = mid;
  }
  return high;
}

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

  qs.resize(Q);
  REP(i,Q) cin >> qs[i].first >> qs[i].second;

  int l = search();
  int r = rsearch();
  cout << N - (l + 1 + (N - 1 - r)) << endl;

  return 0;
}


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

using namespace std;
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
//#define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main(){
    IOS;
    long long a,b,c,d;

    long long ans=0;
    cin >> a >> b >> c >> d;

    long long g = __gcd(c,d);
    long long l = (c*d)/g;
    ans= b-a+1-(b/c-(a-1)/c)-(b/d-(a-1)/d)+(b/l-(a-1)/l);


cout << ans << endl;
return 0;}


Measured memory_bytes: 256
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        diag = [[None for j in range(151)] for i in range(151)]
        for i in range(1, len(diag)):
            for j in range(1, len(diag[0])):
                if i >= j:
                    continue
                diag[i][j] = i * i + j * j
        while True:
            h, w = map(int, raw_input().split())
            if h == 0 and w == 0:
                break
            m = (float('inf'), float('inf'), float('inf'))
            for i in reversed(range(1, len(diag))):
                for j in reversed(range(1, len(diag[0]))):
                    if diag[i][j] is not None and diag[i][j] >= h * h + w * w:
                        if diag[i][j] == h * h + w * w:
                            if h < i <= m[0]:
                                m = (i, j, diag[i][j])
                        elif m[2] == diag[i][j]:
                            if i < m[0]:
                                m = (i, j, diag[i][j])
                        elif m[2] > diag[i][j]:
                            m = (i, j, diag[i][j])

            print '{0} {1}'.format(m[0], m[1])
                        
                        
        
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Measured memory_bytes: 5136
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;

int a[10];
int main(){
	for(int i = 0; i < 4; i++)
		scanf("%d", &a[i]);
	sort(a, a + 4);
	if(a[0] == 1 && a[1] == 4 && a[2] == 7 && a[3] == 9) puts("YES");
	else puts("NO");
}

Measured memory_bytes: 256
#include<iostream>
#include <stdio.h>
#include<string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdint>
#include <map>
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main(){

  ll n;
  cin >> n;
  
  ll a[200010];
  
  for(ll i = 1; i <= n; i++){
    int num;
    cin >> num;
    a[num] = i;
  }

  ll ans = 0;
  ll countf = 1;
  for(ll i = 1; i< n; i++){
    if(a[i] < a[i+1]) countf++;
    else			 {
      ans = max(countf,ans);
      countf = 1;
    }
  }
  
  if(countf == n) {cout << 0 << endl; return 0;}
  
  cout << n-ans << endl;
    
return 0;
}

Measured memory_bytes: 1792
# input
x, y = [int(i) for i in input().split()]
s = [input() for i in range(x)]

ans = []

r0 = ''
for i in range(y+2):
    r0 += '#'
ans.append(r0)

for ss in s:
    ans.append('#' + ss + '#')

ans.append(r0)

for a in ans:
    print(a)

Measured memory_bytes: 3060
//go:generate echo "https://atcoder.jp/contests/dp/tasks/dp_a"
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
)

type scanner struct{ *bufio.Scanner }

func newScanner(r io.Reader) *scanner {
	s := bufio.NewScanner(r)
	s.Split(bufio.ScanWords)
	s.Buffer(nil, 100000000)
	return &scanner{s}
}

func (s *scanner) Int() int {
	s.Scan()
	n, _ := strconv.Atoi(s.Text())
	return n
}

func (s *scanner) IntSlice(l int) []int {
	if l == 0 {
		return []int{}
	}
	sl := make([]int, l, l)
	for i := range sl {
		sl[i] = s.Int()
	}
	return sl
}

func iabs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func solve(n int, heights []int) int {
	t := make([]int, n+1, n+1)
	for i := range t {
		t[i] = math.MaxInt64
	}

	t[0] = 0
	for i := 1; i < n; i++ {
		if v := t[i-1] + iabs(heights[i]-heights[i-1]); v < t[i] {
			t[i] = v
		}
		if 1 < i {
			if v := t[i-2] + iabs(heights[i]-heights[i-2]); v < t[i] {
				t[i] = v
			}
		}
	}

	return t[n-1]
}

func main() {
	sc := newScanner(os.Stdin)
	n := sc.Int()
	heights := sc.IntSlice(n)
	ans := solve(n, heights)
	fmt.Println(ans)
}


Measured memory_bytes: 3792
import scala.io.StdIn._
import scala.annotation.tailrec

object Main extends App {
  val mod: Long => Long = _ % 1000000007L
  val Array(n, k) = readLine().split(" ").map(_.toInt)

  def sum(l: Long, r: Long): Long = {
    (l + r) * (r - l + 1) / 2
  }

  var ans = 0L
  for {
    i <- k to n + 1
  } yield {
    val min = sum(0, i - 1)
    val max = sum(n - i + 1, n)
    ans = mod(ans + (max - min + 1))
  }
  println(ans)
}


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

#define ll long long
#define INF 99999999
#define INF_LL 1LL << 60
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

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 (b<a) { a=b; return 1; } return 0; }

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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

    ll ans = 0;
    if( N*2 <= M )
    {
        ans += N;
        M -= N*2;
    }
    else
    {
        ans += M/2;
        M = 0;
    }
    ans += M/4;
    cout << ans << endl;
}


Measured memory_bytes: 256
/*
ID: techiah1
PROG: test
LANG: C++
*/
#define _CRT_SECURE_NO_WARNINGS
#pragma _attribute_((optimize("-O2")))
#pragma comment(linker, "/STACK:102400000,102400000")

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <cstdio>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <time.h>
#include <iomanip>

//#define Local

using namespace std;

const int N = 100010, M = N + 10;

struct node
{
	int next = -1;
	int to, w;
}edge[2 * M];
int head[N];
long long dist[N];
int cnt;
void inserts(int u, int v, int w)
{
	edge[cnt].w = w;
	edge[cnt].to = v;
	edge[cnt].next = head[u];
	head[u] = cnt++;
	edge[cnt].w = w;
	edge[cnt].to = u;
	edge[cnt].next = head[v];
	head[v] = cnt++;
}
void init()
{
	memset(head, -1, sizeof(head));
	cnt = 0;
}
void SPFA(int u)
{
	int x, y, w;
	bool vis[N];
	memset(dist, 0x3f, sizeof(dist));
	dist[u] = 0;
	memset(vis, false, sizeof(vis));
	queue<int> q;
	while (!q.empty())q.pop();
	q.push(u);
	while (!q.empty())
	{
		x = q.front();  q.pop();
		vis[x] = false;
		for (int i = head[x]; i != -1; i = edge[i].next)
		{
			w = edge[i].w;  y = edge[i].to;
			if (dist[x] + w<dist[y])
			{
				dist[y] = dist[x] + w;
				if (!vis[y])
					q.push(y);
				vis[y] = true;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input1.txt", "r", stdin);
	//freopen("output1.txt", "w", stdout);

	int n;
	cin >> n;
	init();
	for(int i=1;i<n;i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		inserts(u, v, w);
		//inserts(v, u, w);
	}
	int q, w;
	cin >> q >> w;
	SPFA(w);
	for(int i=0;i<q;i++)
	{
		int a, b;
		cin >> a >> b;
		cout << dist[a] + dist[b] << endl;
	}

	return 0;
}

Measured memory_bytes: 5376
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include <iomanip>
#include <string>
#include <string.h>
#include <deque>
#include <queue>
#include <stack>

using namespace std;

#define For(i, s, n) for (int i = s; i <= n; ++i)
#define ForD(i, s, n) for (int i = s; i >= n; --i)
#define ForV(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
#define sz(a) ((int)(a).size())
#define ii pair<int, int>
#define fi first
#define se second

typedef long long ll;

const int N = 1e5 + 5, LIMIT = 1e9 + 7;

vector <int> a[N];
int p[N], vis[N];
int n, m, res = 0, cnt = 0, root;

void Read()
{
    //freopen("EQUALS.INP", "r", stdin);
    //freopen("EQUALS.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int u, v;
    cin >> n >> m;
    For (i, 1, n)
    {
        cin >> p[i];
    }
    For (i, 1, m)
    {
        cin >> u >> v;
        a[u].pb(v);
        a[v].pb(u);
    }
}

void Dfs(int u)
{
    if (root == u)
    {
        ++res;
    }
    vis[u] = cnt;
    ForV (j, a[u].size())
    {
        int v = a[u][j];
        if (!vis[v])
        {
            Dfs(v);
        }
    }
}

void Process()
{
    ms(vis, 0);
    For (i, 1, n)
    {
        if (!vis[i])
        {
            root = p[i];
            ++cnt;
            Dfs(i);
        }
        else
        {
            if (vis[i] == vis[p[i]] || i == p[i])
            {
                ++res;
            }
        }
    }
    cout << res;
}

int main()
{
    Read();
    Process();
    return 0;
}


Measured memory_bytes: 8576
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  int sum = 0;
  rep(i, N) {
    cin >> A[i];
    sum += A[i];
  }
  int ans = 0;
  
  auto chans = [&](int n) {
    vector<int> v = A;
    rep(i, N) v[i] %= n;
    sort(v.begin(), v.end());
    vector<ll> minus(N+1), plus(N+1);
    rep(i, N)
      minus[i+1] = minus[i]+v[i];
    for(int i=N; i>0; i--)
      plus[i-1] = plus[i]+(n-v[i-1])%n;
    rep(i, N+1) {
      if(!(abs(minus[i]-plus[i])%n)) {
        if(max(minus[i], plus[i]) <= K) {
          chmax(ans, n);
          break;
        }
      }
    }
  };
  
  for(int i=1; i*i<=sum; i++) {
    if(!(sum%i)) {
      chans(i);
      chans(sum/i);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define maxn 100000
using namespace std;

int n,ans;
int ar[maxn][3];
int dp[maxn][3];

int main() {
	cin >> n;
	for( int i = 0 ; i < n ; i++ )
		for( int j = 0 ; j < 3 ; j++ )
			cin >> ar[i][j];
	for( int i = 0 ; i < 3 ; i++ )
		dp[0][i] = ar[0][i];
	for( int i = 1 ; i < n ; i++ )
		for( int j = 0 ; j < 3 ; j++ )
			for( int k = 0 ; k < 3 ; k++ )
				if( j != k )
					dp[i][j] = max( dp[i][j] , dp[i-1][k] + ar[i][j] );
	for( int i = 0 ; i < 3 ; i++ )
		ans = max( ans , dp[n-1][i] );
	cout << ans << endl;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i,N) cin >> A[i];

  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());

  ll ans = 0;
  priority_queue<int> q;
  q.push(A[0]);
  for (int i = 1; i < N; i++) {
    ans += q.top();
    q.pop();
    q.push(A[i]);
    q.push(A[i]);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 5020
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <string>

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

ll t[200000] = {};
int main() {
	ll N, T; cin >> N >> T;

	ll cnt = 0;
	repe(i, 1, N) {
		ll p; cin >> p;
		t[i] = p;

		cnt += min(t[i] - t[i - 1], T);
	}
	cout << cnt + T << endl;

	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
ifstream fin("date.in");
int n, m, t, lin[300100], col[300100], lin_max, col_max, l, c, a[300100], b[300100];

int main() {
	cin >> n >> m >> t;
	for (int i = 1; i <= t; i++) {
		cin >> a[i] >> b[i];
		lin[a[i]]++;
		col[b[i]]++;
		lin_max = max(lin_max, lin[a[i]]);
		col_max = max(col_max, col[b[i]]);
	}

	int lines_same = 0, cols_same = 0;
	for (int i = 1; i <= n; i++)
		if (lin[i] == lin_max)
			lines_same++;
	for (int i = 1; i <= m; i++)
		if (col[i] == col_max)
			cols_same++;

	long long total = (long long)lines_same * cols_same;
	for (int i = 1; i <= t; i++)
		if (lin[a[i]] == lin_max && col[b[i]] == col_max)
			total--;

	if (total > 0)
		cout << lin_max + col_max;
	else
		cout << lin_max + col_max - 1;
    return 0;
}


Measured memory_bytes: 8288