akhauriyash/Code-Regression huggingface dataset:
# include <algorithm>
# include <cassert>
# include <cctype>
# include <cstdio>
# include <cstdlib>
# include <cstring>
# include <cmath>
# include <iostream>
# include <map>
# include <queue>
# include <set>
# include <sstream>
# include <stack>
# include <string>
# include <vector>
# include <iomanip>

# define rep(i, n) for (int i = 0; i < (int)(n); i++)
# define irep(i, n) for (int i = int(n) - 1; i >= 0; i--)
# define FOR(i, m, n) for (int i = int(m); i < (int)(n); i++)

using namespace std;

int d[21][21];


bool clear() {
  int res = 0;

  for (int i=0; i<21; i++) {
    for (int j=0; j<21; j++) {
      res += d[i][j];
    }
  }

  return res == 0;
}


int main() {
  int n, x, y, z; // z: window
  char dir; // direction

  map<char, vector<int>> m;
  m['N'] = { 0, 1};
  m['E'] = { 1, 0};
  m['S'] = { 0, -1};
  m['W'] = {-1, 0};

  while (cin >> n && n) {
    rep (i, 21) rep(j, 21) d[i][j] = 0;

    vector<int> p = {10, 10}; // ?????¨???

    for (int i=0; i<n; i++) {
      cin >> x >> y;
      d[x][y] = 1;
    }

    cin >> n;
    for (int i=0; i<n; i++) {
      cin >> dir >> z;

      for (int t=0; t<z; t++) {
        p[0] += m[dir][0];
        p[1] += m[dir][1];

        d[p[0]][p[1]] = 0;
      }
    }

    if (clear()) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 3040
import java.io.*;

public class Main {
	public static void main(String[] args) {
		try {
			BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
			int n;
			while (0 != (n = Integer.parseInt(in.readLine()))) {
				int[] num = new int[n];
				long[] tot = new long[n];
				int size = 0;
				for (int i = 0; i < n; i++) {
					int[] cur = new int[3];
					String[] s = in.readLine().split(" ");
					for (int j = 0; j < 3; j++) {
						cur[j] = Integer.parseInt(s[j]);
					}
					int idx;
					for (idx = 0; idx < size && num[idx] != cur[0]; idx++) {}
					num[idx] = cur[0];
					tot[idx] += cur[1] * (long) cur[2];
					if (idx == size) {
						size++;
					}
				}
				boolean flg = true;
				for (int i = 0; i < size; i++) {
					if (tot[i] >= 1000000) {
						flg = false;
						System.out.println(num[i]);
					}
				}
				if (flg) {
					System.out.println("NA");
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 11000
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define print(x) cout << x << endl;
using namespace std;
typedef long long ll;

int main()
{
    int N;
    cin >> N;
    int W[N] = {};
    int w;
    rep(i, N) {
        cin >> w;
        if (i == 0) W[i] = w;
        else W[i] += w + W[i - 1];
    }

    int ans = 100000;

    rep(i, N) {
        ans = min(abs(ans), abs(W[N-1] - 2 * W[i]));
    }
    

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;

int main(){
//	IOS;
	long long int a,b;
	cin >> a >> b;
	int cnt=0;
	while(a<=b) cnt++,a*=2;
	cout << cnt << '\n';
	return 0;
}


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

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

using namespace std;

enum Result {
    STAY,
    FALL_RIGHT,
    FALL_LEFT,
};

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

    int N, Q;
    string s;
    cin >> N >> Q >> s;
    vector<char> t(Q), d(Q);
    REP(i, Q) {
        cin >> t[i] >> d[i];
    }

    function<Result(int)> f = [&](int x) {
        REP(i, Q) {
            if (t[i] == s[x]) {
                if (d[i] == 'L') {
                    --x;
                    if (x == -1) {
                        return FALL_LEFT;
                    }
                } else if (d[i] == 'R') {
                    ++x;
                    if (x == N) {
                        return FALL_RIGHT;
                    }
                }
            }
        }
        return STAY;
    };

    int result = N;

    int low = 0;
    int high = N;
    while (low < high) {
        int step = (high - low) / 2;
        int x = low + step;
        if (f(x) == FALL_RIGHT) {
            high = x;
        } else {
            low = x + 1;
        }
    }
    result -= N - low;

    low = -1;
    high = N - 1;
    while (low < high) {
        int step = (high - low) / 2;
        int x = high - step;
        if (f(x) == FALL_LEFT) {
            low = x;
        } else {
            high = x - 1;
        }
    }
    result -= high + 1;

    cout << result << endl;

    return 0;
}


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

int main() {
  int n;
  cin >> n;
  multiset<int> st;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) {
    auto itr = st.upper_bound(-a[i]);
    if(itr != st.end()) st.erase(itr);//eraseで全部消えない？
    st.insert(-a[i]);
  }
  cout << st.size() << endl;
}

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

bool isleap(int y) {
    return (y%4==0)&&((y%100!=0)||(y%400==0));
}

int dc(int y,int m,int d) {
    int res = 0;
    for(int i=1; i<y; ++i) {
        res += 365;
        if(isleap(i)) res++;
    }

    for(int i=1; i<m; ++i) {
        res += 31;
        if(i == 4 || i == 6 || i == 9 || i == 11) res--;
        if(i == 2) {
            res -= 3;
            if(isleap(y)) res++;
        }
    }
    res += d-1;
    return res;
}

int main() {
    int y1,y2,m1,m2,d1,d2;
    while(cin>>y1>>m1>>d1>>y2>>m2>>d2) {
        if(y1 == -1 && y2 == -1) break;

        else cout<<dc(y2,m2,d2)-dc(y1,m1,d1)<<endl;
    }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define MAX 100000
const long long INF=1145141919,MOD=1e9+7;
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

int main(){
    int n;
    cin>>n;
    long long a[n]={};
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n-1;i++){
        long long x=a[i],y=a[i+1],z;
        if(x<y){
            z=x;
            x=y;
            y=z;
        }
        while((z=x%y)!=0){
            x=y;
            y=z;
        }
        a[i+1]=y;
    }
    cout<<a[n-1]<<endl;

    return 0;
}


Measured memory_bytes: 1024
from collections import deque

n, m = map(int, input().split())
info = [[] for _ in range(n)]
visited = [0] * n
dist = [0] * n
ans = 'Yes'
for i in range(m):
    l, r, D = map(int, input().split())
    info[l-1].append([r-1, D])
    info[r-1].append([l-1, -D])

for i in range(n):
    if visited[i]:
        continue
    q = deque()
    q.append(i)
    while q:
        p = q.pop()
        for x, d in info[p]:
            if visited[x] == 0:
                visited[x] = 1
                dist[x] = dist[p] + d
                q.append(x)
            elif dist[x] != dist[p] + d:
                ans = 'No'

print(ans)

Measured memory_bytes: 80052
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ALL(a)  (a).begin(),(a).end()
 
const ll mod = 1000000007;
const ll LINF = 1e13;
const ll LLINF = 1e18;
const ll ALPHABET = 26;
 
template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}
 
template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x; //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいい
  return is;
}


int main(){
    // ll N,S,K;
    // ll a,b,c;

    ll n;
    cin >> n;
    string s;
    string t;
    cin >> s;
    cin >> t;

    string ans = "";

    for (ll i = 0; i < n; i++)
    {
      ans+=s[i];
      ans+=t[i];
          }
    
    

  cout << ans;

}


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

using namespace std;

#define int long long

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

typedef vector<int> VI;
typedef pair<int, int> PII;

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

int ans = 0;

signed main(){

    int N;
    cin >> N;

    int prev = -1;
    bool ok = true;

    REP(i, N){
        int y;
        cin >> y;
        if(prev <= y){
            ans++;
            prev = y;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <typeinfo>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int dp[100][10];

int main()
{
    ll k, tmp_k;
    bool flag = false;

    cin >> k;

    rep(i, 100)
    {
        rep(j, 10)
        {
            if (i == 0)
            {
                dp[i][j] = 1;
            }
            else
            {
                dp[i][j] = (j == 0 ? 0 : dp[i - 1][j - 1]) + dp[i - 1][j] + (j == 9 ? 0 : dp[i - 1][j + 1]);
            }
            if (j != 0 && dp[i][j] >= k)
            {
                cout << j;
                i--;
                while (i >= 0)
                {
                    if (j != 0)
                    {
                        if (dp[i][j - 1] >= k)
                        {
                            j = j - 1;
                            i--;
                            cout << j;
                            continue;
                        }
                        else
                        {
                            k -= dp[i][j - 1];
                        }
                    }

                    if (dp[i][j] >= k)
                    {
                        i--;
                        cout << j;
                        continue;
                    }
                    else
                    {
                        k -= dp[i][j];
                    }

                    if (j != 9)
                    {
                        if (dp[i][j + 1] >= k)
                        {
                            j = j + 1;
                            i--;
                            cout << j;
                            continue;
                        }
                        else
                        {
                            k -= dp[i][j + 1];
                        }
                    }
                }
                cout << endl;
                flag = true;
            }
            else if (j != 0)
            {
                k -= dp[i][j];
                // cout << "(" << i << ", " << j << "): " << k << endl;
            }
            if (flag)
                break;
        }
        if (flag)
            break;
    }

    // cout << endl;
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 <string>
#include <cstring>
#include <ctime>


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x*x; }

//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 EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#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)
#define loop(n) FOR(i,0,n)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18


int main() {
	double x1, y1, x2, y2; cin >> x1>> y1>> x2>> y2;

	double dx = abs(x1 - x2);
	double dy = abs(y1 - y2);
	
	cout <<fixed<<setprecision(8)<< sqrt(dx*dx + dy*dy) << endl;

	return 0;
}


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

int main(){
    using namespace std;
    constexpr unsigned int MOD = 1000000007;
    unsigned long N, K;
    cin >> N >> K;
    vector<unsigned int> dp(K + 1);
    dp[0] = 1;
    for(unsigned long i{0}, a; i < N; ++i){
        cin >> a;
        for(unsigned long j{K}; j > a; --j)dp[j] += dp[j] > dp[j - a - 1] ? -dp[j - a - 1] : MOD - dp[j - a - 1];
    }
    for(unsigned long i{0}; i < N; ++i)partial_sum(dp.begin(), dp.end(), dp.begin(), [](auto i, auto j){return (i + j) % MOD;});
    cout << dp.back() << endl;
    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
const int N=1000005,Mod=1e9+7;
inline int qpow(int a,int b){
	int ans=1;
	while (b){
		if (b&1) ans=1ll*ans*a%Mod;
		a=1ll*a*a%Mod,b>>=1; 
	}
	return ans;
}
int fac[N],inv[N],pow3[N];
inline void init_binom(){
	fac[0]=1;for (int i=1;i<=1000000;i++) fac[i]=1ll*fac[i-1]*i%Mod;
	inv[1000000]=qpow(fac[1000000],Mod-2);
	for (int i=999999;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%Mod;
	pow3[0]=1;for (int i=1;i<=1000000;i++) pow3[i]=1ll*pow3[i-1]*3ll%Mod;
}
inline int C(int n,int m){
	return 1ll*fac[n]*inv[m]%Mod*inv[n-m]%Mod;
}
int n,m,k;
int main (){
	init_binom();
	scanf ("%d%d%d",&n,&m,&k);
	int ans=0,x=1;
	if (m<k) m^=k^=m^=k;
	for (int i=0;i<=m+k;i++) {
        ans=(ans+1ll*C(n-1+i,n-1)*pow3[m+k-i]%Mod*x%Mod)%Mod;
        if (i<k) x=x*2ll%Mod;
        else if(i>=m) x=((x*2ll%Mod-C(i,k)-C(i,i-m))%Mod+Mod)%Mod;
        else x=(x*2ll%Mod-C(i,k)+Mod)%Mod;
    }
	printf ("%d",(ans+Mod)%Mod);
	return 0;
}


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

using namespace std;
#define all(a)a.begin(),a.end()
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod = int(1e9)+7;
using V = vector<int>;
using P = pair<int,int>;

V a,b,c,d;
ll ans=0;
int n,m,q;
void dfs(V l){
    if(l.size()==n+1){
        ll now=0;
        rep(i,q){
            if(l[b[i]]-l[a[i]]==c[i])now+=d[i];
        }
        ans=max(ans,now);
        return;
    }
    l.push_back(l.back());
    while(l.back()<=m){
        dfs(l);
        l.back()++;
    }

}

int main()
{
    cin >>n>>m>>q;
    a=b=c=d=V (q);
    rep(i,q)cin >>a[i]>>b[i]>>c[i]>>d[i];
    dfs (V (1,1));
    cout << ans << endl;
    return 0;
}


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

void fnInput(vector<int> &rvnElm, vector<int> &rvnTrg)
{
  int nElmCnt, nTrgCnt;
  cin >> nElmCnt;

  rvnElm.resize(nElmCnt);
  for (int i = 0; i < nElmCnt; i++)
    cin >> rvnElm[i];

  cin >> nTrgCnt;

  rvnTrg.resize(nTrgCnt);
  for (int i = 0; i < nTrgCnt; i++)
    cin >> rvnTrg[i];
}

int fnRcsSch(int nPos, int nTrg, const vector<int> &cnrvnElm, vector<vector<int>> &rvvnDP)
{
  if (!nTrg)                    return 1;
  if (nPos == cnrvnElm.size())  return 0;
  if (nTrg < 0)                 return 0;
  if (rvvnDP[nPos][nTrg] != -1) return rvvnDP[nPos][nTrg];

  if (fnRcsSch(nPos + 1, nTrg, cnrvnElm, rvvnDP))
    return (rvvnDP[nPos][nTrg] = 1);
  else if (fnRcsSch(nPos + 1, nTrg - cnrvnElm[nPos], cnrvnElm, rvvnDP))
    return (rvvnDP[nPos][nTrg] = 1);
  else
    return (rvvnDP[nPos][nTrg] = 0);
}

void fnExhSch(const vector<int> &cnrvnElm, const vector<int> &cnrvnTrg)
{
  vector<vector<int>> vvnDP(21, vector<int>(2001, -1));
  
  for (int i = 0; i < cnrvnTrg.size(); i++)
  {
    int nTrg = cnrvnTrg[i];

    if (fnRcsSch(0, nTrg, cnrvnElm, vvnDP))
      cout << "yes" << endl;
    else
      cout << "no" << endl;
  }
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  vector<int> vnElm, vnTrg;

  fnInput(vnElm, vnTrg);
  fnExhSch(vnElm, vnTrg);

  return 0;
}

Measured memory_bytes: 3348
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
typedef pair<int,int> PI;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
 
typedef struct{
  short x,y;
  int cost;
  short ch;
}mouse;
const int MAX=(1<<14)-1;
mouse Q[MAX+1];
int s,num;

mouse t;
short cx,cy,nx,ny,ch,nch,h,w,n;
int cost;

char in[16];
int inum[3];
 
main(){
  int s=0;
  int nums=0;
  do{
    read(0,in+s,1);
    if(isdigit(in[s]))inum[nums]=inum[nums]*10+in[s]-'0';
    else nums++;
  }while(in[s++]!='\n');
  h=inum[0];
  w=inum[1];
  n=inum[2];

  short maxch[h][w];
  char ku[h][w];
  
  rep(i,h){
    read(0,ku[i],w+1);
    rep(j,w){
      if(ku[i][j]=='S')cx=i,cy=j;
      maxch[i][j]=-1;
    }
  }
 
 
  Q[s+num++]=(mouse){cx,cy,0,0};
  maxch[cx][cy]=0;
 
  while(true){
    t=Q[s++&MAX];
    num--;
    cx=t.x,cy=t.y,cost=t.cost;
    ch=t.ch;
 
    rep(i,4){
      nx=cx+dx[i],ny=cy+dy[i];
      if(nx<0 || nx>=h || ny<0 || ny>=w)continue;
      if(ku[nx][ny]=='X')continue;
      nch=ch;
      if(ku[nx][ny]<='9' && ku[nx][ny]>='1' && ku[nx][ny]-'0'==t.ch+1){
        nch=ch+1;
      }
 
      if(maxch[nx][ny]>=nch)continue;
      if(nch==n){
        printf("%d\n",cost+1);
        return 0;
      }
      maxch[nx][ny]=nch;
      Q[s+num++&MAX]=(mouse){nx,ny,cost+1,nch};
    }
  }
}

Measured memory_bytes: 3876
#include <stdio.h>
#include <string.h>

int main()
{int a,d,s=0;
  scanf("%d",&a);
  while( a>=5){
  if(a>=500){

    d=a/500;
    s=s+d*1000;
     a=a%500;


  }
  else if(a>=5){

    d=a/5;
    s=s+d*5;
  a=a%5;
  }

  }
  printf("%d",s);

}


Measured memory_bytes: 128
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

sx,sy,tx,ty = inm()
p = 'L'
p += 'U'*(ty+1-sy)
p += 'R'*(tx+1-sx)
p += 'D'
p += 'L'*(tx-sx)
p += 'D'*(ty-sy)
p += 'R'*(tx-sx)
p += 'U'*(ty-sy)
p += 'R'
p += 'D'*(ty+1-sy)
p += 'L'*(tx+1-sx)
p += 'U'
print(p)



Measured memory_bytes: 62120
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i=0;i<n;i++)
#define REP(i,n) for (int i=1;i<=n;i++)
#define print(x) cout << x << endl;
typedef long long ll;

int gcd(int x, int y) {
	if (x < y) {
		swap(x, y);
	}
	int r = x % y;
	while (r != 0) {
		x = y;
		y = r;
		r = x % y;
	}
	return y;
}

int main() {
	int n, m, k; cin >> n >> m >> k;
	int t = gcd(n, m);
	int now = 0;
	for (int i = t; i > 0; i--) {
		if (t % i == 0) {
			now++;
		}
		if (now == k) {
			cout << i << endl;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 256
n = int(input())
b = list(map(int,input().split()))
a = []
c = 0

a.append(b[0])

for i in range(n-2):
    if n == 2:
        a.append(b[i])
        break
    c = min(b[i],b[i+1])
    a.append(c)

a.append(b[n-2])
print(sum(a))

Measured memory_bytes: 38384
/// {{{
#include "bits/stdc++.h"
#define   ALL(x)  x.begin(), x.end()
#define   iostreamBooster()  do{cin.tie(nullptr);ios::sync_with_stdio(false);}while(0)
using namespace std;
typedef long long i64;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
// }}}


template<class Abel> struct UnionFind {
  vector<int> par;
  vector<int> rank;
  vector<Abel> diff_weight;

  UnionFind(int n = 1, Abel SUM_UNITY = 0) {
    init(n, SUM_UNITY);
  }

  void init(int n = 1, Abel SUM_UNITY = 0) {
    par.resize(n); rank.resize(n); diff_weight.resize(n);
    for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
  }

  int root(int x) {
    if (par[x] == x) {
      return x;
    }
    else {
      int r = root(par[x]);
      diff_weight[x] += diff_weight[par[x]];
      return par[x] = r;
    }
  }

  Abel weight(int x) {
    root(x);
    return diff_weight[x];
  }

  bool issame(int x, int y) {
    return root(x) == root(y);
  }

  bool merge(int x, int y, Abel w) {
    w += weight(x); w -= weight(y);
    x = root(x); y = root(y);
    if (x == y) return false;
    if (rank[x] < rank[y]) swap(x, y), w = -w;
    if (rank[x] == rank[y]) ++rank[x];
    par[y] = x;
    diff_weight[y] = w;
    return true;
  }

  Abel diff(int x, int y) {
    return weight(y) - weight(x);
  }
};

signed main()
{
  iostreamBooster();

  int N, M;
  cin >> N >> M;

  UnionFind<i64> uf(N+5);

  bool ok = true;
  for (int i = 0; i < M; ++i) {
    i64 l, r, d;
    cin >> l >> r >> d;

    if (uf.issame(l, r)) {
      if (uf.diff(l, r) != d) {
        ok = false;
      }
    }
    else {
      uf.merge(l, r, d);
    }
  }

  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}



Measured memory_bytes: 1792
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int main(){
  int n;
  string s;
  cin>>n>>s;
  int count=0;
  for(int i=0;i<=n-3;i++){
    if(s.substr(i,3)=="ABC")count++;
  }
  cout<<count;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define Int int64_t
#define dump(x) cout << (x) << endl
#define fi first
#define se second
Int mod = 1e9+7;
Int INF = 1e18;
double EPS = 0.00000001;
//Int mod = 998244353;

int main() {
    Int n, d;
    cin >> n >> d;
    d *= 2;
    d++;
    Int res = n / d;
    if (n % d != 0) res++;
    dump(res);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define FOR(i, a, b) for (int i = a; i <= (int)(b); i++)
#define FORD(i, a, b) for (int i = a; i >= (int)(b); i--)
 
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using Lint = long long;
#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法
 
#define ALL(x) (x).begin(), (x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
 
#define PB push_back
#define MP make_pair
using P=pair<int, int>;
using V=vector<double>;
using M=map<int, int>;
using S=set<int>;
#include <math.h>
#define COUT(x) cout << (x) << endl
#define SCOUT(x) cout << (x) << " "
 
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
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;}
/* vector<T>のイテレータはvector<T>::iterator型
vector<int>::iterator it = vc.begin();  // begin()はvectorの最初の要素を指すイテレータを返す
vector<int>::iterator endIt = vc.end(); // end()はvectorの終端位置を指すイテレータを返す
while (it != endIt)
{
  cout << *it << '\n'; // イテレータの指す要素は、ポインタのように*演算子でアクセス
  it++;                // インクリメントすることで次の要素を指します。
}
}*/
int main(){
int n;
cin >> n;
  if(n>=30)COUT("Yes");
  else COUT("No");
  
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)

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

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//素因数分解
vector<pair<ll, int>>factorize(ll n) {
	vector<pair<ll, int>>res;
	for (ll i = 2;i * i <= n;++i) {
		if (n % i)continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1)res.emplace_back(n, 1);
	return res;
}

int bingo[3][3];
bool flag[3][3];
int cnt[2][105];
int h, w;
int choco[1010][1010];
int s[11][11];

int main() {
	ll x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;
	vector<ll>p(a), q(b), r(c);
	rep(i, a) {
		cin >> p[i];
	}
	rep(i, b) {
		cin >> q[i];
	}
	rep(i, c) {
		cin >> r[i];
	}
	sort(p.begin(), p.end(), greater<ll>());
	sort(q.begin(), q.end(), greater<ll>());
	sort(r.begin(), r.end(), greater<ll>());
	vector<ll>d;
	rep(i, x)d.push_back(p[i]);
	rep(i, y)d.push_back(q[i]);
	rep(i, c)d.push_back(r[i]);
	sort(d.rbegin(), d.rend());
	ll ans = 0;
	rep(i, x + y)ans += d[i];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 8688
N, M = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)

total = A.inject(:+)
low = total / (4 * M).to_f

ret = 'Yes'
sort = A.sort.reverse
M.times do |m|
  if sort[m] < low
    ret = 'No'
    break
  end
end

puts ret

Measured memory_bytes: 1788
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
cnt = 0
for a, b in zip(A, B):
    if a > b:
        cnt -= a - b
    if a < b:
        cnt += (b - a) // 2

if cnt < 0:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 4596
#include <iostream>
 
int main()
{
    int a, b;
  
  
	std::cin >> a >> b;
 
   
    if (a > b) {
      std::cout << 2 * a - 1 << std::endl;
    } else if (a == b) {
      std::cout << 2 * a << std::endl;
    } else {
      std::cout << 2 * b - 1 << std::endl;
    }
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		String s = fs.next();
		
		int left = 0;
		int right = s.length()-1;
		
		int ans = 0;
		while(left < right) {
			if(s.charAt(left) != s.charAt(right)) {
				ans++;
			}
			left++;
			right--;
		}
		System.out.println(ans);
	}

	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}


}


Measured memory_bytes: 23124
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7; 
bool comp(ll a, ll b){
  return a>b;
}
ll calcFinal(vector<ll> &v){
    ll res = 1;
    for(ll i : v) {
        if(i<0) res *= MOD+i;
        else res *= i;
        res %= MOD;
    }
    return res;
}
int main(){
    if (fopen("input.in", "r")) 
        freopen("input.in", "r", stdin), freopen("output.out", "w", stdout);
  int N,K;
  cin>>N>>K;
  vector<ll> pos;
  vector<ll> neg;
  for(int i=0;i<N;i++){
    ll x;
    cin>>x;
    if(x<0){
      neg.push_back(x);
    }else{
      pos.push_back(x);
    }
  }
  sort(pos.begin(),pos.end(),comp);
  sort(neg.begin(),neg.end());
  ll negindex=0;
  ll posindex=0;
  int negnum=0;
  vector<ll> v;
  ll final = 1;
  if(pos.size()==0 && K%2==1){
    sort(neg.begin(),neg.end(),comp);
    for(int i=0;i<K;i++){
      final=(final*(1000000007+neg[i]))%1000000007;
    }
    cout<<final<<endl;
    return 0;
  }
  for(int i=0;i<K;i++){
    if(posindex==pos.size() ||(negindex<neg.size() &&neg[negindex]*-1>pos[posindex])){
      v.push_back(neg[negindex]);
      negindex++;
      negnum++;
    }else{
      v.push_back(pos[posindex]);
      posindex++;
    }
  }

  int counter;
  if(K!=N && negnum%2==1){
    ll add1 = -1, rem1;
    ll add2 = -1, rem2;
    if(posindex!=0 &&negindex != neg.size()){
        counter=K-1;
        while(v[counter]<0){
            counter--;
        }
        add1 = negindex;
        rem1 = counter;
    }
    if(negindex!=0 && posindex!= pos.size()){
        counter=K-1;
        while(v[counter]>=0){
            counter--;
        }
        add2 = posindex;
        rem2 = counter;
    }
    if(add2 == -1 || (add1 != -1 && v[rem1] * pos[add2] < v[rem2] * neg[add1])){
        v[rem1] = neg[add1];
    } else {
        v[rem2] = pos[add2];
    }
  } 
  final = calcFinal(v);
  cout<<final<<endl;
}

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

int main()
{
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    int pa = 0, pb = 0;
    ll value = 0;
    while (pa < X || pb < Y)
    {
        if (pb >= Y)
        {
            value += min(A, 2 * C);
            pa++;
        }
        else if (pa >= X)
        {
            value += min(B, 2 * C);
            pb++;
        }
        else
        {
            value += min(A + B, 2 * C);
            pa++;
            pb++;
        }
    }
    cout << value << endl;
    return 0;
}

Measured memory_bytes: 3572
n = int(input())
num_list = list(map(int, input().split()))

ans = 1

for e in num_list:
    if e == 0:
        ans = 0

for e in num_list:
    ans *= e
    if ans > 1000000000000000000:
        ans = -1
        break
    if ans == 0:
        break

print(ans)


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

int mod = 1e9 + 7;

signed main(){
  
  int n, k, zero = 0;
  vector<int> A, B;
  
  cin >> n >> k;
  
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    if( a == 0 ) zero++;
    if( 0 < a ) A.push_back( a );
    if( a < 0 ) B.push_back( -a );
  }
  
  sort( A.begin(), A.end(), greater<int>() );
  sort( B.begin(), B.end(), greater<int>() );
  
  // pattern 1
  if( n - k < zero ){
    cout << 0 << endl;
    return 0;
  }
  
  // pattern 2
  int mul = 1, cnt = k;
  int idxA = 0, idxB = 0;
  
  while( cnt ){

    int Acnt = (int)A.size() - idxA;      
    int Bcnt = (int)B.size() - idxB;
    
    if( cnt % 2 ){
      
      if( Acnt ){
	mul = mul * A[idxA++] % mod;
	cnt--;
      }
      else break;
      
    }
    else{
      
      if( 2 <= Acnt && 2 <= Bcnt ){
	
	if( A[idxA] * A[idxA+1] < B[idxB] * B[idxB+1] ){
	  mul = mul * B[idxB++] % mod;
	  mul = mul * B[idxB++] % mod;
	  cnt -= 2;
	}
	else{
	  mul = mul * A[idxA++] % mod;
	  mul = mul * A[idxA++] % mod;
	  cnt -= 2;
	}
	
      }
      else if( 2 <= Acnt ){
	mul = mul * A[idxA++] % mod;
	mul = mul * A[idxA++] % mod;
	cnt -= 2;
      }
      else if( 2 <= Bcnt ){
	mul = mul * B[idxB++] % mod;
	mul = mul * B[idxB++] % mod;
	cnt -= 2;
      }
      else break;
    }
    
  }
  
  if( cnt == 0 ){
    cout << mul << endl;
    return 0;
  }
  else if( zero ){
    cout << 0 << endl;
    return 0;
  }
  
  // pattern 3

  sort( B.begin(), B.end() );
  
  if( n == k ){
    
    mul = 1;
    
    for(int a : A ) mul = mul * a % mod;
    for(int b : B ) mul = mul * b % mod;
    
    cout << mod - mul << endl;
    
  }
  else{
    
    mul = 1;

    for(int i=0;i<k;i++) mul = mul * B[i] % mod;
    
    cout << mod - mul << endl;
      
  }
  
  return 0;
}


Measured memory_bytes: 5468
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Watch {
    Integer seconds;
    
    public Watch(Integer seconds) {
        this.seconds = seconds;
    }
    
    public Integer getHours() {
        return  seconds/60/60;
    }
    public Integer getMinutes() {
        return  (seconds/60)%60;
    }
    public Integer getSeconds() {
        return  seconds%60;
    }
}

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String inputLine = reader.readLine();
        String[] splitStrings = inputLine.split("\\s");
        
        if(splitStrings.length != 1) {
            throw new Exception("invalid input");
        }
        
        Watch watch = new Watch(Integer.parseInt(splitStrings[0]));
        System.out.printf("%d:%d:%d\n", watch.getHours(), watch.getMinutes(), watch.getSeconds());
    }
}


Measured memory_bytes: 24696
n=int(input())
s=list(input())
ma=0
for i in range(n):
  c=[]
  count=0
  a=s[:i+1]
  b=s[i+1:]
  for j in range(len(a)):
    if a[j] not in c:
      if a[j] in b:
        c.append(a[j])
        count+=1
    if count>ma:
      ma=count
print(ma)

Measured memory_bytes: 9196
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define INF INT_MAX
int dp[1001][1001];
int main(void)
{
	int n,m;
	int d[1001];
	int c[1001];
	int i,j,k;
	cin>>n>>m;
	for(i=0;i<n;i++) cin>>d[i];
	for(i=0;i<m;i++) cin>>c[i];
	for(i=0;i<=m;i++){
		for(j=0;j<=n;j++) dp[i][j]=INF;
	}
	dp[0][0]=0;
	for(i=0;i<m;i++){
		for(j=0;j<=n;j++){
			if(dp[i][j]!=INF){
				if(dp[i+1][j+1]==INF||dp[i+1][j+1]>dp[i][j]+c[i]*d[j]) dp[i+1][j+1]=dp[i][j]+c[i]*d[j];
				if(dp[i+1][j]==INF||dp[i+1][j]>dp[i][j]) dp[i+1][j]=dp[i][j];
			}
		}
/*
		for(j=0;j<=m;j++){
			for(k=0;k<=n;k++){
				cout<<dp[j][k]<<" ";
			}
			cout<<endl;
		}
		cout<<endl;
		for(j=0;j<200000000;j++);
*/
	}
	cout<<dp[m][n]<<endl;
	return 0;
}


Measured memory_bytes: 6980
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

#define X first
#define Y second
#define N 300000
#define M 300000

typedef long long ll;
const int INF=1<<30;

int a[N];

int main()
{
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	
	int n;  ll ans=0;
	scanf("%d",&n);
	for (int i=1;i<=3*n;i++) scanf("%d",&a[i]);
	sort(a+1,a+3*n+1);
	int j=3*n;
	for (int i=1;i<=n;i++)
	{

		ans+=a[j-1]; j-=2;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define MOD 1000000007
#define MOD2 1000000006
#define TEMPMOD1 998244353
#define TEMPMOD2 998244352
#define INF 1000000000000000007
#define NEGINF -1000000000000000007
#define vll vector<ll> 
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define plll pair<ll,pll>
#define vpll vector<pll>
using namespace std;
typedef long long int ll;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    ll n;
    cin>>n;
    ll arr1[n+1];
    for(ll i=1;i<=n;i++)
    {
        cin>>arr1[i];
    }
    ll prefix[n+1][21];
    for(ll i=0;i<21;i++)
    {
        prefix[0][i]=0;
    }
    for(ll i=1;i<=n;i++)
    {
        for(ll j=0;j<21;j++)
        {
            prefix[i][j]=prefix[i-1][j];
            if((arr1[i]>>j)&1)
            {
                prefix[i][j]++;
            }
        }      
    }
    ll low,high,mid,ans1;
    ll result=0;
    for(ll i=1;i<=n;i++)
    {
        low=i;
        high=n;
        while(low<=high)
        {
            mid=(low+high)/2;
            bool check1=true;
            for(ll j=0;j<21;j++)
            {
                if(prefix[mid][j]>(prefix[i-1][j]+1))
                {
                    check1=false;
                    break;
                }

            }    
            if(check1)
            {
                ans1=mid;
                low=mid+1;
            }
            else
            {
                high=mid-1;
            }
        }
        result+=(ans1+1)-i;
    }
    cout<<result;
    return 0;
}

Measured memory_bytes: 34688
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define all(x)              (x).begin(), (x).end()
#define inf                 1e18

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	ifstream cin("input.txt");
//	ofstream cout("output.txt");
	ll k;
	string s;
	cin >> s >> k;
	int n = s.size();
	vector < vector < vector <ll> > > dp(n + 1, vector < vector <ll> > (k + 100, vector <ll> (2)));
	dp[0][0][1] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= k; ++j) {
			for (int z = 0; z < 2; ++z) {
				for (int d = 0; d <= 9; ++d) {
					if (j + (d != 0) > k) {
						continue;
					}
					if (j > i || (d > s[i] - '0' && z == 1)) {
						continue;
					}
					dp[i + 1][j + (d != 0)][z & (d == s[i] - '0')] += dp[i][j][z];
				}
			}
		}
	}
	cout << dp[n][k][1] + dp[n][k][0];
}

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

int main(){
  int a,b;//整数a,bの入力
  double x;
  cin >> a >> b;
  x=(a+b)/2;
    if((a+b)%2!= 0)
    {
      x+=1;
    }
  else{}
  cout << x << endl;
}

Measured memory_bytes: 256
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

	public void Proc()
	{
        int[] tmp = Reader.ReadLine().Split(' ').Select(a => int.Parse(a) - 1).ToArray();
        int an = tmp[0] * tmp[1];
        Console.WriteLine(an);
    
    }



    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"



2 2


";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}


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

#define x first
#define y second
#define int64 long long
#define MaxN 2000
#define MOD 998244353

int spec[MaxN+1][MaxN+1];
int dp[MaxN+1][MaxN+1];
int coef[2*MaxN+1];
int res[2*MaxN+1];
int sum[MaxN+1];
int N, K;

void Precalc()
{
    int i, j;

    for(i = 2; i <= 2 * K; ++i)
        for(j = 1; j < (i + 1) / 2; ++j)
        if(i - j <= K) ++coef[i];

    for(i = 0; i <= K; ++i) spec[0][i] = 1;
    for(i = 1; i <= N; ++i)
        for(j = 1; j <= K; ++j)
        spec[i][j] = (spec[i-1][j] + spec[i][j-1]) % MOD;

    for(i = 0; i <= K; ++i) dp[i][0] = 1;
    for(i = 1; i <= N; ++i) dp[1][i] = 2;
    for(j = 2; j <= K; ++j)
    {
        dp[j][1] = 2 * j;
        sum[0] = dp[j][0];
        for(i = 1; i <= N; ++i) sum[i] = (sum[i-1] + dp[j-1][i]) % MOD;
        for(i = 2; i <= N; ++i) dp[j][i] = (2LL * sum[i-1] + dp[j-1][i]) % MOD;
    }
}

int main(){

    int i, j;

    scanf("%d %d", &K, &N);
    Precalc();


    for(i = 2; i <= 2 * K; ++i)
    {
        for(j = 0; j <= N; ++j)
        res[i] = (res[i] + 1LL * dp[ coef[i] ][j] * spec[N - j][ K - 2 * coef[i] - (i % 2 == 0) ]) % MOD;

        if(i % 2) continue;
        for(j = 0; j < N; ++j)
        res[i] = (res[i] + 1LL * dp[ coef[i] ][j] * spec[N - j - 1][ K - 2 * coef[i] - (i % 2 == 0) ]) % MOD;
    }

    for(i = 2; i <= 2 * K; ++i) printf("%d\n", res[i]);


return 0;
}


Measured memory_bytes: 31616
n = int(input())

dp = [10 ** 5]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    dp[i] = dp[i-1] + 1
    k = 6
    while i-k >= 0:
        dp[i] = min(dp[i], dp[i-k]+1)
        k *= 6
    k = 9
    while i-k >= 0:
        dp[i] = min(dp[i], dp[i-k]+1)
        k *= 9
print(dp[n])

Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define dl double long
const int INF=0x3fffffff;
const ll MOD=1000000007;
const ll MODD=998244353;
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
template <int MOD>
struct ModInt {
    using lint = long long;
    int val;
 
    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };
 
    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt inv() const { return this->pow(MOD - 2); }
 
    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
    ModInt pow(lint n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }
 
    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }
 
    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }
 
    // I/O
    friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept { return is >> x.val; }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

int main() {
  	ll N, ans=0;
    cin >> N;
  	vector<ll> p(N);
  	rep(i, N) cin >> p[i];
	rep(i, N-2){
    	if(p[i] < p[i+1] && p[i+1] < p[i+2] ||
           p[i+2] < p[i+1] && p[i+1] < p[i]){
          ++ans;
        }
    }
    cout << ans << "\n";
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cassert>
#include<numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
const int INF = 1001001001;
const long long LINF = 1001002003004005006ll;
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; }
typedef long long ll;
typedef pair<int,int> P;

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

struct Data {
  int x,y,v;
  Data(int x, int y, int v):x(x),y(y),v(v) {}
};

int main(){
    int h,w;
    cin >> h >> w;
    int si,sj,fi,fj;
    cin >> si >> sj >> fi >> fj;
    si--,sj--,fi--,fj--;
    vector<vector<int>> f(h,vector<int>(w,INF));
    vector<string> s(h);
    rep(i,h)cin >> s[i];
    deque<Data> dq;
    vector<vector<int>> d(h,vector<int>(w,INF));
    d[si][sj]=0;
    dq.push_back(Data(si,sj,0));
    while(!dq.empty()){
        int i = dq.front().x;
        int j = dq.front().y;
        int v = dq.front().v;
        dq.pop_front();
        if(d[i][j]!=v)continue;
        for(int _=0;_<4;_++){
            int ni=i+dx[_],nj=j+dy[_];
            if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
            if (s[ni][nj] == '#') continue;
            if (d[ni][nj] <= v) continue;
            dq.push_front(Data(ni,nj,v));
            d[ni][nj]=d[i][j];
        }
        for(int ei=-2;ei<=2;ei++){
            for(int ej=-2;ej<=2;ej++){
                int ni=i+ei,nj=j+ej;
                if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
                if (s[ni][nj] == '#') continue;
                if (d[ni][nj] <= v+1) continue;
                dq.push_back(Data(ni,nj,v+1));
                d[ni][nj]=d[i][j]+1;
            }
        }
    }
    int ans = d[fi][fj];
    if (ans == INF) ans = -1;
    cout << ans << endl;
}

Measured memory_bytes: 13512
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define ll int
#define bits_count __builtin_popcountll
#define endl '\n'
#define double long double
#define ld double
#define FOR(i,a,n) for (ll i=(a);i<=(n);++i)
#define RFOR(i,a,n) for (ll i=(n);i>=(a);--i)
#define FI(i,n) for (ll i=0; i<(n); ++i)
#define ZERO(a) memset((a),0,sizeof((a)))
#define MINUS(a) memset((a),-1,sizeof((a)))
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define all(g) g.begin(),g.end()
#define sz(x) (ll)x.size()
#define pr pair<int,int>
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int MAXN = 1e5 + 10;
int a[MAXN];
int fact[MAXN];
const int MOD = 1e9 + 7;

int power(int x,int y){
    int res = 1;
    while(y){
        if(y&1) res = (res*x)%MOD;
        x = (x*x)%MOD; y >>= 1;
    }
    return res;
}

int invmod(int x){ return power(x,MOD-2); }

int nCr(int n,int r){
    int ret = fact[n];
    ret = (ret*invmod(fact[r]))%MOD;
    ret = (ret*invmod(fact[n-r]))%MOD;
    return ret;
}

void solve(){
    fact[0] = 1;
    FOR(i,1,MAXN-1) fact[i] = (fact[i-1]*i)%MOD;

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

    FOR(i,1,n) cin>>a[i];

    int ans = 0;

    sort(a+1,a+n+1);

    FOR(i,k,n){
        int temp = (a[i]*nCr(i-1,k-1))%MOD;
        ans = (ans + temp)%MOD;
    }

    FOR(i,1,n-k+1){
        int temp = (a[i]*nCr(n-i,k-1))%MOD;
        ans = (ans - temp)%MOD;   
        ans = (ans + MOD)%MOD; 
    }
    cout<<ans<<endl;
}

signed main(){

   FastRead;    


    int t = 1; 
    // cin>>t; 
    FOR(i,1,t){
        // cout<<"Case #"<<i<<": ";
        solve();
    }
}

Measured memory_bytes: 1792