akhauriyash/Code-Regression huggingface dataset:
/***
 ** " Experience is the name everyone gives to their mistakes. "
 ** 	-- Oscar Wilde
***/

/**
  *  Author: dhruv_gheewala
  *  Date:   14.03.2020
  *  Time:   02:09:30
**/

#define DEBUG
#if __has_include("debug.h")
    #include "debug.h"
#else
    #include<bits/stdc++.h>
    using namespace std;

    #define p(str) 42
    #define o(str) 108
    #define fundri 137
    #define d(...) 1729
#endif

typedef unsigned int ui;
typedef long long int ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

const bool testcases = 0;
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define test int __T__=1;if(testcases)cin>>__T__;while(__T__--)
#define nl cout<<'\n'
#define pb push_back
#define pop pop_back
#define all(s) s.begin(),s.end()
#define ff first
#define ss second
#define sort_by(cont,expr) sort(all(cont),[&](const auto &lhs,const auto &rhs){return expr;})

#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=(n)-1;~i;i--)
#define loop(i,l,r) for(int i=l;i<r;i++)
#define rloop(i,r,l) for(int i=r;i>l;i--)

ll seed;auto random_address=[]{char *p=new char;delete p;return (uint64_t)p;};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()*(random_address()|1));
inline int rnd(int l=0,int r=INT_MAX){return uniform_int_distribution<int>(l,r)(rng);}

template<typename T,typename U>inline bool exist(T cont,U val){return cont.find(val)!=cont.end();}
template<typename T>bool isPrime(T n){for(T i=2;i*i<=n;i++)if(n%i==0)return 0;return 1;}
template<typename TAIL>inline void inp(TAIL& T){cin>>T;}
template<typename HEAD,typename... TAIL>inline void inp(HEAD &H,TAIL&... T){cin>>H;inp(T...);}
template<typename T>inline bool in_range(T a,T l,T r){return (a>=l&&a<=r);}
template<typename T,typename U>inline istream& operator >>(istream& in,pair<T,U> &a){in>>a.ff>>a.ss;return in;}
template<typename T>inline istream& operator >>(istream& in,vector<T> &a){for(auto &x : a)in>>x;return in;}

int main()
{
    std::chrono::time_point<std::chrono::high_resolution_clock> start_time, end_time;
    start_time = std::chrono::high_resolution_clock::now();

    #ifdef DHRUV_GHEEWALA
        freopen("INPUT.txt","r",stdin);
        freopen("OUTPUT.txt","w",stdout);
        freopen("DEBUG.txt","w",stderr);
    #endif
    
    fast;
    int n;
    test{
    
    cin>>n;
    vi h(n);
    cin>>h;

    vi dp(n+1,INT_MAX);
    dp[0]=0;
    rep(i,n)
    {
        if(i+1<n)
            dp[i+1]=min(dp[i]+abs(h[i+1]-h[i]),dp[i+1]);
        if(i+2<n)
            dp[i+2]=min(dp[i]+abs(h[i+2]-h[i]),dp[i+2]);
        d(dp);
    }
    d(dp);
    cout<<dp[n-1],nl;
    fundri;
    
    }

    end_time = std::chrono::high_resolution_clock::now();
    ll elapsed_time = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
    o("\n\n======\n");
    o("Elapsed Time: "<<elapsed_time<<" ms\n");

    return 0;
}

Measured memory_bytes: 1024
n, t = map(int, input().split())
tList = list(map(int, input().split()))
tSum = t

for i in range(n-1):
    if tList[i+1] - tList[i] > t:
        tSum += t
    else:
        tSum += tList[i+1] - tList[i]

print(tSum)


Measured memory_bytes: 26708
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_temp>
using smaller_queue = priority_queue<Q_temp, vector<Q_temp>, greater<Q_temp>>;

const ll MOD = (ll)(1e9 + 7);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

const ll MAX_V = 200010;

class dijkstra
{
public:
  struct edge
  {
    ll to;
    ll cost;
  };

  vector<edge> E[MAX_V];
  ll d[MAX_V];

  void calc(ll s)
  {
    priority_queue<pll, vector<pll>, greater<pll>> que;
    rep(i, MAX_V) d[i] = LINF;
    que.emplace(0LL, s);
    d[s] = 0LL;
    while (!que.empty())
    {
      pll p = que.top();
      que.pop();
      ll v = p.second;
      if (d[v] < p.first)
        continue;

      for (auto &&e : E[v])
      {
        if (d[e.to] > d[v] + e.cost)
        {
          d[e.to] = d[v] + e.cost;
          que.emplace(d[e.to], e.to);
        }
      }
    }
  }
};

dijkstra ds;

vector<int> ch[100010];
int par[100010];
int len[100010];

int dfs(int v)
{
  int Max = 0;
  for (auto c : ch[v])
  {
    Max = max(Max, dfs(c) + 1);
  }
  len[v] = Max;
  return len[v];
}

int main()
{
  int n, u, v;
  cin >> n >> u >> v;
  dijkstra ds;
  rep(i, n - 1)
  {
    int a, b;
    cin >> a >> b;
    ds.E[a].push_back({b, 1});
    ds.E[b].push_back({a, 1});
  }
  ds.calc(v);
  for (int i = 1; i <= n; ++i)
  {
    for (auto t : ds.E[i])
    {
      if (ds.d[t.to] == ds.d[i] + 1)
      {
        ch[i].push_back(t.to);
        par[t.to] = i;
      }
    }
  }
  dfs(v);

  int ans = 0;
  int now = u;
  rep(i, (ds.d[u] - 1) / 2)
  {
    ans++;
    now = par[now];
  }

  while (len[now] != 0)
  {
    int Max = -1;
    int t;
    for (auto c : ch[now])
    {
      if (Max < len[c])
      {
        Max = len[c];
        t = c;
      }
    }
    ans++;
    now = t;
  }

  bool up = true;
  while (ds.d[now] > ans)
  {
    if (up)
    {
      now = par[now];
    }
    else
    {
      now = ch[now][0];
    }
    up ^= 1;
    if (ds.d[now] != ans)
      ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 26368
#include<bits/stdc++.h>
using namespace std;
int n,m,cc,bit[100005]; 
vector<int>g[100005];
void add(int p,int x){while(p<=m)bit[p]+=x,p+=(p&(-p));}
int sum(int p){int res=0;while(p)res+=bit[p],p-=(p&(-p));return res;}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		g[r-l+1].push_back(l);
	}
	int ans=n;
	for(int i=1;i<=m;i++)
	{
		int res=0;
		for(int j=0;j<g[i].size();j++)
		{
			add(g[i][j],1);
			add(g[i][j]+i,-1);
			ans--;
		}
		for(int j=i;j<=m;j+=i)res+=sum(j);
		printf("%d\n",ans+res);
	}
	return 0;
}

Measured memory_bytes: 6784
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
#define Fi first
#define Se second
using namespace std;
static const LL INF = 1LL<<61LL;
typedef pair<int,int> PII;

int N,M;
int A[100010];
int temp=1;
int ans;

int main(){
    cin>>N>>M;
    rep(i,M){
        int a;
        cin>>a;
        A[a]=1;
    }
    FOR(i,1,N){
        //cout<<temp<<endl;
        if(A[i]==1){
            if(temp==1&&A[1]!=1){
                int t=(i-temp);
                temp=i;
                ans=max(ans,t);
                continue;
            }
            int t=(i-temp-1)/2;
            if(i-temp-1<=0)t=0;
            else if((i-temp-1)%2!=0)t++;
            temp=i;
            ans=max(ans,t);
        }
        else if(i==N){
            ans=max(ans,N-temp);
        }
    }
    cout<<ans<<endl;
}

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

int main() {
  string s, t, u;
  cin >> s >> t >> u;
  s.at(0) = toupper(s.at(0));
  t.at(0) = toupper(t.at(0));
  u.at(0) = toupper(u.at(0));

  cout << s.at(0) << t.at(0)<< u.at(0) << endl;
}


Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,a[100002]={};
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	n+=2;
	int sum=0;
	for(int i=1;i<n;i++)
		sum+=abs(a[i]-a[i-1]);
	for(int i=1;i<n-1;i++)
		cout<<sum-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1])<<endl;
}


Measured memory_bytes: 1664
//This code was made by Chinese_zjc_.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#define int long long
#define INF 0x3fffffffffffffff
using namespace std;
int a,b;
signed main()
{
	std::ios::sync_with_stdio(false);
	cin>>a>>b;
	if(a<10&&b<10&&a>0&&b>0)
	{
		cout<<a*b;
	}
	else
	{
		cout<<-1;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(A) (A).begin(),(A).end()
#define ll long long
const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;

int main(void){
	int N;
	cin >> N;
	int A[N+1],B[N+1];
	for(int i=0;i<N+1;i++)cin >> A[i];
	for(int i=0;i<N;i++)cin >> B[i];
	ll ans = 0;
	for(int i=0;i<N;i++){
		if(B[i]>A[i]){
			ans += A[i];
			int tmp = B[i]-A[i];
			if(tmp>=A[i+1]){
				ans += A[i+1];
				A[i+1] = 0;
			}else{
				ans += tmp;
				A[i+1] -=tmp;
			}
		}else{
			ans += B[i];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
	int a, b;

	for (;;) {
		scanf("%d %d", &a, &b);
		if (a == 0 && b == 0) {
			break;
		}
		if (a > b) {
			printf("%d %d\n", b, a);
		}
		else {
			printf("%d %d\n", a, b);
		}
	}

	return 0;
}

Measured memory_bytes: 596
#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define Yes "Yes"
#define No "No"
#define YESNO OUT(three(solve(),YES,NO))
#define YesNo OUT(three(solve(),Yes,No))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(b-1);i>=(LL)(a);i--)
#define REP(i,b) FOR(i,zero,b)
#define rep REP
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,zero,b)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define zero 0LL
#define all ALL
#define pb emplace_back
#define eb pb
#define int long long
using namespace std;
template<typename T> inline void maximize(T &a, T b) { a = max(a, b); }
template<typename T> inline void minimize(T &a, T b) { a = min(a, b); }
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef int LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef tuple<int, int, int, int> tapu;
typedef vector<tapu> Vtapu;
typedef priority_queue<pr, Vpr, greater<pr> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
const int SIZE1 = 3e5 + 1000;
const int SIZE2 = 5010;
const int SIZE3 = 430;
const int SIZE = SIZE1;
const int MAPSIZE = 40;
const LL p =   998244353;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
typedef pair<ld, ut> pld;
ut N, M, K, L, Q, D, H, W,R;
LL vals[SIZE], answer = zero;
int A[SIZE],B[SIZE];string s[SIZE];
Vpr edges[SIZE];
LL dist[SIZE];
LL C[SIZE];
set<int> withes;
LL solve(){
	cin >> N >>K;
	int used=0;
	int a=0,b=0;
	VI as,bs;
	EFOR(i,K,K+3*N-1){
		if(used<N){
			a+=i;
			used++;
			withes.insert(i);
		}
		else if(used<2*N){
			a+=i;
			used++;
			as.pb(i);
		}else{
			b+=i;
			bs.pb(i);
		}
	}
	if(a>b) return 0;
	LL sta=N-1,stb=N/2-1;
	REP(i,N){
		if(i%2==0){
			A[i]=as[sta];
			C[i]=bs[N-i-1];
			auto it=withes.upper_bound(C[i]-A[i]);
			--it;
			B[i]=(*it);
			withes.erase(it);
			sta-=1;
		}else{
			A[i]=as[stb];
			C[i]=bs[N-i-1];
			auto it=withes.upper_bound(C[i]-A[i]);
			--it;
			B[i]=(*it);
			withes.erase(it);
			stb-=1;
			
		}
	}
	return 1;
}

signed main() {
 
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	string s;
	if(solve()){
		REP(i,N){
			cout << A[i] <<" " << B[i] << " " << C[i] << endl;
			assert(A[i]+B[i]<=C[i]);
		}
	}else{
		cout << -1 << endl;
	}
 
 
	//cin >> N;
	return 0;
 
}


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

#define LL long long
#define RG register

using namespace std;
template<class T> T gi() {
	T x = 0; bool f = 0; char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = 1, c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f ? -x : x;
}
int fx[] = {1, -1, 0, 0};
int fy[] = {0, 0, 1, -1};
int id[25][25];
char ch[100][100];
int f[1000][1000];
int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	int tot = 0, H = gi<int>(), W = gi<int>();
	for (int i = 1; i <= H; i++)
		scanf("%s", ch[i] + 1);
	for (int i = 1; i <= H; i++)
		for (int k = 1; k <= W; k++)
			if (ch[i][k] == '.') id[i][k] = ++tot;
	for (int i = 1; i <= tot; i++)
		for (int j = 1; j <= tot; j++)
			if (i != j) f[i][j] = 1e9;
	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= W; j++)
			if (ch[i][j] == '.') {
				for (int k = 0; k < 4; k++) {
					int x = i + fx[k], y = j + fy[k];
					if (x < 1 || x > H || y < 1 || y > W) continue;
					f[id[i][j]][id[x][y]] = f[id[x][y]][id[i][j]] = 1;
				}
			}
	for (int k = 1; k <= tot; k++)
		for (int i = 1; i <= tot; i++)
			for (int j = 1; j <= tot; j++)
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
	int ans = 0;
	for (int i = 1; i <= tot; i++)
		for (int j = 1; j <= tot; j++)
			ans = max(ans, f[i][j]);
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 1792
import numpy as np
N, K, Q = map(int, input().split())
A = np.array([int(input()) for _ in range(Q)])

ans = np.zeros(N)
ans += K

for a in A:
    ans[a-1] += 1

ans -= Q

for a in ans:
    if a>0:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 17120
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc =  new Scanner(System.in);
		char[] c = sc.next().toCharArray();
		int n = c.length;
		int score = 0;
		int p = 0;
		
		for(int i=0; i<n; i++){
			if(p>0){
				if(c[i] == 'g'){
					score++;
					p--;
				}else{
					p--;
				}
			}else{
				if(c[i] == 'g'){
					p++;
				}else{
					p++;
					score--;
				}
			}
		}
		System.out.println(score);
	}

}

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

int main(){
    long long x;
    cin >> x;
    long long sum=0;
    sum += x/500;
    sum *=1000;
    x = x % 500;
    sum += 5*(x/5);
    cout << sum << endl;
}

Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.math;

void main() {
	auto input = getStdin!(string[])[0].split(" ").to!(real[]);
	real a = input[0];
	real b = input[1];
	real theta = input[2] * PI / 180.0L;
	
	real s = (a * b * sin(theta)) / 2.0L;
	"%.8f".writefln(s);
	real l = a + b + (a.pow(2) + b.pow(2) - 2.0L * a * b * cos(theta)).sqrt;
	"%.8f".writefln(l);
	real h = b * sin(theta);
	"%.8f".writefln(h);
}

T getStdin(T)() {
    string[] cmd;
    string line;
    while ((line = chomp(stdin.readln())) != "") cmd ~= line;
    return to!(T)(cmd);
}

Measured memory_bytes: 2560
#コピペAC
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9
def dfs(cur, a, b, c):
  if cur == N:
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
  return min(ret0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))


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

int main(){
	int a,b,c,x,y;
	cin>>a>>b>>c>>x>>y;
	int ans=0;
	if(2*c>=a+b) ans+=(a+b)*min(x,y);
	else ans+=c*2*min(x,y);
	int r=max(x,y)-min(x,y);
	if(r>0){
		int big=(max(x,y)==x?a:b);
		if(2*c >= big) ans+=big*r;
		else ans+=2*c*r;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;

ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (0 <= x and x < p);
    assert (0 <= y);
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll inv(ll x, ll p) { // p must be a prime, O(log p)
    assert ((x % p + p) % p != 0);
    return powmod(x, p-2, p);
}
constexpr int mod = 1e9+7;
int fact(int n) {
    static vector<int> memo(1, 1);
    if (memo.size() <= n) {
        int l = memo.size();
        memo.resize(n+1);
        repeat_from (i, l, n+1) memo[i] = memo[i-1] *(ll) i % mod;
    }
    return memo[n];
}
int choose(int n, int r) { // O(n) at first time, otherwise O(\log n)
    if (n < r) return 0;
    r = min(r, n - r);
    return fact(n) *(ll) inv(fact(n-r), mod) % mod *(ll) inv(fact(r), mod) % mod;
}

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(n + 1); repeat (i, n + 1) scanf("%d", &a[i]);
    // solve
    int dup[2]; {
        vector<int> used(n, -1);
        repeat (i, n + 1) {
            if (used[a[i] - 1] != -1) {
                dup[0] = used[a[i] - 1];
                dup[1] = i;
                break;
            }
            used[a[i] - 1] = i;
        }
    }
    int l = dup[0];
    int m = dup[1] - (dup[0] + 1);
    int r = n + 1 - (dup[1] + 1);
    repeat_from (k, 1, n + 2) {
        ll result = 0;
        if (k == 1) {
            result = n;
        } else {
            result += choose(l + m + r, k); // none
            result += choose(l + m + r, k - 1); // left
            result += choose(l + m + r, k - 1); // right
            result -= choose(l + r, k - 1); // meet
            result += mod;
            result += choose(l + m + r, k - 2); // both
        }
        printf("%lld\n", result % mod);
    }
    return 0;
}


Measured memory_bytes: 2544
#include<stdio.h>

int main(void){
  int a,b,c;

  scanf("%d %d",&a,&b);

  c = a+b;
  if(c<0) c = -c;

  if(c%2==0)
    printf("%d\n",c/2);
  else
    printf("%d\n",(c+1)/2);

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD ((int)1e9+7)
 
using namespace std;
 
struct matrix
{
	vector<vector<long long> > v;
	int n,m;
	matrix(int n,int m):n(n),m(m),v(vector<vector<long long> >(n))
	{
		for(int i=0;i<n;i++)
			v[i]=vector<long long>(m,0);
	}
	matrix operator *(const matrix& other) const
	{
		matrix res(n,other.m);
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<other.m;j++)
			{
				res.v[i][j]=0;
				for(int k=0;k<other.n;k++)
				{
					res.v[i][j]+=(v[i][k]%MOD)*(other.v[k][j]%MOD);
					res.v[i][j]%=MOD;
				}
			}
		}
		return res;
	}
};
 
matrix poww(matrix b,long long p)
{
	if(p==1)
		return b;
	matrix res=poww(b*b,p/2);
	if(p%2)
		res=res*b;
	return res;
}

int n;
long long k;

int main()
{
	cin >> n >> k;
	matrix mat(n,n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin >> mat.v[i][j];
	mat=poww(mat,k);
	matrix base(n,1);
	for(int i=0;i<n;i++)
		base.v[i][0]=1;
	base=mat*base;
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		ans+=base.v[i][0];
		ans%=MOD;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define ljc 998244353
#define ll long long
using namespace std;
ll mu[1010101],tot,T,p[1010101];
bool vis[1010101];
#define gc getchar
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
inline ll fast_pow(ll a,ll b,ll p){
	ll t=1;
	while (b){
		if (b&1ll) t=t*a%p;
		b>>=1ll;a=a*a%p; 
	} 
	return t;
}
inline void init(ll nx){
    mu[1]=1;
    for (ll i=2;i<=nx;i++){
        if (!vis[i]) p[++tot]=i,mu[i]=-1;
        for (ll j=1;j<=tot&&i*p[j]<=nx;j++){
        	if (i*p[j]>nx) continue;
            vis[i*p[j]]=1;
            if ((i%p[j])==0){
                mu[i*p[j]]=0;
                break;
            }
            mu[i*p[j]]=-mu[i];
        }
    }   
}
ll a[1010101],n,m,sum[1010101],f[1010101];
signed main(){
	init(1000000);
	n=read();
	ll aaa=0;
	for (int i=1;i<=n;i++){
		a[i]=read();aaa=(aaa+a[i])%ljc;
	}
	for (int i=1;i<=n;i++){
		for (ll tmp=1;tmp*tmp<=a[i];tmp++){
			if (a[i]%tmp==0){
				sum[tmp]=(sum[tmp]+a[i])%ljc;
				if (tmp*tmp!=a[i]) sum[a[i]/tmp]=(sum[a[i]/tmp]+a[i])%ljc;
			}
		}
	}
	for (int i=1;i<=1000000;i++) sum[i]=sum[i]*sum[i]%ljc;
	for (int i=1;i<=1000000;i++){
		for (int j=i;j<=1000000;j+=i){
			f[i]=(f[i]+sum[j]*mu[j/i]+ljc)%ljc;
		}
	}
	ll ans=0;
	for (int i=1;i<=1000000;i++){
		ans=(ans+f[i]*fast_pow(i,ljc-2,ljc)%ljc)%ljc;
	}
	cout<<((ans-aaa+ljc)%ljc*(ljc+1)/2%ljc)%ljc;
	return 0;
}

Measured memory_bytes: 30136
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int vector_finder(vector<int> vec, int number) {
  auto itr = find(vec.begin(), vec.end(), number);
  size_t index = distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  int s,a;
  cin >> s;
  a = s;
  vector<int>vec;
  for (int i = 1; i <10000; i++) {
    if (vector_finder(vec,a)) {
      cout << i << endl;
      break;
    }
    vec.push_back(a);
    if (a%2 == 0) {
      a /= 2;
    }
    else {
      a = a*3 + 1;
    }
  }
}  

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

typedef long double ll;
#define    mod      1000000007
#define    speed    ios_base::sync_with_stdio(false);
#define    up       cin.tie(NULL);
#define    pb       push_back
#define    mp       make_pair
#define    T        int t; cin >> t; while(t--)

ll dp[3005][3005] , arr[3005];
int  n, k;

int main(){
   for(int i = 0; i <= 3000; i++){
       for(int j = 0; j <= 3000; j++){
           dp[i][j] = 1.0;
       }
   }
   cin >> n;
   for(int i = 1; i <= n; i++){
       cin >> arr[i];
       dp[0][i] = dp[0][i-1]*arr[i];
   }
   k = n/2;
   if(n%2==0){
       k--;
   }
   for(int i = 1; i <= k; i++){
       for(int j = i; j <= n; j++){
              dp[i][j] = arr[j]*dp[i][j-1] + (1.0-arr[j])*dp[i-1][j-1];
       }
   }
    cout << setprecision(12) << dp[k][n] << '\n';

}

Measured memory_bytes: 141184
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
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; }

void dfs(string red, string blue, string s, map<pair<string, string>, ll>& mp) {
  int i = red.size()+blue.size();
  if (i == s.size()) {
    mp[{red, blue}]++;
    return;
  }
  dfs(red+s[i], blue, s, mp);
  dfs(red, blue+s[i], s, mp);
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  string s;
  cin >> n >> s;
  string s1 = s.substr(0, n), s2 = s.substr(n);
  reverse(s2.begin(), s2.end());
  map<pair<string, string>, ll> mp1, mp2;
  dfs("", "", s1, mp1);
  dfs("", "", s2, mp2);
  ll ans = 0;
  for (auto e : mp1)
    ans += e.second*mp2[e.first];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 89632
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int no_of_input,no_of_ticket;
  int input;
  priority_queue<int> q1;
  cin >> no_of_input >> no_of_ticket;
  for(int i=0;i<no_of_input;i++){
    cin >> input;
    q1.push(input);
  }
  while(no_of_ticket--){
    int a = q1.top();
    q1.pop();
    a/= 2;
    q1.push(a);
  }
  int ans = 0;
  while(q1.size()!=0){
    ans += q1.top();
    q1.pop();
  }
  cout << ans;
}

Measured memory_bytes: 1400
import numpy as np
a = int(input())
b = int(input())
c = int(input())
s = int(input())

num = 0
a_list, b_list, c_list = np.array(range(a+1)), np.array(range(b+1)), np.array(range(c+1))

for al in a_list:
    for bl in b_list:
        for cl in c_list:
            summy = 500*al + 100*bl +50*cl
            if summy==s:
                num += 1
print(num)                

Measured memory_bytes: 14412
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
	int A, B;
	cin >> A >> B;

	if(A>8 || B>8)
		cout << ":(" << endl;
	else
		cout << "Yay!" << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	//while (true) {
	int N =sc.nextInt();
	int L =sc.nextInt();

	int small;
	if(L > 0) {
	    small = L;
	} else {
	    small = L+N-1;
	}
	
	int taste = 0;

	for(int i = 1; i <= N; i++) {
	    int k = L+i-1;
	    //System.out.println(k);
	    if(k == 0) small = 0;
	    taste += k;
	}

	    System.out.println(taste - small);

    }
}


Measured memory_bytes: 23252
#include<stdio.h>
int main(void){
	int r, c, c_last, i, j, table[100][100], rsum = 0, csum = 0, total = 0;
	
	scanf("%d %d\n", &r, &c);
	c_last = c-1;
	for(i = 0; i < r; i++){
		for(j = 0; j < c; j++){
			if(j == c_last){
				scanf("%d\n", &table[i][j]);
			}else{
				scanf("%d ", &table[i][j]);
			}
		}
	}
	
	for(i = 0; i < r; i++){
		for(j = 0; j < c; j++){
			rsum += table[i][j];
			printf("%d ", table[i][j]);
			if(j == c_last){
				printf("%d\n", rsum);
			}
		}
		rsum = 0;
	}
	
	for(j = 0; j < c; j++){
		for(i = 0; i < r; i++){
			csum += table[i][j];
		}
		printf("%d ", csum);
		total += csum;
		csum = 0;
		if(j == c_last){
			printf("%d\n", total);
		}
	}
	return 0;
}



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

int main() {
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  if(a+b>c+d) cout<<"Left"<<endl;
  else if(a+b<c+d) cout<<"Right"<<endl;
  else cout<<"Balanced"<<endl;
}

Measured memory_bytes: 256
from sys import exit
import math
import collections
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

s = input()
t = input()
n = len(s)

for i in range(n):
    flag = 0
    for j in range(n):
        if s[(i+j)%n] != t[j]:
            flag = 1
            break
    if flag == 0:
        print('Yes')
        exit()
print('No')

Measured memory_bytes: 9240
# coding=utf-8


def partial_swap(origin, begin, end, begin2):
    for i in range(end-begin):
        origin[begin+i], origin[begin2+i] = origin[begin2+i], origin[begin+i]

    return origin


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    for i in range(Q):
        b, e, t = map(int, input().split())
        A = partial_swap(A, b, e, t)

    print(' '.join(map(str, A)))



Measured memory_bytes: 5644
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int h = sc.nextInt();
		int w = sc.nextInt();
		String[] s = new String[h + 2];
		StringBuilder[] sb = new StringBuilder[h + 2];
		String tmp = ".";

		for (int i = 0; i < h + 2; i++) {
			sb[i] = new StringBuilder();
		}

		for (int i = 0; i < w + 2; i++) {
			sb[0].append(tmp);
			sb[h + 1].append(tmp);
		}

		for (int i = 1; i < h + 1; i++) {
			s[i] = sc.next();
			sb[i].insert(0, "." + s[i] + ".");
		}

		for (int i = 1; i < h + 1; i++) {
			for (int j = 1; j < w + 1; j++) {
				if (sb[i - 1].substring(j, j + 1).equals(".") &&
						sb[i + 1].substring(j, j + 1).equals(".") &&
						sb[i].substring(j - 1, j).equals(".") &&
						sb[i].substring(j + 1, j + 2).equals(".") &&
						sb[i].substring(j, j + 1).equals("#")) {
					System.out.println("No");
					System.exit(0);
				}
			}
		}

		System.out.println("Yes");

		sc.close();
	}
}

Measured memory_bytes: 23764
//↓見なくていいよ！ここから--------------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
var obj;
var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  console.error("\n");
  var start = new Date();
  Main();
  var end = new Date() - start;
  
  myerr("time : " + (end) + "ms");
  myerr("memory : " + Math.round(process.memoryUsage().heapTotal / 1024) + "KB");
});
function makeClone(obj){return JSON.parse(JSON.stringify(obj));}
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  var returnObj = {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(!this.hasNext()){throw "ArrayIndexOutOfBoundsException これ以上ないよ";}else{var returnInput = this.list[this.index];this.index++;return returnInput;}}
  };
  return returnObj;
}
function myout(s){console.log(s);}
function myerr(s){console.error("debug:" + require("util").inspect(s,false,null));}
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す 1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map(Number);case 6:return i.split("");case 7:return i.split("").map(Number);case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}

//↑見なくていいよ！ここまで--------------------------------------------------
function Main(){
	var s = next();
	var output = "abcdefghijklmnopqrstuvwxyz";
	myout(output[output.indexOf(s) + 1]);
}


Measured memory_bytes: 30012
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

SIZE = 32

POW = [None]*SIZE
POW[0] = 1
for i in range(1,SIZE):
    POW[i] = POW[i-1]*2

x = int(input())
BIT = [0]*SIZE

for i in range(0,SIZE):
    if POW[(SIZE-1)-i] <= x:
        BIT[i] = 1
        x -= POW[(SIZE-1)-i]

#ビット列
for i in range(SIZE):
    print("%d"%(BIT[i]),end="")
print()

#反転
for i in range(SIZE):
    print("%d"%(1-BIT[i]),end="")
print()

#左シフト
for i in range(1,SIZE):
    print("%d"%(BIT[i]),end="")
print("0")

#右シフト
print("0",end="")
for i in range(SIZE-1):
    print("%d"%(BIT[i]),end="")
print()


Measured memory_bytes: 6392
#include <iostream>
#include <cmath>

using namespace std;

long long f(long long b, long long n) {
    long long ans = 0;

    while (n) {
        ans += n % b;
        n /= b;
    }

    return ans;
}

int main() {
    long long n, s;

    cin >> n >> s;

    if (n == s) {
        cout << n+1 << endl;
        return 0;
    }

    if (n > s) {
        for (long long i = 2; i <= sqrt(n); i++) {
            if (f(i, n) == s) {
                cout << i << endl;
                return 0;
            }
        }

        for (long long i = sqrt(n); i > 0; i--) {
            long long b = (n-s+i) / i;
            if (b >= 2 && f(b, n) == s) {
                cout << b << endl;
                return 0;
            }
        }
    }

    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    A = list(map(int,input().split()))
    ret = abs(A[0] - A[1]) + abs(A[1] - A[2]) + abs(A[2] - A[0])
    ans = INF
    for i in range(3):
        ans = min(ans,ret - abs(A[i] - A[(i+1)%3]))
    print(ans)

if __name__ == '__main__':
    main()



Measured memory_bytes: 3188
num = input("")
num = num.split(" ")
N = int(num[0])
M = int(num[1])
a = int(N*(N-1)/2) if N*(N-1) >= 0 else 0
b = int(M*(M-1)/2) if M*(M-1) >= 0 else 0
print(a + b)


Measured memory_bytes: 3060
#include <stdio.h>
int main(void)
{
	char Digit[11] = {'\0'};
	scanf("%s",Digit);
	int Difference[8] = {0};
	int i;
	for (i = 0;i < 8;i++)
	{
		if ((Digit[i+2] - 48) < 0)
		{
			break;
		}
		int a = Digit[i] - 48;
		int b = Digit[i+1] - 48;
		int c = Digit[i+2] - 48;
		Difference[i] = (a * 100) + (b * 10) + c - 753;
		if (Difference[i] < 0)
		{
			Difference[i] = -(Difference[i]);
		}
	}
	int Min = Difference[0];
	for (i = 1;i < 8;i++)
	{
		if ((Digit[i+2] - 48) < 0)
		{
			break;
		}
		if (Min > Difference[i])
		{
			Min = Difference[i];
		}
	}
	printf("%d\n",Min);
}

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

int d[5],flag[10];

int main()
{
    cin>>d[0]>>d[1]>>d[2];
    for(int i=0; i<3; i++)
        flag[d[i]]++;
    if(flag[5]==2 && flag[7]==1) puts("YES"); 
    else puts("NO");
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 2000000

void CountingSort(int [], int [], int, int);

int main()
{
  int A[MAX], B[MAX], n, i, k = 0;

  scanf("%d", &n);

  for(i = 1; i < n + 1; i++){
    scanf("%d", &A[i]);
    if(A[i] > k)
      k = A[i];
  }

  CountingSort(A, B, n, k);

  return 0;
}

void CountingSort(int A[], int B[], int n, int k)
{
  int i, j, C[k + 1];

  for(i = 0; i < k + 1; i++)
    C[i] = 0;

  for(j = 1; j < n + 1; j++)
    C[A[j]]++;

  for(i = 1; i < k + 1; i++)
    C[i] = C[i] + C[i - 1];

  for(j = n; j >= 1; j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }

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



Measured memory_bytes: 17392
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let a: isize = iterator.next().unwrap().parse().unwrap();
    let b: isize = iterator.next().unwrap().parse().unwrap();
    let c: isize = iterator.next().unwrap().parse().unwrap();
    let d: isize = iterator.next().unwrap().parse().unwrap();

    let t1 = (c + b - 1) / b;
    let t2 = (a + d - 1) / d;

    return if t1 <= t2 {
        "Yes".to_string()
    } else {
        "No".to_string()
    }
}


Measured memory_bytes: 2116
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 2 - 170;

int main() {
    int n;
    string s;
    cin >> n >> s;
    using P = pair<int, int>;
    vector<P> v(static_cast<u32>(n), P{0, 0});
    for (int i = 0; i < n-1; ++i) {
        if(s[i] == 'W') v[i+1].second++;
    }
    int a = 0;
    for (int i = 0; i < n; ++i) {
        a += v[i].second;
        v[i].second = a;
    }
    for (int i = n-1; i > 0; --i) {
        if(s[i] == 'E') v[i-1].first++;
    }
    a = 0;
    for (int i = n-1; i >= 0; --i) {
        a += v[i].first;
        v[i].first = a;
    }
    int ans = INF<int>;
    for (int i = 0; i < n; ++i) {
        ans = min(ans, v[i].first+v[i].second);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 2948
#include<map>
#include<set>
#include<cmath>
#include<regex>
#include<queue>
#include<stack>
#include<bitset>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>

#pragma warning(disable:4996)
using namespace std;

string s;

int main() {
	cin >> s;
	for (int i = 0; i < s.size(); ++i) {
		s[i] = s[i] == ',' ? ' ' : s[i];
	}
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int h[100010];
int ans;
vector<int> adj[100010];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
   for (int i = 1; i <= m; i++) 
   {
       int a, b;
       cin >> a >> b;
       adj[a].push_back(b);
       adj[b].push_back(a);
   }
   for (int i = 1; i <= n; i++)
   {
       int f = 0;
       if (adj[i].empty()) 
       {
           ans++;
           continue;
       }
       for (int j = 0; j < adj[i].size(); j++)
       {
           if (h[adj[i][j]]>=h[i])
           {
               f = 1;
               break;
           }
       }
       if (f == 1) continue;
       ans++;
   }
   cout << ans;
   return 0;
}

Measured memory_bytes: 9100
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vec=vector<ll>;
using mat=vector<vec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define bFor(i,a,b) for(i=a;i>=b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
#define endl "\n"
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}while(0)
using datas=pair<ll,ll>;
using tdata=pair<ll,datas>;

int main(){
  ll i,j,k,N,ans=0;
  cin>>N;
  mat v(N,vec(N)),ch(N,vec(N,1));
  rep(i,N){
    rep(j,N){
      cin>>v[i][j];
    }
    if(v[i][i]){
      cout<<-1<<endl;
      return 0;
    }
  }
  rep(k,N){
    rep(i,N){
      rep(j,N){
        if(i==k||k==j)continue;
        if(v[i][j]>v[i][k]+v[k][j]){
          cout<<-1<<endl;
          return 0;
        }else if(v[i][j]==v[i][k]+v[k][j]){
          ch[i][j]=0;
        }
      }
    }
  }
  rep(i,N){
    For(j,i+1,N){
      if(ch[i][j])ans+=v[i][j];
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1664
#include <stdio.h>

void trace(int A[],int N){
  int i;
  for (i=0;i<N;i++){
    if(i>0)printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
}



void insertionSort(int A[],int N){
  int i,j,v;
  for (i=0;i<N;i++){
    v=A[i];
    j=i-1;
    while(j>=0 && A[j] > v ){
      A[j+1] = A[j];
      j--;
    }
    A[j+1]=v;
    trace(A,N);
  }
}

int main(){
  int i,j,N;
  int A[100];

  scanf("%d",&N);
  for(i=0;i<N;i++)scanf("%d",&A[i]);

  
  insertionSort(A,N);
  

  return 0;
}

    
    



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

using namespace std;

int arr[100005];

int n, t, ans;

void solve() {
    scanf("%d %d", &n, &t);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
    }

    int mn = 1e9;
    int x = 0;

    for (int i = 1; i <= n; ++i) {
        x = max(x, arr[i] - mn);
        mn = min(mn, arr[i]);
    }

    mn = 1e9;

    for (int i = 1; i <= n; ++i) {
        if (arr[i] - mn == x) {
            ++ans;
        }

        mn = min(mn, arr[i]);
    }

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

int main() {
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 640
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# N個の最大公約数
def eucledean(A, N):
    # A = sorted(A)
    ans = A[0]
    for i in range(1, N):
        ans = gcd(A[i], ans)
    return ans


def lcm(a, b):
    return a*b // gcd(a, b)


# N個最小公倍数
def lcm_n(A, N):
    # A = sorted(A)
    ans = A[0]
    # for i in range(1, N):
    #     ans = fractions.gcd(A[i], ans)
    for i in range(1, N):
        ans = lcm(ans, A[i])
    return ans


def modinv(a):
    return pow(a, MOD-2, MOD)


def main():
    N = I()
    A = LI()
    ans = 0

    a = lcm_n(A, N)
    a %= MOD
    for i in range(N):
        ans += a * modinv(A[i])
        ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()


Measured memory_bytes: 69588
function main() {
  process.stdin.resume();
  process.stdin.setEncoding("utf8");
  var chunks = "";

  process.stdin.on("data", function (chunk) {
    chunks += chunk;
  });

  process.stdin.on("end", function () {
    var inputs = chunks.trim().split("\n");
    var words = inputs.slice(1);

    words.sort((a, b) => cmp(a, b));
    console.log(words.join(""));
  });

  function cmp(a, b) {
    for (var i = 0; i < a.length; i++) {
      if (a[i] < b[i]) {
        return -1;
      } else if (a[i] > b[i]) {
        return 1;
      }
    }

    return 0;
  }
}

main();


Measured memory_bytes: 7628
# AGC024C

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


def main():
    n = int(input())
    a = [None] * n
    for i in range(n):
        a[i] = int(input())

    prev = a[-1]
    if a[0]!=0:
        print(-1)
        return
    count = 0
    for num in a[::-1]:
        if prev==num+1:
            pass
        elif prev >= num+2:
            print(-1)
            return
        else:
            count += num
        prev = num
    print(count)
main()

Measured memory_bytes: 46812
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    //*
    int a;
    cin >> a ;
    //*/

    /*
    vector<int> vec(3);
    cin >> vec.at(0) >> vec.at(1) >> vec.at(2) ;
    
    sort(vec.begin(), vec.end());
    //*/
    
    //*
    if( a == 3 || a == 5 || a == 7 ){
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    //*/
    
    //cout << a + b / 2 << endl;

    return 0; 
}


Measured memory_bytes: 3616
import static java.util.Comparator.comparing;

import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        Solver solver = new Solver(System.in, out);
        solver.solve();
        out.close();
    }
}
class Solver {
	Scanner sc;
	PrintWriter out;
    public Solver(InputStream in, PrintWriter out) {
    	sc = new Scanner(in);
    	this.out = out;
    }
    // ==========================================================
    public void solve() {
    	int N = ni();
    	int[][] X = new int[N][];
    	for (int i = 0; i < N; i++) {
			X[i] = ndi(3);
		}
    	int[][] dp = new int[N+10][3];
    	int wk;
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < 3; j++) {
    			if(j == 0)		wk = Math.max(dp[i][1], dp[i][2]);
    			else if(j == 1) wk = Math.max(dp[i][0], dp[i][2]);
    			else			wk = Math.max(dp[i][0], dp[i][1]);
    			dp[i+1][j] = Math.max(dp[i+1][j], wk + X[i][j]);
			}
		}
    	out.println(Math.max(dp[N][0], Math.max(dp[N][1], dp[N][2])));
    }
    // ------------------------------------------
    // 入力
    // ------------------------------------------
    public int ni() {
    	return sc.nextInt();
    }
    public long nl() {
    	return sc.nextLong();
    }
    public String ns() {
    	return sc.next();
    }
    public char[] nc() {
    	return sc.next().toCharArray();
    }
    public int[] ndi(int N) {
    	int[] ans = new int[N];
    	for (int i = 0; i < N; i++) {
			ans[i] = ni();
		}
    	return ans;
    }
    public long[] ndl(int N) {
    	long[] ans = new long[N];
    	for (int i = 0; i < N; i++) {
			ans[i] = nl();
		}
    	return ans;
    }
    public String[] nds(int N) {
    	String[] ans = new String[N];
    	for (int i = 0; i < N; i++) {
			ans[i] = ns();
		}
    	return ans;
    }
    public char[][] ndc(int N) {
    	char[][] ans = new char[N][];
    	for (int i = 0; i < N; i++) {
			ans[i] = nc();
		}
    	return ans;
    }
    public int[][] nddi(int N, int S) {
    	int[][] ans = new int[N][S];
    	for (int i = 0; i < N; i++) {
			for (int j = 0; j < S; j++) {
				ans[i][j] = ni();
			}
		}
    	return ans;
    }
}


Measured memory_bytes: 96452
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; 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--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

    ll n, l;
    cin >> n >> l;

    ll alls = 0;
    REP(i, n){
        alls += l + i;
    }
    ll res;
    if(l >= 0){
        cout << alls - l << endl;
        return 0;
    }
    if(l <= - n + 1){
        cout << alls - (l + n - 1) << endl;
        return 0;
    }
    cout << alls << endl;
    return 0;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
h=list(map(int,input().split()))
#dp[i]はiに来たときのコストの総和の最小値

dp=[float('inf')]*n
dp[0]=0

for i in range(1,n):
  for j in range(min(k,i)):
    dp[i]=min(dp[i],dp[i-j-1]+abs(h[i]-h[i-j-1]))

print(dp[n-1])

Measured memory_bytes: 85548
import java.util.*;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    char[] c = s.toCharArray();
    boolean t = true;
    for(int i=0;i<s.length();i++){
      if (i%2 == 0 && c[i] == 'L'){
        t = false;
        break;
      } else if (i%2 == 1 && c[i] == 'R'){
        t = false;
        break;
      }
    }
    if(t == true){
      System.out.println("Yes");
    } else if (t == false){
      System.out.println("No");
    }
  }
}

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

int main() {
  int64_t n, a, b;
  cin >> n >> a >> b;
  
  int64_t ans = a * (n / (a + b));
  if (n % (a + b) < a) {
    ans += n % (a + b);
  }
  else {
    ans += a;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256