akhauriyash/Code-Regression huggingface dataset:
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(ll)(n);++i)
#define _repe3(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define _rrepe2(i,n) for(ll i=(ll)(n);i>=0;i--)
#define _rrepe3(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);i--)
#define rrepe(...) _overload3(__VA_ARGS__,_rrepe3,_rrepe2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;
const ll mod = 998244353;

ll N;
ll S;
vl A;

void solve();

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> N;
    cin >> S;
    A = vl(N);
    for(int i = 0; i < N; ++i){
        cin >> A[i];
    }
    solve();
}

// 入力は全て整数である。
// 1 <= N <= 3000
// 1 <= S <= 3000
// 1 <= A_i <= 3000

#ifndef TEMPLATE_USED
#include "../template/template.hpp"
#endif

template<int m>
struct MInt{
    //static int m;

    ll x;
    MInt(ll x=0):x((x%m+m)%m){}

    MInt operator-()const{return MInt(-x);}
    MInt operator+(const MInt &p)const{return MInt(*this)+=p;}
    MInt operator-(const MInt &p)const{return MInt(*this)-=p;}
    MInt operator*(const MInt &p)const{return MInt(*this)*=p;}
    MInt operator/(const MInt &p)const{return MInt(*this)/=p;}

    MInt &operator+=(const MInt &p){
        if((x+=p.x)>=m)x-=m;
        return *this;
    }
    MInt &operator-=(const MInt &p){
        if((x+=m-p.x)>=m)x-=m;
        return *this;
    }
    MInt &operator*=(const MInt &p){
        (x*=p.x)%=m;
        return *this;
    }
    MInt &operator/=(const MInt &p){
        return *this*=p.inv();
    }

    MInt pow(ll n)const{
        MInt ret(1),mul(x);
        while(n){
            if(n&1)ret*=mul;
            mul*=mul;
            n>>=1;
        }
        return ret;
    }
    MInt inv()const{
        //return pow(m-2);
        int a=x,b=m,u=1,v=0,t;
        while(b){
            t=a/b;
            swap(a-=t*b,b);
            swap(u-=t*v,v);
        }
        return MInt(u);
    }

    friend ostream& operator<<(ostream& os,const MInt& a) {return os<<a.x;}
};
//int MInt::m=0;
using mint=MInt<mod>;

// ll N, ll S, vl A
// f(T) の和を 998244353 で割ったあまりを出力せよ。
void solve(){
    /* (´~`) */
    vector<mint> dp(S+1);
    dp[0]=1;
    rep(i,N)rrepe(j,S){
        if(j+A[i]<=S)dp[j+A[i]]+=dp[j];
        dp[j]+=dp[j];
    }
    cout<<dp[S]<<endl;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	int n,m;
	cin >> n >> m;
	if(n==0&&m==0)break;
	m++;
	vector< vector<int> > dis(m,vector<int>(m,1000000));
	vector< vector<int> > mon(m,vector<int>(m,1000000));
	REP(i,n){
	    int a,b,cost,time;
	    cin >> a >> b >> cost >> time;
	    dis[a][b] = time;
	    dis[b][a] = time;
	    mon[a][b] = cost;
	    mon[b][a] = cost;
	}
	REP(k,m)REP(i,m)REP(j,m){
	    dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
	    mon[i][j] = min(mon[i][j],mon[i][k]+mon[k][j]);
	}
	cin >> n;
	REP(i,n){
	    int p,q,r;
	    cin >> p >> q >> r;
	    if(r == 0){
		cout << mon[p][q] << endl;
	    }else{
		cout << dis[p][q] << endl;
	    }
	}
    }
    return 0;
}

Measured memory_bytes: 1300
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
using namespace std;
#define int long long


signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    string s; cin >> s;
    string t = "keyence";

    if(s.substr(0,7) == "keyence" || s.substr(s.size()-7,s.size()-1) == "keyence"){
        cout << "YES" << endl;
        return 0;
    }

    for(int i = 1;i < 7;i ++){
        if(s.substr(0,i) == t.substr(0,i) && 
        s.substr(s.size()-7+i,7-i) == t.substr(i,7-i)){
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;



}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i==n-1];};
ll partition(ll A[], ll p, ll r){
    ll x = A[r];
    ll i = p-1;
    rep(j,p,r){
        if(A[j] <= x){
            i++;
            swap(A[i], A[j]);
        }
    }
    swap(A[i+1], A[r]);
    return i+1;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    ll A[100010];
    cin >> N;
    rep(i,0,N) cin >> A[i];
    ll pos = partition(A, 0, N-1);
    rep(i,0,N){
        if(i == pos){
            cout << "[" << A[i] << "]" << " \n"[i==N-1];
        }else{
            cout << A[i] << " \n"[i==N-1];
        }
    }

    
}


Measured memory_bytes: 3888
#include <iostream>

using namespace std;

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

	int total_syukudai = 0;
	for (int i = 0; i < M; i++) {
		int a;
		cin >> a;
		total_syukudai = total_syukudai + a;
	}

	if(N - total_syukudai >= 0) {
		cout << N - total_syukudai << endl;
	}
	else {
		cout << -1 << endl;
	}



}


Measured memory_bytes: 3628
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif
using namespace std;

int main() {
  int a,b;
  cin >> b >> a;
  vector<vector<int>> list(b, vector<int>(a));
  rep(i, b) {
    rep(j, a) {
      cin >> list[i][j];
    }
  }
  double tmp = 0.0;
  int ans = 0;
  int chk = 0;
  rep(i, b) {
    rep(j, b) {
      tmp = 0.0;
      rep(k, a) { 
        tmp += pow(list[i][k]-list[j][k],2);
      }
      chk = sqrt(tmp) * 1000;
      if (chk%1000 == 0) {
        ans++;
      }
    }
  }
  ans -= b;
  ans /= 2;
  cout << ans;
  return 0;
}
/*
//よく使うやつ
int N;
cin >> N;
vector<int> list(N);
for (int i = 0; i < N; i++) {
cin >> list[i];
}
// for文
for (int i = 0; i < N; i++) {
}
//配列
vector<int> list;
list.at(i)
vector<vector<int>> list(10, vector<int>(10));
sort(all(list));
sort(all(list), greater<int>());
//配列の内容表示
dout << "====listの内容====\n";
for (int i = 0; i < N; i++) dout << list[i] << endl;
dout << "====ここまで====\n";
*/


Measured memory_bytes: 256
#include <stdio.h>

int min(int a, int b){
  return a<b ? a :b;
}

int main(){
  int n,i,sum=0;
  
  scanf("%d",&n);
  
  i=1;
  while(i<=n){
    sum += min(n,i*10-1)-i+1;
    i *= 100;
  }
  
  printf("%d", sum);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H,W,D;
  cin>>H>>W>>D;
  int a[H+1][W+1];
  int x[H*W+1],y[H*W+1];
  for(int i=1; i<=H; i++){
    for(int j=1; j<=W; j++){
      cin>>a[i][j];
      x[a[i][j]]=i,y[a[i][j]]=j;
    }
  }
  int S[H*W+1];
  for(int i=1; i<=H*W; i++){
      if(i<D){continue;}
      S[i]=S[i-D]+(abs(x[i-D]-x[i])+abs(y[i-D]-y[i]));
  }
  int Q;
  cin>>Q;
  for(int i=0; i<Q; i++){
    int a,b;
    cin>>a>>b;
    cout<<S[b]-S[a]<<endl;
  }
} 

Measured memory_bytes: 2560
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
  vector<int> a(5);
  for(int i=0;i<5;i++){
    cin>>a.at(i);
  }
  
  int hantei;
  for(int i=0;i<5;i++){
    if(a.at(i)==0){
      hantei=i+1;
    }
  }
    cout<<hantei;
    
  return 0;
    
    
}

Measured memory_bytes: 3588
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static System.Array;

class Program
{
	public static void Main()
	{
		var n = ReadLine().Split().Select(decimal.Parse).ToArray();
		if(n[0] / n[2] <= n[1])
			WriteLine("Yes");
		else
			WriteLine("No");
	}
}


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

using namespace std;

int main() {
	string a;
	cin >> a;
	int i = 0;
	if (a.size() >= 8) {
		while (true) {
			if (a.size()-i < 8) {
				break;
			}
			string aizu = "AIDUNY";
			int counter[6] = {0};
			bool hantei = false;
			for (int k = i; k < i+8; k++) {
				for (int j = 0; j < 6; j++) {
					if (a[k] == aizu[j]) {
						counter[j]++;
						break;
					} else if (j == 5){
						i = k;
						hantei = true;
					}
				}
				if (hantei) {
					break;
				}
			}
			if (counter[0] == 2 && counter[1] == 1 && counter[2] == 1 && counter[3] == 1 && counter[4] == 2 && counter[5] == 1) {
				a[i] = 'A';
				a[i+1] = 'I';
				a[i+2] = 'Z';
				a[i+3] = 'U';
				a[i+4] = 'N';
				a[i+5] = 'Y';
				a[i+6] = 'A';
				a[i+7] = 'N';
				i += 7;
			}
			i++;
		}
	}
	cout << a << endl;
	return 0;
}

Measured memory_bytes: 1192
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pii pair<int,int> 
#define pb push_back
#define INF INT_MAX 
#define mod 1000000007ll
#define fi first
#define se second
#define f(i,p,q) for(int i=p;i<q;i++)
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define psi(a) printf(" %d",a)
#define poi(a) printf("%d",a)
#define sl(a) scanf("%lld",&a)
#define pl(a) printf("%lld\n",a)
#define Nline() printf("\n")
#define sstr(str) scanf("%s",str)
#define pstr(str) printf("%s\n",str)
#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define vi vector<int>
#define vvi vector<vi>
#define all(v) (v).begin(),(v).end()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())
#define ios ios::sync_with_stdio(false); cin.tie(0);cout.tie(NULL);
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
const char nl = '\n';
#define SZ(V) (int )V.size()
#define FORN(i, n) for(i = 0; i < n; i++)
#define FORAB(i, a, b) for(i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  (B) <= (A) && (A) <= (C)
#define AIN(A, B, C) assert(IN(A, B, C))
ll power(ll x, unsigned int y) {ll res = 1;	while (y > 0) { if (y & 1) res = res*x%mod; y = y>>1; x = (x*x)%mod;} return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
void solve(){
   int n;
   cin>>n;
ll ar[n];
   f(i,0,n)cin>>ar[i];
   int ans=0;
  // set<pair<int,pair<int,int>>>p;
   f(i,0,n)
   { f(j,i+1,n){
   	 	f(k,j+1,n){
   	 		if( ar[i]!=ar[j] &&ar[j]!=ar[k] &&ar[i]!=ar[k] &&ar[i]+ar[j]>ar[k] && ar[i]+ar[k]>ar[j] && ar[k]+ar[j]>ar[i]){
   	 			//cout<<ar[i]<<" "<<ar[j]<<" "<<ar[k]<<"\n";
   	 		    //p.insert({ar[i],{ar[j],ar[k]}});
   	 			ans++;
   	 		}
   	 	}
   	 }
   }
   // cout<<p.size();
    cout<<ans;
}
int main() {
    ios;
	int t=1;
	//cin>>t;
	while(t--)solve();
 
    
}


Measured memory_bytes: 3648
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(list(sys.stdin.readline())[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    s = S()
    N = len(s)
    for i in range(N-1):
        if s[i] == s[i+1]:
            return(" ".join(map(str,[i+1,i+2])))
    for i in range(N-2):
        if s[i] == s[i+2]:
            return(" ".join(map(str,[i+1,i+3])))
    return(" ".join(map(str,[-1,-1])))

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


Measured memory_bytes: 49776
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
int main() {
    ll n,m;
    const ll MOD = 1e9+7;
    std::cin >> n>>m;
    vector<ll> x(n);
    vector<ll> y(m);
    for (int i = 0; i < n; i++) {
        std::cin >> x[i];
    }
    for (int i = 0; i < m; i++) {
        std::cin >> y[i];
    }
    ll sum1 = 0;
    ll sum2 = 0;
    // どれくらい重複
    for (int i = 0; i < n-1; i++) {
        sum1 += (x[i+1]-x[i])%MOD*(i+1)%MOD*(n-1-i)%MOD;
        sum1 %= MOD;
    }
    for (int i = 0; i < m-1; i++) {
        sum2 += (y[i+1]-y[i])%MOD*(i+1)%MOD*(m-1-i)%MOD;
        sum2 %= MOD;
    }
    std::cout << sum1%MOD*sum2%MOD << std::endl;
}


Measured memory_bytes: 1792
input()
A = list(map(int,input().split()))

count = 0
flag = True
while(flag):
  for i in range(len(A)):
    if A[i]%2 == 0:
      A[i] = A[i]/2
    else:
      flag = False
      break
  count += 1
print(count - 1)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  int n, z, w;
  cin >> n >> z >> w;

  vector<int> a(n);
  for (auto& e : a) cin >> e;

  if (n == 1) {
    cout << abs(a[0]-w) << endl;
    return 0;
  }

  cout << max(abs(a[n-1] - w), abs(a[n-1] - a[n-2])) << endl;
  return 0;
}


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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int_fast32_t i = 0; i < ((int_fast32_t)(n)); i++)   // 0-indexed up
#define rep1(i,n) for(int_fast32_t i = 1; i <= ((int_fast32_t)(n)); i++) // 1-indexed up
#define rrep(i,n) for(int_fast32_t i = ((int_fast32_t)(n)-1); i >= 0; i--)  // 0-indexed down
#define rrep1(i,n) for(int_fast32_t i = ((int_fast32_t)(n)); i >= 1; i--)   // 1-indexed down
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/
vi mv_i = {1,0,-1,0};
vi mv_j = {0,-1,0,1};

/*MAIN==================================================*/
signed main(){
    int START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
//    cout << fixed << setprecision(15);

    /**
     * 全点からBFSすれば良さそう。
     * それで白黒移動できるルートがいくつか得られるので、
     * それぞれのルートで白の個数 * 黒の個数を計算。
     * これの総和を求める。
     */

    i32 h,w; cin >> h >> w;
    vec<vec<char>> s(h, vec<char>(w));
    rep(i,h) rep(j,w) cin >> s[i][j];


    queue<PII> que;
    vii seen(h, vi(w, -1));
    i32 route_id = 0;
    rep(si, h) rep(sj, w) {
        if(seen[si][sj] != -1) continue;

        que.emplace(si, sj);
        seen[si][sj] = route_id;

        while(que.size()) {
            i32 i, j;
            tie(i,j) = que.front(); que.pop();
            rep(idx, 4) {
                i32 ni = i + mv_i[idx], nj = j + mv_j[idx];
                if(!(0 <= ni && ni < h && 0 <= nj && nj < w)) continue;
                if(s[ni][nj] == s[i][j]) continue;
                if(seen[ni][nj] != -1) continue;
                seen[ni][nj] = route_id;
                que.emplace(ni, nj);
            }
        }

        ++route_id;
    }

    vi white(route_id), black(route_id);
    rep(i,h) rep(j,w) {
        if(seen[i][j] == -1) continue;
        if(s[i][j] == '#') ++black[seen[i][j]];
        else ++white[seen[i][j]];
    }

    i64 ans = 0;
    for(i32 i = 0; i < route_id; ++i) {
        ans += black[i] * white[i];
    }

    cout << ans << '\n';

    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 3712
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>

using namespace std;

using PLI = pair<long long, int>;

long long calc(vector<long long> x, vector<long long> y, vector<long long> z, int type, int m) {

	priority_queue<PLI> que;

	for (int i = 0; i < x.size(); i++) {
		x[i] *= type & 1 ? 1 : -1;
		y[i] *= type & 2 ? 1 : -1;
		z[i] *= type & 4 ? 1 : -1;
		que.push(make_pair(x[i] + y[i] + z[i], i));
	}

	long long a = 0;
	long long b = 0;
	long long c = 0;

	for (int i = 0; i < m; i++) {
		int idx = que.top().second;
		que.pop();

		a += x[idx];
		b += y[idx];
		c += z[idx];

	}
	long long ret = abs(a) + abs(b) + abs(c);
	return ret;

}

int main() {
	int n, m;
	cin >> n >> m;

	vector<long long> x(n, 0), y(n, 0), z(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> z[i];
	}

	long long ans = 0;
	for (int i = 0; i < 8; i++) {
		auto tmp = calc(x, y, z, i, m);
		ans = max(ans, tmp);
	}

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


Measured memory_bytes: 384
#include <cstdio>
#include <vector>
#include <utility>

using namespace std;

vector<pair<int, int> > ans;

void cw(int loc)
{
    for (int i = 1; i <= loc - 1; i++) {
        ans.push_back(make_pair(i, 0));
    }
    ans.push_back(make_pair(loc-1, 1));
    ans.push_back(make_pair(loc, 1));
    for (int i = loc; i >= 0; i--) {
        ans.push_back(make_pair(i, 0));
    }
}

void ccw(int loc)
{
    for (int i = 1; i <= loc; i++) {
        ans.push_back(make_pair(i, 0));
    }
    ans.push_back(make_pair(loc, 1));
    ans.push_back(make_pair(loc-1, 1));
    for (int i = loc - 1; i >= 0; i--) {
        ans.push_back(make_pair(i, 0));
    }
}

void work(vector<int>& elems, vector<int>& ops)
{
    if (elems.size() == 1) {
        ops.push_back(elems[0]); return;
    }
    vector<int> left;
    vector<int> right;
    for (int i = 0; i < elems.size() / 2; i++) {
        left.push_back(elems[i]);
    }
    for (int i = elems.size() / 2; i < elems.size(); i++) {
        right.push_back(elems[i]);
    }
    vector<int> leftans;
    vector<int> rightans;
    work(left, leftans);
    work(right, rightans);
    for (int i = 0; i < leftans.size(); i++) {
        ops.push_back(leftans[i]);
    }
    for (int i = 0; i < rightans.size(); i++) {
        ops.push_back(rightans[i]);
    }
    reverse(leftans.begin(), leftans.end());
    reverse(rightans.begin(), rightans.end());
    for (int i = 0; i < leftans.size(); i++) {
        ops.push_back(-leftans[i]);
    }
    for (int i = 0; i < rightans.size(); i++) {
        ops.push_back(-rightans[i]);
    }
}

char s[500]; int n;

int main()
{
    ans.push_back(make_pair(0, 0));
    scanf("%d", &n);
    scanf("%s", s);
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < (1 << n); j++) {
            if ((i & j) == i && s[i] == '0' && s[j] == '1') {
                printf("Impossible"); return 0;
            }
        }
    }
    for (int i = 0; i < (1 << n); i++) {
        if (s[i] == '1') continue;
        bool good = true;
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) && s[i ^ (1 << j)] == '0') good = false;
        }
        if (!good) continue;
        vector<int> elems;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) elems.push_back(j + 1);
        }
        vector<int> ops;
        work(elems, ops);
        for (int j = 0; j < ops.size(); j++) {
            if (ops[j] > 0) {
                cw(ops[j]);
            } else {
                ccw(-ops[j]);
            }
        }
    }
    printf("Possible\n%d\n", (int)(ans.size()) - 1);
    for (int i = 0; i < ans.size(); i++) {
        printf("%d %d\n", ans[i].first, ans[i].second);
    }
    return 0;
}


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


signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
    cout << fixed << setprecision(20);

    int h,w;
    char a,b;
    cin>>h>>w>>a>>b;
    string s[h];
    int dp[26][26];
    int INF = 1e9;
    for(int i=0;i<26;i++){
        for(int j=0;j<26;j++){
            dp[i][j] = INF;
            if(i==j) dp[i][j] = 0;
        }
    }
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    bool used[h][w] = {};
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(used[i][j]) continue;
            if(s[i][j] == '|'){
                char u='0',v='0';
                for(int k=i;k>=0;k--){
                    used[k][j] = 1;
                    if(s[k][j] !='o' && s[k][j] !='.' && s[k][j]!='|'){
                        u = s[k][j];
                        break;
                    }
                }
                for(int k=i;k<h;k++){
                    used[k][j] = 1;
                    if(s[k][j] !='o' && s[k][j] !='.' && s[k][j]!='|'){
                        v = s[k][j];
                        break;
                    }
                }
                //cerr << i << " " << j << " " << u << " " << v << endl;
                if(u!='0' && v!='0') {
                    dp[u-'A'][v-'A'] = 1;
                    dp[v-'A'][u-'A'] = 1;
                }
            }
            if(s[i][j] == '-'){
                char u='0',v='0';
                for(int k=j;k>=0;k--){
                    used[i][k] = 1;
                    if(s[i][k]!='o' && s[i][k]!='.' && s[i][k] !='-'){
                        u = s[i][k];
                        break;
                    }
                }
                for(int k=j;k<w;k++){
                    used[i][k] = 1;
                    if(s[i][k]!='o' && s[i][k]!='.' && s[i][k] !='-'){
                        v = s[i][k];
                        break;
                    }
                }
                //cerr << i << " " << j << " " << u << " " << v << endl;
                if(u!='0' && v!='0') {
                    dp[u-'A'][v-'A'] = 1;
                    dp[v-'A'][u-'A'] = 1;
                }
            }
        }
    }
    for(int k=0;k<26;k++)for(int i=0;i<26;i++)for(int j=0;j<26;j++){
        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
    }
    cout << dp[a-'A'][b-'A'] << endl;

    
}


Measured memory_bytes: 3232
n=gets.to_i
a=gets.split.map(&:to_i).sort
f=true
i=0
if n.odd?
  n.times do |i|
    f=false if a[i]!=(i+1)/2*2
  end
else
  n.times do |i|
    f=false if a[i]!=i/2*2+1
  end
end
puts f ? 2**(n/2)%1000000007 : 0

Measured memory_bytes: 9968
unittest
{
	assert( [ "5 4 1", "1 2", "2 3", "3 4", "3 5" ].solve == 2 );
	assert( [ "5 4 5", "1 2", "1 3", "1 4", "1 5" ].solve == 1 );
	assert( [ "2 1 2", "1 2" ].solve == 0 );
	assert( [ "9 6 1", "1 2", "2 3", "3 4", "4 5", "5 6", "4 7", "7 8", "8 9" ].solve == 5 );
}



import std.algorithm;
import std.container;
import std.conv;
import std.format;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto u = 0L;
	auto v = 0L;
	input.front.formattedRead!"%s %s %s"( n, u, v );
	u--;
	v--;
	auto abs = new long[ 2 ][ n - 1 ];
	foreach( ref ab; abs )
	{
		input.popFront;
		ab = input.front.split.to!( long[] );
		ab[] -= 1;
	}
	
	// 移動範囲を探索
	auto nss = toAdjacencyList!true( n, abs );
	auto as = bfs( nss, v );
	auto ts = bfsEx( nss, as, u );
	
	// 端に追い詰められるパターンのターン数を計算
	auto ans = 0L;
	foreach( i, t, a; lockstep( ts, as ) )
	{
		if( nss[ i ].length == 1 && t <= a ) ans = max( ans, a - 1 );
	}
	return ans;
}

// 辺配列から隣接リストを作成
auto toAdjacencyList( bool undirected = false )( long n, long[ 2 ][] es )
{
	auto nss = new long[][ n ];
	foreach( e; es )
	{
		nss[ e[ 0 ] ] ~= e[ 1 ];
		static if( undirected ) nss[ e[ 1 ] ] ~= e[ 0 ];
	}
	return nss;
}

// グラフの始点指定最短経路探索（幅優先探索）
auto bfs( long[][] nss, long s )
{
	auto ds = new long[ nss.length ];
	ds[] = long.max;
	ds[ s ] = 0;
	
	auto queue = make!DList( s );
	while( !queue.empty )
	{
		auto f = queue.front;
		queue.removeFront();
		
		foreach( t; nss[ f ] )
		{
			if( ds[ t ] < long.max ) continue;
			
			ds[ t ] = ds[ f ] + 1;
			queue.insertBack( t );
		}
	}
	return ds;
}

// グラフの始点指定最短経路探索（幅優先探索）
auto bfsEx( long[][] nss, long[] as, long s )
{
	auto ds = new long[ nss.length ];
	ds[] = long.max;
	ds[ s ] = 0;
	
	auto queue = make!DList( s );
	while( !queue.empty )
	{
		auto f = queue.front;
		queue.removeFront();
		
		foreach( t; nss[ f ] )
		{
			if( ds[ t ] < long.max || as[ t ] <= ds[ f ] ) continue;		// 青木君とすれ違うことはできない
			
			ds[ t ] = ds[ f ] + 1;
			queue.insertBack( t );
		}
	}
	return ds;
}


Measured memory_bytes: 16088
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int n,i,y,x,m;
    cin>>n>>m;
    int ar[n+1],ans[n+1],vis[n+1];
    for(i=1;i<=n;i++)
    {
        cin>>ar[i];
        ans[i]=1;
        vis[i]=0;
    }
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        if(ar[x]>ar[y])
        {
            ans[x]=ans[x]&1;
            ans[y]=ans[y]&0;
        }
        else if(ar[y]>ar[x])
        {
            ans[y]=ans[y]&1;
            ans[x]=ans[x]&0;
        }
        else
        {
            ans[y]=ans[y]&0;
            ans[x]=ans[x]&0;
            
        }
        vis[x]=1;
        vis[y]=1;
    }
    ll res=0;
    for(i=1;i<=n;i++)
    {
        if(ans[i]==1 or vis[i]==0)
        {
            res+=1;
            //cout<<ar[i]<<" ";
        }
    }
    //cout<<"\n";
    cout<<res<<"\n";
    
    return 0;
}

Measured memory_bytes: 4752
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Numerics;
using System.IO;
using System.Runtime.InteropServices;
using static System.Math;
using static io;
public class CompetitiveProgramming
{
  public void Solve()
  {
    var s = Strs;
    var st = new Stack<int>();
    for (int i = 0; i < s.Length; ++i)
    {
      if (s[i] == "+")
      {
        st.Push(st.Pop() + st.Pop());
      }
      else if (s[i] == "-")
      {
        st.Push(-st.Pop() + st.Pop());
      }
      else if (s[i] == "*")
      {
        st.Push(st.Pop() * st.Pop());
      }
      else st.Push(int.Parse(s[i]));
    }
    Write(st.Pop());
  }
}



class Program
{
  static void Main(string[] args)
  {
    var CompetitiveProgramming = new CompetitiveProgramming();
    CompetitiveProgramming.Solve();
  }
}
public static class io
{
  public static string Str => Console.ReadLine();
  public static string[] Strs => Str.Split(' ');
  public static long[] Longs => Strs.Select(long.Parse).ToArray();
  public static int[] Ints => Strs.Select(int.Parse).ToArray();
  public static char[] Chars => Str.ToArray();
  public static double[] Doubles => Strs.Select(double.Parse).ToArray();
  public static long Long1 => Longs[0];
  public static int Int1 => Ints[0];
  public static char Char1 => Chars[0];
  public static double Double1 => Doubles[0];
  public static long[] VerticalRead(int N) { long[] A = new long[N]; for (int i = 0; i < N; ++i) A[i] = Long1; return A; }
  public static void Write(string a) => Console.WriteLine(a);
  public static void Write(params object[] i) => Write(string.Join(" ", i));
  public static void Write<T>(IEnumerable<T> a) => Write(string.Join(" ", a));
  public static void Verticalwrite<T>(IEnumerable<T> a) { foreach (var z in a) Write(z); }
  public static void YN(bool i) { if (i) Write("Yes"); else Write("No"); }
}



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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T>
string join(const vector<T>&v, string del=", "){ stringstream s;
    for(auto x : v) s << del << x; return s.str().substr(del.size());
}
template<typename T>
ostream& operator<<(ostream& o, const vector<T>&v){
    if(v.size()) o << "[" << join(v) << "]"; return o;
}
template<typename T>
ostream& operator<<(ostream& o, const vector<vector<T> >&vv){
    int l = vv.size();
    if(l){ o<<endl; rep(i,l) o << (i==0 ? "[ " : ",\n  " ) << vv[i] << (i==l-1 ? " ]" : ""); }
    return o;
}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

struct UnionFind {
    int n;
    vector<int> dat;
    UnionFind(int size): n(size), dat(size, -1) { }
    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (dat[y] < dat[x]) swap(x, y);
            dat[x] += dat[y];
            dat[y] = x;
        }
        return x != y;
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    int root(int x){
        return dat[x] < 0 ? x : dat[x] = root(dat[x]);
    }
    int size(int x){
        return -dat[root(x)];
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");
    int n,m; cin >> n >> m;
    vector<pii> es;
    rep(i,m){
        int a,b; cin >> a >> b;
        a--; b--;
        es.emplace_back(a, b);
    }

    int ans = 0;
    rep(i,m){
        auto uf = UnionFind(n);
        rep(j,m){
            if(i != j) uf.unite(es[j].fi, es[j].se);
        }
        if(!uf.same(es[i].fi, es[i].se)) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

const int INF = 1e9 + 239;

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

	int n, L;
	cin >> n >> L;
	int s = 0;
	int m1 = -INF;
	int m2 = INF;
	for (int i = 1; i <= n; i++) {
		int c = L + i - 1;
		s += c;
		if (c < 0) m1 = max(m1, c);
		else m2 = min(m2, c);
	}
	if (abs(m1) < abs(m2)) cout << s - m1 << endl;
	else cout << s - m2 << endl;
}


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

int ans;
char a[200005];

int main() {
	int n; cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	int l = 0, r = n - 1;
	while (l < r) {
		while (a[l] == 'R') l++;
		while (a[r] == 'W') r--;
		if (l < r) { ans++; swap(a[l], a[r]); }
	}
	cout << ans << endl;
}


Measured memory_bytes: 3756
#include<iostream>

using namespace std;

int main(){
	int W,H,x,y,r;
	cin>> W>> H>> x>> y>> r;
	if(x>=r && x<=W-r && y>=r && y<=H-r){
		cout<< "Yes"<<endl;
	}
	else{
		cout<< "No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
#include <stdint.h>

int main(void) {
  int64_t N, M;
  scanf("%ld %ld", &N, &M);

  if(N >= (M/2)) {
    printf("%ld\n", M/2);
  } else {
    int64_t REM = (M - 2 * N) / 4;
    printf("%ld\n", N+REM);
  }
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll max_n=1e5+100;
const ll inf=0x3f3f3f3f;
ll t,n,m,p[max_n],v[max_n],q[max_n],dp[max_n];
int main(){
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    while(cin>>n>>m){
        for(int i=0;i<n;i++){
            cin>>p[i]>>q[i];
        }
        memset(dp,0,sizeof(dp));
        ll ans=0;
        for(int i=0;i<n;i++){
            for(int j=m;j>=p[i];j--){
                dp[j]=max(dp[j],dp[j-p[i]]+q[i]);
                ans=max(ans,dp[j]);
            }
        }cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 4412
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

string str[2];
short dp[4001][4001];

void solve()
{
	
	short ans = 0;


	if(str[0].length() > str[1].length()){
		swap(str[0],str[1]);
	}
	for(short i = 0; i < 4001; i++){
		for(short j = 0; j < 4001; j++)
			dp[j][i] = 0;
	}
	for(short i = 0; i < str[0].length(); i++){
		for(short j = 0; j < str[1].length(); j++){
			if(str[0][i] == str[1][j]){
				dp[j+1][i+1] += (dp[j][i]+1);
				ans = max(ans,dp[j+1][i+1]);
			}


		}
	}
	
/*
// dp表 確認(日本語)
// dp-table checking(English)

	cout << " ";
	for(short i = 0; i < str[0].length(); i++)
		cout << "  " << str[0][i];
	cout << endl;

	for(short i = 0; i < str[1].length(); i++){
		cout << str[1][i];
		for(short j = 0; j < str[0].length(); j++)
			prshortf("%3d", dp[i][j]);
		cout << endl;
	}
*/
	cout << ans << endl;

			
	
}


int main(void)
{
	while(cin >> str[0] >> str[1], !cin.eof()){
		solve();
	}

	return 0;
}

Measured memory_bytes: 32468
import java.util.*;

public class Main {
    public static void main(String[] args) {
        new Main().solve();
    }

    void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int x[] = new int[N];
        int y[] = new int[N];
        int h[] = new int[N];
        for (int i = 0; i < N; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            h[i] = sc.nextInt();
        }
        for (int i = 0; i <= 100; i++) {
            for (int j = 0; j <= 100; j++) {
                int H = 0;
                Boolean B = true;
                for (int k = 0; k < N; k++) {

                    if (h[k] != 0) {
                        H = h[k] + Math.abs(x[k] - i) + Math.abs(y[k] - j);
                    }
                }
                for (int k = 0; k < N; k++) {
                    if (h[k] != Math.max(H - Math.abs(x[k] - i) - Math.abs(y[k] - j), 0)) {
                        B = false;
                    }
                }
                if (B) {
                    System.out.println(i + " " + j + " " + H);
                }
            }
        }
    }
}

Measured memory_bytes: 23208
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  int a[n];
  int ans=1;
  rep(i,n){
    cin>>a[i];
    if(i!=0 &&  a[i-1]>=a[i]) ans++;
  }
  cout<<ans<<endl<<n<<endl;
  

  return 0;
}



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

using ll=long long;
using vec=valarray<ll>;
using mat=valarray<vec>;

const ll mod=1000000009;

vec mul(mat a,vec b){
	int m=a.size();
	vec c(0LL,m);
	rep(i,m)rep(j,m){
		c[i]+=1LL*a[i][j]*b[j]%mod;
		c[i]%=mod;
	}
	return c;
}

mat mul(mat a,mat b){
	int m=a.size();
	mat c(vec(0LL,m),m);
	rep(i,m)rep(j,m) rep(k,m){
		c[i][j]+=1LL*a[i][k]*b[k][j]%mod;
		c[i][j]%=mod;
	}
	return c;
}

mat power(mat a,ll n){
	int m=a.size();
	mat b(vec(0LL,m),m);
	rep(i,m) b[i][i]=1;
	while(n){
		if(n&1) b=mul(b,a);
		a=mul(a,a);
		n>>=1;
	}
	return b;
}

int main(void){
	ll w,h,n;
	int T=0;
	while(cin >> w >> h >> n,w){
		map<ll,vector<ll>> obj;
		rep(i,n){
			ll x,y;
			cin >> x >> y;
			obj[y-1].emplace_back(x-1);
		}
		
		mat A(vec(0LL,w),w);
		vec ans(0LL,w); ans[0]=1LL;
	
		rep(i,w){
			if(i-1>=0) A[i][i-1]=1LL;
			A[i][i]=1LL;
			if(i+1<w) A[i][i+1]=1LL;
		}
		
		ll cur=0LL;
		for(auto &it:obj){
			ll y=it.first;
			ans=mul(power(A,y-cur),ans);
			for(auto &x:it.second) ans[x]=0LL;
			cur=y;
		}
		ans=mul(power(A,h-1-cur),ans);
		cout << "Case " << ++T << ": "<< ans[w-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 3248
#include <stdio.h>

int H, W;
char s[128][128];

int miyukiti[128][128];

int main(void) {
	int i, j;
	if (scanf("%d%d", &H, &W) != 2) return 1;
	for (i = 0; i < H; i++) {
		if (scanf("%127s", s[i]) != 1) return 1;
	}
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			if (i == 0 && j == 0) {
				miyukiti[0][0] = (s[0][0] != '.');
			} else {
				int mareitaso = 9999;
				if (j > 0) {
					int tomatu = miyukiti[i][j - 1] + (s[i][j - 1] == '.' && s[i][j] != '.');
					if (tomatu < mareitaso) mareitaso = tomatu;
				}
				if (i > 0) {
					int sumipe = miyukiti[i - 1][j] + (s[i - 1][j] == '.' && s[i][j] != '.');
					if (sumipe < mareitaso) mareitaso = sumipe;
				}
				miyukiti[i][j] = mareitaso;
			}
		}
	}
	printf("%d\n", miyukiti[H - 1][W - 1]);
	return 0;
}

/*

右か下にしか行かない経路だから、矩形で経路が1区間だけ囲める。
→ 黒への突入回数を最小化

*/


Measured memory_bytes: 1784
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <codecvt>
#include <locale>
#include <numeric>
using namespace std;
using ll = long long;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    for(int i=0; i<N; ++i) {
        cin >> a[i];
    }
    ll sum = accumulate(a.begin(), a.end(), 0LL);
    sort(a.rbegin(), a.rend());
    int res = 0;
    vector<bool> dp(K);
    dp[0] = true;
    for(int i=0; i<N; ++i) {
        bool f = false;
        for(int j=0; j<K; ++j) {
            f |= dp[j] && j+sum >= K;
        }
        if(!f) {
            res++;
        }
        sum -= a[i];
        for(int j=K-1-a[i]; j>=0; --j) {
            dp[j+a[i]] = dp[j+a[i]] | dp[j];
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

//#define DEBUG
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>


int main() {
#ifdef DEBUG

#endif
	int N;
	int i;
	int tmp;
	int cnt = 1;

	//*
	scanf("%d", &N);
	/*/
	int j;
	for (j = 1000; j <= 1200; j++) {
		N = j;
		printf("%d ", N);
	//*/
	tmp = N % 10;
	N /= 10;
	cnt = 1;
	for (i = 1; i < 4; i++) {
		if (tmp == N % 10) {
			cnt++;
		}
		else {
			cnt = 1;
			tmp = N % 10;
		}
		//printf("cnt=%d\n", cnt);
		N /= 10;
		if (cnt == 3)break;
	}

	if (cnt >= 3) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	//}

}

Measured memory_bytes: 128
n = int(input())
t = [0]
x = [0]
y = [0]
for i in range(n):
    ti, xi, yi = map(int, input().split())
    t.append(ti)
    x.append(xi)
    y.append(yi)

flag = 0
for i in range(1, n+1):
    time = t[i] - t[i-1]
    dst = abs(x[i]-x[i-1]) + abs(y[i]-y[i-1])
    if time < dst or (time - dst) % 2 == 1:
        flag = 1
if flag:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 11728
n = int(input())
nums = list(map(int,input().split()))

nums.sort()

if n%2==1:
    print(0)
else:
    x=int((n/2)-1)
    y=int(n/2)
    a=nums[x]
    b=nums[y]
    s=b-a
    print(s)

Measured memory_bytes: 14428
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
const int mod=1e9+7;

int main(){
  int n;cin>>n;
  int a[n];rep(i,n)cin>>a[i];
  int m=1e9+7;
  int ctr=0;
  vector<int> p(2*n+5);
  rep(i,n)p[i]=-1;
  rep(i,n,2*n+5)p[i]=mod;
  rep(i,n){
    auto it=lower_bound(all(p),a[i]);
    --it;
    *it=a[i];
  }
  rep(i,2*n+5){
    if(p[i]!=-1&&p[i]!=mod)ctr++;
  }
  cout<<ctr<<endl;
}


Measured memory_bytes: 1408
#include <iostream>
#include <cassert>
#include <iomanip>
#include <utility>
#include <cmath>
#include <numeric>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

typedef long long ll;
typedef pair<int, int> p_i;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repext(i, a, b) for (int i = a; i < b; i++)
#define reprev(i, n) for (int i = n - 1; i >= 0; i--)
#define repextrev(i, a, b) for (int i = b - 1; i >= a; i--)
#define vec_all(vec) vec.begin(), vec.end()

// vectorデバッグ
template<typename T>
void dump_vec(vector<T> vec) {
    rep(i, vec.size()) {
        cout << vec[i] << endl;
    }
}

// --- notice ---
// intの和はllにしろ

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

    vector<int> p(n);
    rep(i, n) {
        cin >> p[i];
    }

    int count = 0;
    rep(i, n) {
        if (i + 1 == p[i]) {
            if (i != n - 1) {
                swap(p[i], p[i + 1]);
            }

            count++;
        }
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<set>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1

#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 1000000007;
const int INF = 2000000000;

    string S,T;
    ll N,ans=0;
    ll A[110];
    bool F=true;
int main(){
    ios_base::sync_with_stdio(false);
    cin>>N;
    REP(i,N){cin>>A[i];}
    sort(A,A+N,std::greater<ll>());
    REP(i,N){
        DEB(A[i])END
        if(i%2)ans-=A[i];
        else ans+=A[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
N=int(input())
list1=[]

s=input()
S=s
list1.append(s)
#print(list1[0][-1])
for i in range(N-1):
    s=input()
    #print(s)
    #print(s[len(s)-1])
    if s in list1:
        print("No")
        exit()
    elif s[0] != S[len(S)-1]:
        print("No")
        exit()
    else:
        S=S+s
        list1.append(s)
print("Yes")


Measured memory_bytes: 3060
MOD = (10**9) + 7
n = int(input())
a = list(map(int,input().split()))

cnt = [0] * 60

for num in a:
  for j in range(60):
    cnt[j] += (num >> j) % 2
ans = 0
for b in range(60):
  ans += cnt[b] * (n-cnt[b]) << b
  
ans %= MOD
print(ans)

Measured memory_bytes: 122808
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main {
    public static void main(String args[]) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String buf;
 
        try {
            int sum = 0;
            String index = "0123456789";
            while ((buf = br.readLine())!=null) {
                for (int i=0;i<buf.length();i++) {
                    String str = "";
                    while (index.indexOf(buf.charAt(i))!=-1) {
                        str = str+buf.charAt(i);
                        if (i+1<buf.length()) i++;
                        else break;
                    }
                    if (!str.equals("")) sum += Integer.parseInt(str);
                }
            }
            System.out.println(sum);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Measured memory_bytes: 24204
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1e9+7;
const llint big=(llint)(2.19e15+1);
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int main(void){
	cout<<setprecision(20);
	lldo a,b,C;cin>>a>>b>>C;
	C*=pai;C/=180;
	lldo S=a*b*sin(C)/2;cout<<S<<endl;
	lldo L=a+b+sqrt(a*a+b*b-2*a*b*cos(C));cout<<L<<endl;
	lldo h=2*S/a;cout<<h<<endl;
	RE;
}


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

int main(){
  int S;
  cin >> S;
    
  int h = S / 60 / 60;
  int m = S / 60 - (h * 60);
  int s = S - (h * 60 * 60) - (m * 60);
  
  cout << h;
  cout << ':';
  cout << m;
  cout << ':'; 
  cout << s << endl;

  return 0;
}


Measured memory_bytes: 3092
l, r = map(int, input().split())

i_max = min(r, l+2019)
mod_min = 2019
for i in range(l, i_max):
    j_max = min(r, i+2019)
    for j in range(i+1, j_max+1):
        mod = (i*j) % 2019
        if mod < mod_min:
            mod_min = mod

print(mod_min)


Measured memory_bytes: 2940
use std::io::stdin;fn main(){let mut st=String::new();stdin().read_line(&mut st).unwrap();let a:Vec<_>=st.trim().split(' ').map(|x| x.parse().unwrap()).collect();let r=(1..1001).find(|x| x*8/100==a[0] && x/10==a[1]).unwrap_or(-1);println!("{}",r)}

Measured memory_bytes: 4352