akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,k,a[N],dp[N];
inline int read(){
	int x=0,w=1;
	char ch=0;
	while (ch<'0' || ch>'9'){
		ch=getchar();
		if (ch=='-') w=-1;	
	}
	while (ch<='9' && ch>='0'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*w;
}
int main(){
	n=read(),k=2;
	for (int i=1;i<=n;++i) a[i]=read();
	dp[1]=0;
	for (int i=2;i<=n;++i){
		dp[i]=2e9;
		for (int j=max(1,i-k);j<i;++j)
			dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
	}
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
    public static void main(String[] arg){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i=0 ;i < a.length; i++){
            a[i] = sc.nextInt();
        }
        for(int j = a.length - 1; j>=0 ; j--){
            System.out.print(a[j]);
            if(j == 0) break;
            System.out.print(" ");
        }
        System.out.println();
        sc.close();
    }
}


Measured memory_bytes: 26368
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=2e5+10;
char str[maxn],tar[maxn];
vector <int> pos[30];
int Pos[30],a[maxn],bit[maxn];
struct node{
	int l,r;
	char ch;
};
struct node Pair[maxn];
bool cmp(const node &lhs,const node &rhs){
	return lhs.l<rhs.l; 
}
inline int read(){
	int x=0,flag=1;
	char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')flag=-1,ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*flag;
}
inline int lowbit(int x){
	return x&(-x);
}
inline void Update(int posit){
	while(posit<=maxn-5){
		bit[posit]++;
		posit+=lowbit(posit);
	}
}
inline int Query(int posit){
	int ans=0;
	while(posit){
		ans+=bit[posit];
		posit-=lowbit(posit);
	}
	return ans;
}
int main(){
	int i,j,k,m,n;
	int mid=0;
	scanf("%s",str+1);
	n=strlen(str+1);
	for(i=1;i<=n;i++)pos[str[i]-'a'+1].push_back(i);
	int cnt=0;
	for(i=1;i<=26;i++){
		int size=pos[i].size();
		if(pos[i].size()%2==1 && mid){
			puts("-1");
			return 0;
		}
		else if(pos[i].size()%2==1)mid=i;
		for(j=0;j<size/2;j++){
			Pair[++cnt].l=pos[i][j];
			Pair[cnt].r=pos[i][size-j-1];
			Pair[cnt].ch=i+'a'-1;
		}
	}
	sort(Pair+1,Pair+cnt+1,cmp);
	for(i=1;i<=cnt;i++)tar[i]=tar[n-i+1]=Pair[i].ch;
	if(mid)tar[(n+1)/2]='a'+mid-1;
	for(i=1;i<=n;i++)
		a[i]=pos[tar[i]-'a'+1][Pos[tar[i]-'a'+1]++];
	ll ans=0;
	for(i=1;i<=n;i++){
		ans+=1ll*Query(a[i]);
		Update(a[i]);
	}
	printf("%lld\n",1ll*(n-1)*n/2-ans);
	return 0;
}

Measured memory_bytes: 4728
#include<bits/stdc++.h>
 using namespace std;
 #define ll long long int
 int main()
 {    
        long long int  n,x,a,c;
         cin>>n>>x>>a;
          if(n%x==0)
              c=n/x;
           else
            c=n/x+1;
         cout<<c*a;
   }


Measured memory_bytes: 3592
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define first_more_idx(ve, num) upper_bound(all(ve), num)-ve.begin() // idx = first_more_idx(ve,num); if(idx = ve.size()) , then not exist
#define first_lessequal_idx(ve, num) lower_bound(all(ve), num)-ve.begin()
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > // only sort first param
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll power(ll x, ll n){if(n == 0) return 1;return  (n%2)? x*power(x, n-1)%MOD : power(x*x%MOD, n/2);}

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

    ll N, K;
    cin >> N >> K ;

    if( K > (((N-2) * (N-1) )/2 )) {
        cout << "-1" << endl;
        return 0;
    }else{
        ll mx = (N-2)*(N-1)/2;

        vector<pair<ll,ll> > ans ;
        vector<pair<ll,ll> > els;
        rep(i, N){
            if(i == 0) continue;
            ans.pb(mp(1, (i+1)));
        }
        rep(i, N) rep(j, N){
            if(i == 0 || j == 0) continue;
            if(j <= i) continue;
            els.pb(mp((i+1), (j+1)));
        }

        rep(i, mx-K){
            ans.pb(els[i]);
        }

        cout << ans.size() << endl;
        rep(i, ans.size()){
            cout << ans[i].first << " " << ans[i].second << endl;
        }
    }



    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define INF 10000000000

int main() {
	long long n, ans = 1;
	cin >> n;
	vector<long long> a(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (!a[i]) ans = 0;
	}
	for (int i = 0; i < n; i++) {
		if (!ans) break;
		if (1000000000000000000 / ans < a[i]) {
			ans = -1;
			break;
		}
		ans *= a[i];
	}

	cout << ans;
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  int x;
  
  x = N % 100;
  x %= 10;
  
  if(x == 3){
    cout << "bon" << endl;
  }else if (x == 0 || x == 1 || x == 6 || x == 8){
    cout << "pon" << endl;
  }else{
    cout << "hon" << endl;
  }
  
  return 0;
}
  
  

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

int main() {
  string s;
  cin >> s;
  int count = 0;
  int nokori = 15 - s.size();
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'o') count++;
  }
  cout << (count + nokori >= 8 ? "YES" : "NO") << endl;
  return 0;
}

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

int main() {
  long N, K, i, j;
  bool flag = true;
  cin >> N >> K;
  i = 1;
  j = K;
  while (flag) {
    if (N >= j) {
      i++;
      j *= K;
    } else {
      break;
    }
  }
  cout << i << endl;
}

Measured memory_bytes: 256
s = input()

n = len(s)
ans = 'No'

if s == s[::-1]:
  s_2 = s[:int((n - 1) / 2)]
  if s_2 == s_2[::-1]:
    s_3 = s[int((n + 3) / 2 - 1):]
    if s_3 == s_3[::-1]:
      ans = 'Yes'

print(ans)

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

using namespace std;

int N;
int dist_c[101];

int main() {
  cin >> N;
  int m = 0;
  for(int i = 0; i < N; i++) {
    int a;
    cin >> a;
    m = max(m,a);
    dist_c[a]++;
  }

  int Min = 100;
  for(int i = 0; i <= m; i++) {
    int d = max(i,m-i);
    Min = min(Min,d);
    if(--dist_c[d] < 0) {
      cout <<"Impossible"<<endl; return 0;
    }
  }

  for(int i = 0; i <= Min; i++) {
    if(dist_c[i] > 0){
      cout <<"Impossible"<<endl; return 0;
    }
  }

  cout <<"Possible"<<endl;
}
    


Measured memory_bytes: 256
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    T =     _in[1]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    TF = 'Yes' if S==T[:-1] else 'No'
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)


Measured memory_bytes: 61636
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>

using namespace std;

#define ll long long

void dfs(vector<vector<int>> &tree, int q, vector<ll> &ans, ll c, vector<int> &flag){
    ans[q] += c;
    flag[q] = 1;

    for(int i = 0;i < tree[q].size();++i){
        if(flag[tree[q][i]] == 0){
            dfs(tree, tree[q][i], ans, ans[q], flag);
        }
    }

    return;
}

int main(void){
    int n, q;
    cin >> n >> q;
    vector<vector<int>> tree(n, vector<int>());
    for(int i = 0;i < n-1;++i){
        int a, b;
        cin >> a >> b;
        tree[a-1].push_back(b-1);
        tree[b-1].push_back(a-1);
    }

    vector<ll> ans(n, 0);
    for(int i = 0;i < q;++i){
        int q, x;
        cin >> q >> x;
        ans[q-1] += (ll)x;
    }

    vector<int> flag(n, 0);

    dfs(tree, 0, ans, 0, flag);

    for(int i = 0;i < ans.size();++i){
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 28160
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
    int N, H, W;
    cin >> N >> H >> W;

    cout << (N - H + 1) * (N - W + 1) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <math.h>
#include <unordered_map>
#include <algorithm>

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline int lcm(int a,int b){return a*b/gcd(a,b);}
typedef long long ll;
typedef std::vector<int> VI;
typedef std::pair<int, int> PII;

using namespace std;

const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x+=a.x)>=mod) x-=mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x+=mod-a.x)>=mod) x-= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};

mint c[4005][4005];

void init() {
  c[0][0] = 1;
  for (int i=0; i<=4000;i++) {
    for (int j=0;j<=i;j++) {
      c[i+1][j] += c[i][j];
      c[i+1][j+1] += c[i][j];
    }
  }
}

mint comb(int n, int k)
{
  return c[n][k];
}

mint f2(int n, int k)
{
  return comb(n+k-1, k-1);
}

mint f(int n, int k)
{
  if (n < k) return 0;
  if (n==0&&k==0) return 1;
  if (k < 1) return 0;
  return f2(n-k, k);
}

int main()
{
  init();
  int n, k;
  cin >> n >> k;
  for (int i=1;i<=k;i++) {
    mint blue = f(k,i);
    mint red = 0;
    {
      red += f(n-k, i-1);
      red += f(n-k, i);
      red += f(n-k, i);
      red += f(n-k, i+1);
    }
    mint ans = blue*red;
    printf("%lld\n", ans.x);
  }
  return 0;
}


Measured memory_bytes: 125568
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=101000;
int n,x[N],l,q,p[N][22],u,v;
int main() {
	scanf("%d",&n);
	rep(i,0,n) scanf("%d",x+i);
	scanf("%d",&l);
	rep(i,0,n) p[i][0]=upper_bound(x,x+n,x[i]+l)-x-1;
	rep(j,1,20) rep(i,0,n) p[i][j]=p[p[i][j-1]][j-1];
	scanf("%d",&q);
	rep(i,0,q) {
		scanf("%d%d",&u,&v);
		--u; --v; if (u>v) swap(u,v);
		int r=0;
		per(j,0,20) if (p[u][j]<v) {
			u=p[u][j],r+=(1<<j);
		}
		printf("%d\n",r+1);
	}
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int K;

int F(ll v) {
	int ret=0;
	while(v) {
		ret+=v%10;
		v/=10;
	}
	return ret;
}

ll nex(ll v) {
	vector<pair<ll,ll>> V;
	ll p=1;
	while(p<=v) {
		ll n=p*(v/p+1)-1;
		V.push_back({n,F(n)});
		p*=10;
	}
	sort(ALL(V));
	int x,y;
	FOR(x,V.size()) {
		
		for(y=x+1;y<V.size();y++) {
			if(V[x].first*V[y].second>V[y].first*V[x].second) break;
		}
		if(y==V.size()) return V[x].first;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	vector<ll> V;
	V.push_back(1);
	while(V.size()<K) V.push_back(nex(V.back()+1));
	
	FORR(c,V) cout<<c<<endl;
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
n = int(input())
b = list(map(int,input().split()))
okcounter = 0
ngcounter = 0
for i in range(n):
  if b[i] % 2  == 0:
    if b[i] % 3 == 0 or b[i] % 5 == 0:
      okcounter += 1
    else:
      ngcounter += 1
      break
if ngcounter > 0:
  print("DENIED")
else:
  print("APPROVED")

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


def main():
    n = int(input())
    s = list(input())

    # 1番目と2番目を決め打ち
    # SS，SW，WW，WS
    # 1文字目とn + 1文字目が一致するかどうか
    for pair in ['SS', 'SW', 'WW', 'WS']:
        ans = ['' for _ in range(n + 1)]

        for index, p in enumerate(pair):
            ans[index] = p

            for j in range(1, n):
                if s[j] == 'o':
                    if ans[j] == 'S':
                        ans[j + 1] = ans[j - 1]
                    else:
                        if ans[j - 1] == 'S':
                            ans[j + 1] = 'W'
                        else:
                            ans[j + 1] = 'S'
                else:
                    if ans[j] == 'S':
                        if ans[j - 1] == 'S':
                            ans[j + 1] = 'W'
                        else:
                            ans[j + 1] = 'S'
                    else:
                        ans[j + 1] = ans[j - 1]

        if ans[0] == ans[-1]:
            if ans[n - 1] == ans[1] and ((s[0] == 'o' and ans[0] == 'S') or (s[0] == 'x' and ans[0] == 'W')):
                print(''.join(ans[:-1]))
                break
            elif ans[n - 1] != ans[1] and ((s[0] == 'o' and ans[0] == 'W') or (s[0] == 'x' and ans[0] == 'S')):
                print(''.join(ans[:-1]))
                break
    else:
        print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 5680
#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++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int n,m;
vector<int> c(20,0),x(20010,0),v;
int dp[20010][260];
int main(){
    while(1){
        cin>>n>>m;
        if(n==0 && m==0) break;
        v.clear();
        for(int i=0;i<m;i++) cin>>c[i];
        for(int i=0;i<n;i++) cin>>x[i];
        for(int i=0;i<20010;i++){
            for(int j=0;j<260;j++){
                dp[i][j]=inf;
            }
        }
        dp[0][128]=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<256;j++){
                for(int k=0;k<m;k++){
                    if(j+c[k]>255){
                        int next=255;
                        dp[i+1][next]=min(dp[i+1][next],dp[i][j]+(next-x[i])*(next-x[i]));
                    }
                    else if(j+c[k]<0){
                        int next=0;
                        dp[i+1][next]=min(dp[i+1][next],dp[i][j]+(next-x[i])*(next-x[i]));
                    }
                    else{
                        int next=j+c[k];
                        dp[i+1][next]=min(dp[i+1][next],dp[i][j]+(next-x[i])*(next-x[i]));
                    }
                }
            }
        }
        int min=inf;
        for(int j=0;j<256;j++){
            if(dp[n][j]<min) min=dp[n][j];
        }
        cout<<min<<endl;
    }
    return 0;
}


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

int main()
{
    bool primes[50000]={false};
    primes[0] = true;
    for(int i=2;i <= 25000;++i) {
        if (primes[i-1]) continue;
        for(int j=i+i;j <= 50000;j+=i) {
            primes[j-1] = true;
        }
    }

    int n;
    while (cin >> n && n) {
        int cnt = 0;
        for(int i=2; i <= n/2;++i) {
            if (!primes[i-1] && !primes[n-i-1]) {
                ++cnt;
            }
        }
        printf("%d\n", cnt);
    }

    return 0;
}

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

struct Unionfind {
	vector<int> data;

	Unionfind(int n) { data.assign(n, -1); }

	int root(int n) {
		if (data[n] < 0) return (n);
		return (data[n] = root(data[n]));
	}

	int size(int n) { return (-data[root(n)]); };
	bool same(int x, int y) { return (root(x) == root(y)); }

	void unite(int x, int y) {
		x = root(x), y = root(y);
		if (x == y) return;
		if (data[x] > data[y]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
	}
};

int main() {
    int N, M; cin >> N >> M;
    Unionfind uni(N);
    for (int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        uni.unite(a, b);
    }
    int Q; cin >> Q;
    while (Q--) {
        int a, b; cin >> a >> b;
        cout << (uni.same(a, b) ? "yes" : "no") << '\n';
    }
    return (0);
}


Measured memory_bytes: 3108
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

  int N, M;
  while(cin>>N>>M,N){
	VI C(M); REP(i,M)cin>>C[i];
	int t = 0;
	vector< vector<LL> > calc(2, vector<LL>(256, 1234567890));
	calc[t][128] = 0;
	REP(i,N){
	  int x; cin >> x;
	  fill(ALL(calc[1-t]), 1234567890);
	  REP(j,M){
		REP(b,256){
		  int d = max(0, min(255, b+C[j]));
		  calc[1-t][d] = min(calc[1-t][d], calc[t][b] + (x-d)*(x-d));
		}
	  }
	  t = 1-t;
	}
	LL ans = 1234567890;
	REP(i,256)
	  ans = min(ans, calc[t][i]);
	cout << ans << endl;
  }

  return 0;
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-6;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

int main(void){
	int32 N;
	vector<double> a;
	cin >> N;
	a.resize(N);
	REP(i, N) cin >> a[i];
	sort(all(a));
	double res = a[0];
	REP(i, N-1){
		if(abs(a[N-1]/2-a[i]) < abs(a[N-1]/2-res))
			res = a[i];
	}
	cout << (int32)a[N-1] << " " << (int32)res << endl;
}


Measured memory_bytes: 1024
#include"bits/stdc++.h"
using namespace std;
int main(){
	string a;
	cin>>a;
	int ans=0;
	for(int i=0;i<(a.size()+1)/2;i++){
		if(a[i]!=a[a.size()-1-i])ans++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(v) std::begin(v), std::end(v)
#define ALLR(v) std::rbegin(v), std::rend(v)
using ll = std::int64_t;
using ull = std::uint64_t;
using pll = std::pair<ll, ll>;
using tll = std::tuple<ll, ll, ll>;
template <typename T> using vec = std::vector<T>;
template <typename T> using vvec = vec<vec<T>>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
#define mv_rec make_v(init, tail...)
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return vec<decltype(mv_rec)>(s, mv_rec); }
#undef mv_rec

ll mod;

ll mod_pow(ll n, ll k) {
    ll ret = 1, cur = n;
    while (k) {
        if (k & 1) ret = ret * cur % mod;
        cur = cur * cur % mod;
        k /= 2;
    }
    return ret;
}

ll mod_inv(ll n) { 
    return mod_pow(n, mod - 2); 
}

ll naive(const std::string &s) {
    ll dp1[10] = {}, dp2[10] = {};
    ll ret = 0;
    for (char c : s) {
        ll n = c - '0';
        std::fill(ALL(dp2), 0);
        dp2[n % mod]++;
        for (ll i = 0; i < 10; i++) {
            ll nxt = (i * 10 + n) % mod;
            dp2[nxt] += dp1[i];
        }
        std::copy(ALL(dp2), dp1);
        ret += dp1[0];
    }
    return ret;
}

ll solve() {
    ll n;
    std::string s;
    std::cin >> n >> mod >> s;

    if (mod < 10) return naive(s);

    vec<ll> cnts(mod + 10, 0);
    cnts[0] = 1;
    ll inv = mod_inv(10);
    ll sum = 0;
    ll ret = 0;
    ll inv_mul = 1;

    for (char c : s) {
        ll num = c - '0';
        sum = (sum + num * inv_mul) % mod;
        (inv_mul *= inv) %= mod;
        ll want = (mod - sum) % mod;
        ret += cnts[want];
        cnts[want]++;
    }
    return ret;
}

int main() {
    std::cout << solve() << '\n';
    return 0;
}


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

int main()
{
	int i,values[3];
	cin >> i;
	for(int j=0 ;j<i;j++)
	{
		cin >> values[0] >> values[1] >> values[2];
		sort(values,values+3);
		if(values[0]*values[0] + values[1]*values[1] == values[2]*values[2])
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1168
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))
ans=0
ans=sum(B)
for i in range(N-1):
    if A[i]+1==A[i+1]:
        ans+=C[A[i]-1]
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
vector<int> dp  (5001,(1<<21));
vector<int> able(5001,false);

void init(){
	int item[6] = {200,300,500,1000,1200,1500};
	int price[6]= {380,550,850,1520,1870,2244};
	
	able[0]=true;
	dp[0]  =0;

	for(int k=0;k<6;k++){	
		for(int i=0;i+item[k]<=5000;i++){
			dp[i+item[k]] = min( dp[i+item[k]] , dp[i]+price[k] );
		}
	}
}

int main(){
	init();
	int n;
	int mi;
	while(cin >> n && n){
		/*mi = 1<<21;
		for(int i=n;i<=5000;i++){
			mi = min(dp[i],mi);
		}*/	
		cout << dp[n] << endl;
	}
}	

Measured memory_bytes: 0
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//List<String> list= new ArrayList<String>(Arrays.asList(s.split("")));
		//List<Integer> list_gold=new ArrayList<Integer>();
		//Integer[] Republican = new Integer[m];
		String s = sc.next();
		List<String> list= new ArrayList<String>(Arrays.asList(s.split("")));
		String mae=list.get(0)+list.get(1);
		String ato=list.get(2)+list.get(3);
		if(Integer.parseInt(mae)>0&&Integer.parseInt(mae)<13) {
			if(Integer.parseInt(ato)>0&&Integer.parseInt(ato)<13) {
				System.out.println("AMBIGUOUS");
			}
			else {
				System.out.println("MMYY");
			}
		}
		else {
			if(Integer.parseInt(ato)>0&&Integer.parseInt(ato)<13) {
				System.out.println("YYMM");
			}
			else {
				System.out.println("NA");
			}
		}
	}

}



Measured memory_bytes: 21844
#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

yes = "Yes"
no = "No"

def main():
    x = ii()
    ans = 0
    ans+=(x//500)*1000
    x%=500
    ans+=(x//5)*5
    print(ans)



main()





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

constexpr int MOD = 1e9 + 7;

signed main() {
  int N, M;
  cin >> N >> M;
  map<int, int> mp;
  for (int i = 0; i < M; i++) {
    int a;
    cin >> a;
    mp[a] = 1;
  }

  static int dp[101010];
  dp[0] = 1;

  for (int i = 0; i < N; i++) {
    if (mp[i]) {
      dp[i] = 0;
    }
    dp[i + 1] = (dp[i + 1] + dp[i]) % MOD;
    dp[i + 2] += (dp[i + 2] + dp[i]) % MOD;
  }

  cout << dp[N] << endl;
  return 0;
}

Measured memory_bytes: 7296
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	string str;
	int t,q,f,sum=0;
	char c;
	cin>>str;
	cin>>q;
	while(q--)
	{
		scanf("%d",&t);
		if(t==1)sum++;
		else
		{
			scanf("%d %c",&f,&c);
			if(sum%2==0)
			{
				if(f==1)str.insert(str.begin(),c);
                else str.insert(str.end(),c);
			}
			else
			{
				if(f==2) str.insert(str.begin(),c);
                else str.insert(str.end(),c);
			}
		}
	}
	if(sum%2==1)reverse(str.begin(),str.end());
	cout<<str<<endl;
	return 0;
}

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

/* {{{ */
#define CL(N) cout << N << endl
#define DCT(N) cout << "debug " << N << endl
#define REP(i, N) for (int i = 0; i < N; i++)
/* }}} */

int main()
{
	int n, l;

    while (cin >> n >> l, n || l){
        int a[100000];
        REP(i, n){
            cin >> a[i];
        }

        int sum = 0;
        REP(i, n - l + 1){
            int si = 0;
            REP(j, l){
                si += a[i + j];
            }

            sum = max(sum, si);
        }

        CL(sum);
    }

	return (0);
}

Measured memory_bytes: 3400
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

typedef complex<double> P;

void solve() {
    int N;
    cin >> N;
    vi X(N), Y(N);
    vector<P> ps(N);
    rep(i, N) {
        cin >> X[i] >> Y[i];
        ps[i] = P(X[i], Y[i]);
    }

    sort(all(ps), [&](P p, P q) {
        return atan2(imag(p), real(p)) < atan2(imag(q), real(q));
    });
    
    double ans = 0;
    rep(i, N) {
        double x = 0, y = 0;
        rep(j, N) {
            x += real(ps[(i + j) % N]);
            y += imag(ps[(i + j) % N]);
            smax(ans, sqrt(x*x + y * y));
        }
    }
    cout << ans << endl;
}

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

Measured memory_bytes: 256
N = int(input())
S = input()
order = list(S)
#print(order)
num = len(order)
T = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
aorder = list(T)
aorder[26:26] = aorder
#print(aorder)
ans = ''
for n in range(num):
    num2 = aorder.index(order[n])
    num3 = num2+N
    aordernum3 = aorder[num3]
    #print(aordernum3)
    ans += aordernum3  
print(ans)


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        if(n == k) {
            System.out.println(1);
            return;
        } else if(k == 2) {
            System.out.println(n - 1);
        } else if(k == 3) {
            System.out.println(n / 2);
        } else {
            int ans = n / (k - 1);
            if(n % (k - 1) != 0) ans++;
            System.out.println(ans);
        }
    }
}

Measured memory_bytes: 58056
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
s  = input()
t  = input()
#  = int(input())
#  = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()
print('Yes' if s == t[:-1] else 'No')


Measured memory_bytes: 9396
#include<cstdio>
#define abs(x) ((x>0)?x:(-(x)))
int H,W,D,A;
int Q,L,R;
int px[90001] ,py [90001];
int d[90001];
int  main()
{
	scanf ("%d %d %d",&H,&W,&D);
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			scanf ("%d",&A);
			px[A]=i,py[A]=j;
		}
	}
	for(int i=D+1;i<=H*W;i++){ 
		d[i]=d[i-D]+abs(px[i]-px[i-D])+ abs(py[i]-py[i-D]);
	} 
	scanf ("%d",&Q);
	while(Q--){ 
		scanf ("%d%d",&L,&R);
		printf ("%d\n",d[R]-d[L]);
	} 
} 



Measured memory_bytes: 2048
N,M,K=map(int,input().split())

for i in range(N+1):
    for j in range(M+1):
        if i==0 or j==0:
            x=N*j+M*i
            if x==K:
                print("Yes")
                exit()
        x=N*j+M*i-(i*j)-i*j
        #print(str(i)+" "+str(j))
        #print(x)
        if x==K:
            print("Yes")
            exit()
print("No")

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

vector<long> ve;

void comb(vector<vector<long>> &v){
    for(int i=0; i<v.size(); ++i){
        v[i][0]=1;
        v[i][i]=1;
    }
    for(int i=1; i<v.size(); ++i){
        for(int j=1; j<i; ++j){
            v[i][j]=v[i-1][j-1]+v[i-1][j];
        }
    }
}

int main() {
	int N, A, B; cin >> N >> A >> B;
	vector<vector<long>> eul(N+1, vector<long>(N+2, 0));
	comb(eul);
	for(int i=0; i<N; ++i){
	    long v;
	    cin >> v;
	    ve.push_back(v);
	}
	sort(ve.begin(), ve.end(), greater<long>());
	long sum=0;
	for(int i=0; i<A; ++i) sum += ve[i];
	cout << setprecision(18) << (double) sum/A << endl;
	int fr, ba;
	for(fr=0; fr<A; ++fr){
	    if(ve[A-fr-1]!=ve[A-1]) break;
	}
	for(ba=0; ba<N-A; ++ba){
	    if(ve[A+ba]!=ve[A-1]) break;
	}
	long ans=0;
	if(fr<A) ans=eul[fr+ba][fr];
	else{
	    for(int i=A; i<=min(A+ba, B); ++i){
	        ans += eul[A+ba][i];
	    }
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	int sum = 0;
	for(int i = 0; i < n; i += 2){
		sum ^= (a[i] ^ a[i + 1]);
	}
	for(int i = 0; i < n; i++) cout << (a[i] ^ sum) << ' ';
	return 0;
}


Measured memory_bytes: 3972
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//--------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n;cin>>n;
    vector<int>t(n);
    for(int i=0;i<n;i++)cin>>t[i];
    int sum=0;for(int i=0;i<n;i++)sum+=t[i];
    int m;cin>>m;
    while(m--){
        int p,x;cin>>p>>x;
        p--;
        cout<<sum-(t[p]-x)<<endl;
    }
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------




Measured memory_bytes: 256
def merge(A, left, mid, right):
    count =0
    L = A[left:mid]
    R = A[mid:right]
    L.append(float('inf'))
    R.append(float('inf'))
    i = 0
    j = 0
    for k in range(left, right):
        count +=1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return count

def MergeSort(A, left, right):
    if left +1 < right:
        mid = (left + right)//2
        countR = MergeSort(A, left, mid)
        countL = MergeSort(A, mid, right)
        return merge(A, left, mid, right) + countL + countR
    return 0

N = int(input())
A = list(map(int, input().split()))
count = MergeSort(A, 0, N)
print(" ".join(list(map(str, A))))
print(count)


Measured memory_bytes: 66592
def match(a, b):
    for i, j in zip(a, b):
        if i != '?' and i != j:
            return False
    return True

def solve(r, t):
    l = len(t)
    m = len(r)
    for i in range(m - l, -1, -1):
        if match(r[i:i+l], t):
            ans = ''
            for j in range(i):
                if r[j] == '?':
                    ans = ans + 'a'
                else:
                    ans = ans + r[j]
            for j in range(l):
                ans = ans + t[j]
            for j in range(i + l, m):
                if r[j] == '?':
                    ans = ans + 'a'
                else:
                    ans = ans + r[j]
            return ans
    return 'UNRESTORABLE'

R = input()
T = input()
print(solve(R, T))

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

int main() {
  int a, b, k; cin >> a >> b >> k;
  int x = 0, ans=1;
   for(int i=min(a,b); i>0; i--) {
    if(a%i==0 && b%i==0) {
     x++;
     if(x==k) ans = i;
    }
  }
  
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
abcd = gets.split("").map(&:to_i)

(1 << 3).times do |bit|
  ans = []

  sum = abcd[0]
  ans << abcd[0]

  3.times do |i|
    sum += (-1) ** bit[i] * abcd[i + 1]
    ans << (bit[i] == 0 ? "+" : "-") << abcd[i + 1]
  end

  if sum == 7
    puts [*ans, "=7"].join
    break
  end
end


Measured memory_bytes: 1916
import java.util.*;
import java.text.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = a - (b*2);
		if(c <= 0){
			System.out.println("0");
		}
		else{
			System.out.println(c);
		}
	}
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
#define eb(t) emplace_back(t)
typedef long long ll;
typedef long long unsigned int llu;
ll INF = 1000000009;
ll MOD = 1000000007;

ll a[55];
ll b[55];
ll c[55];
ll d[55];


ll n,m,q_;

ll ans_s;

ll x[12];

ll ans(ll at, ll bt, ll ct, ll dt){
    ll tmp=0;
    if(x[bt-1]-x[at-1]==ct) tmp+=dt;
    return tmp;
}



// p以上の数の数列をx[q]より右に生成.
void dfs(ll p, ll q){
    if(q>=n){
        /*
        rep(i,n){
            cout << x[i];
        }
        */
        
        ll ans_all = 0;
        rep(i,q_){
            ans_all += ans(a[i],b[i],c[i],d[i]);
            //cout << " " << a[i] << " " << b[i] << " " << c[i] << " " << d[i] << " " << ans(a[i],b[i],c[i],d[i]);
        }
        //cout << " " << ans_all << endl;
        ans_s = max(ans_s, ans_all);
        return;
    }
    else{
        for(ll i=p; i<=m; i++){
            x[q]=i;
            dfs(i,q+1);
        }
    }
}



void solve(){

    cin >> n >> m >> q_;

    rep(i,q_){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }

    ans_s=0;

    dfs(1,0);

    cout << ans_s << endl;


}

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


Measured memory_bytes: 3536
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		double[] a = new double[n];
		
		double sum = 0.0;
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			sum += 1 / a[i];
		}
		
		System.out.println(1 / sum);
		
		sc.close();
	}
}


Measured memory_bytes: 25172
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
//const int mod = ;

ll n, X;

ll f(ll b, ll l, ll u, ll rem) {
  if (b * l >= rem) {
    return (rem + l - 1) / l;
  } else if (b * l + (X - b) * u >= rem) {
    return b + (rem - l * b + u - 1) / u;
  } else {
    return 1e18;
  }
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  cin >> n >> X;
  vl b(n), l(n), u(n), v(n);
  ll s = 0;
  vi ord(n);
  for (int i = 0; i < n; ++i) {
    cin >> b[i] >> l[i] >> u[i];
    v[i] = l[i] * b[i] + (X - b[i]) * u[i];
    s += l[i] * b[i];
    ord[i] = i;
  }
  if (s == 0) {
    cout << 0 << endl;
    return 0;
  }
  sort(ord.begin(), ord.end(), [&](int i, int j){return v[i] > v[j];});
  int k = 0;
  ll sum = 0;
  for (int i = 0; i < n && sum < s; ++i) {
    ++k;
    sum += v[ord[i]];
  }
  ll mi = k * X;
  cerr << k << endl;
  for (int i = k; i < n; ++i) {
    ll rem = s - sum + v[ord[k - 1]];
    int j = ord[i];
    mi = min(mi, (k - 1) * X + f(b[j], l[j], u[j], rem));
  }
  for (int i = 0; i < k; ++i) {
    int j = ord[i];
    ll rem = s - sum + v[j];
    mi = min(mi, (k - 1) * X + f(b[j], l[j], u[j], rem));
  }
  cout << mi << endl;
  return 0;
}


Measured memory_bytes: 3840
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;

int main(void) {
	char str[1001];
	int len, i, sum;
	while (1) {
		gets(str);
		len = strlen(str);
		for (i = 0, sum = 0; i < len; i++) {
			sum += str[i] - '0';
		}
		if (!sum)
			break;
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 1124
from math import factorial

N = int(input())
strings = {}
for _ in range(N):
    string = str(sorted(list(input().rstrip('\n'))))
    if string in strings:
        strings[string] += 1
    else:
        strings[string] = 1

count = 0
for value in strings.values():
    if value >= 2:
        count += factorial(value) // 2 // factorial(value - 2)

print(count)


Measured memory_bytes: 21984
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
	}
	return i
}

func main() {
	var N int
	var D int64
	var x, y int64
	res := 0

    sc.Split(bufio.ScanWords)
	N = nextInt()
	D = int64(nextInt())
	var DD int64
	DD = D * D

    for i := 0; i < N; i++ {
		x = int64(nextInt())
		y = int64(nextInt())
		
		if (DD >= x*x + y*y){
			res++
		}
    }

	fmt.Println(res)
}


   

Measured memory_bytes: 4892
mod = 10**9+7
N = int(input())
x = list(map(int, input().split()))
ans = 1
cnt = 1
now = 0
while now<N-1 and x[now]>=cnt*2-1:
    cnt+=1
    now+=1
ans*=cnt
ans%=mod
for i in range(1, N):
    cnt-=1
    while now<N-1 and x[now]>=cnt*2-1:
        cnt+=1
        now+=1
    ans*=cnt
    ans%=mod
print(ans)



Measured memory_bytes: 62704
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using vpii = vector<pair<int, int>>;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define rep1(i, n) for (int i = 1; i < (int)n; i++)
const ll mod = 1e9+7;
const ll inf = 1e10;
const double pi = 3.141592;

void dfs(vector<ll>& c , vector<vector<int>>& v , vector<int>& f , int id){
  f[id] = 1;
  for(const auto& nid : v[id]){
    if(f[nid]) continue;
    c[nid] += c[id];
    dfs(c, v, f, nid);
  }
  return;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  vector<vector<int>> v(n+1);
  rep(i, n-1){
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  vector<ll> counter(n+1, 0);
  vector<int> flag(n+1, 0);
  rep(i, q){
    int p, x;
    cin >> p >> x;
    counter[p] += x;
  }
  dfs(counter, v, flag, 1);
  rep(i, n) cout << counter[i+1] << "\n";
  return 0;
}

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

int main(void) {
  int N;
  cin >> N;
  vector<int> p(N), v(N);
  for (int i = 0; i < N; i++) {
    cin >> p[i];
    v[i] = p[i];
  }
  sort(v.begin(), v.end());
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (v[i] != p[i]) cnt++;
  }

  cout << (cnt == 2 || cnt == 0 ? "YES" : "NO") << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vv vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define INF 100000000000
#define eps 1e-7
#define mod 1000000007
#define itn int
#define int ll
using namespace std;

int N,K;
string S;
vi zeros;
vi ones;

signed main(void) {
    cin>>N>>K>>S;
    if (S[0]=='0') ones.pb(0);
    int cur=0;
    while(cur<N) {
        if (S[cur]=='0') {
            int con=0;
            while(S[cur]=='0') {
                con++;
                cur++;
            }
            zeros.pb(con);
        }
        if (S[cur]=='1') {
            int con=0;
            while(S[cur]=='1') {
                con++;
                cur++;
            }
            ones.pb(con);
        }
    }
    if (S[N-1]=='0') ones.pb(0);
    assert(ones.size()==zeros.size()+1);
//    for(auto e:ones) {
//        cerr<<e<<" ";
//    }
//    cerr<<endl;
//    for(auto e:zeros) {
//        cerr<<e<<" ";
//    }
//    cerr<<endl;
    if (zeros.size()<=K) {
        cout<<N<<endl;
        return 0;
    }
    int cand=ones[0];
    rep(i, K) {
        cand=cand+zeros[i]+ones[i+1];
    }
//    cerr<<cand<<endl;
    int ans=cand;
    rep(i, zeros.size()-K) {
        cand=cand-ones[i]-zeros[i]+ones[K+1+i]+zeros[K+i];
//        cerr<<cand<<endl;
        ans = max(ans,cand);
    }
    cout<<ans<<endl;
    return 0;
}

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

#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i < n; i++)

typedef long long ll;

long dfs(long N, string s){
    if(stoll(s) > N) return 0;

    long count = 0;
    if(s.find("7") != string::npos && s.find("5") != string::npos && s.find("3") != string::npos){
        count = 1;
    }

    count += dfs(N, s+"7");
    count += dfs(N, s+"5");
    count += dfs(N, s+"3");

    return count;
}

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

    cout<<dfs(N, "0")<<endl;
}

Measured memory_bytes: 256
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<cmath>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>
    #include<cassert>
    #include<cmath>
    #include<cstdint>
     
    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
    #define ALL(a)  (a).begin(),(a).end()
    #define chmin(a, b) a = min(a, b)
    #define chmax(a, b) a = max(a, b)
    #define pb push_back
     
    using namespace std;
    using ll = long long int;
    using Graph = vector<vector<int>>;
    using P = pair<ll, ll>;
     
const int MOD = 1e9 + 7;
const ll ZER = 0;


int main(){
    ll n, x, m;
    cin >> n >> x >> m;
    vector<ll> id(m, -1);
    vector<ll> a;
    ll len = 0;
    ll tot = 0;
    while(id[x] == -1){
        a.push_back(x);
        id[x] = len;
        len++;
        //トータルの和
        tot += x;
        x = x * x % m;
    }

    ll c = len - id[x];
    //周期の中の和
    ll s = 0;
    REP(i, id[x], len - 1)s += a[i];
    ll res = 0;
    if(n <= len){
        rep(i, n)res += a[i];
    }
    else {
        res += tot;
        n -= len;
        res += s * (n / c);
        n %= c;
        rep(i, n)res += a[id[x] + i];
    }
    cout << res << endl;
}



Measured memory_bytes: 4696