akhauriyash/Code-Regression huggingface dataset:
/** "Ever tried.
         Ever failed.
               No matter.
                   Try Again.
                        Fail again.
                             Fail better.**/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define bp  __builtin_popcount
#define pb push_back
#define loop(i,n) for(int i = 0;i < int(n);i++)
#define sz(s) (int)(s.size())
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define setdp memset(dp,-1,sizeof(dp))
#define db(x) cout<<" LOOK "<<(#x)<<" = "<<x <<'\n'
#define NumofDigits(n)   ((long long)log10(n)+1)

using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const int maxn=1e5+5;
const  double EPS = 1e-9;
const int MOD = 1e9+7;
/*
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll fastpow(ll b, ll p)
{if(!p)return 1;ll ret = fastpow(b, p >> 1);ret *= ret;if(p&1)ret*= b;return ret;}
int dx[] = {- 1, 0, 0, 1, 0 };
int dy[] = { 0,- 1, 1, 0, 0 };*/
inline void File()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
}
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
int n,m;
char arr[105][105];
bool valid(int i, int j)
{
    if(i>=0 && j>=0 && i<n && j<m)
        return true;
    return false;
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   // File();
    cin>>n>>m;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin>>arr[i][j];
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            int cnt=0;
            if(arr[i][j]=='#')
                continue;
            for(int d=0; d<8; d++)
            {
                int ni=i+dx[d];
                int nj=j+dy[d];
                if(valid(ni,nj))
                    if(arr[ni][nj]=='#')
                        cnt++;
            }
            arr[i][j]=char(cnt+'0');
        }
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
            cout<<arr[i][j];
        cout<<endl;
    }
}


Measured memory_bytes: 3668
#include <bits/stdc++.h>
#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)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = (1<<30)-1;
//const ll INF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
//inline int in() { int x; scanf("%d",&x); return x;}
template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int a[3][3];

int main () {
  rep(i,3)rep(j,3) cin >> a[i][j];
  int n = in();
  vi b(n);
  rep(i,n) cin >> b[i];
  
  rep(bi,n) {
    rep(i,3)rep(j,3) {
      if (a[i][j] == b[bi]) a[i][j] = 0;
    }
  }

  rep(i,3) {
    bool ok = true;
    rep(j,3) {
      if (a[i][j] != 0) ok = false;
    }
    if (ok) {
      puts("Yes");
      return 0;
    }
  }

  rep(j,3) {
    bool ok = true;
    rep(i,3) {
      if (a[i][j] != 0) ok = false;
    }
    if (ok) {
      puts("Yes");
      return 0;
    }
  }

  bool ok = true;
  rep(i,3) {
    if (a[i][i] != 0) ok = false;
  }
  if (ok) {
    puts("Yes");
    return 0;
  }

  if (a[0][2] != 0 || a[1][1] != 0 || a[2][0 != 0]) {
    puts("No");
    return 0;
  }
  puts("Yes");
  return 0;
}

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

int main(void)
{
    int n;
    int q;
    cin >> n >> q;
    string c;
    cin >> c;
    int cnt = 0;
    vector<int> ruiseki(n, 0);
    ruiseki[0] = 0;
    for (int j = 1; j < n; ++j) {
        if (c[j - 1] == 'A' && c[j] == 'C') {
           ++cnt;
        }
        ruiseki[j] = cnt;
    }
    for (int i = 0; i < q; ++i) {
        int l;
        int r;
        cin >> l >> r;
        cout << ruiseki[r - 1] - ruiseki[l - 1] << endl;
    }
    return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N;
	int ans = 0;
	vector<int> A, B, C;
	
	cin>>N;
	A.resize(N);
	B.resize(N);
	C.resize(N);
	
	for(int i =0; i < N; i++){
		cin>>A[i];
	}
	for(int i =0; i < N; i++){
		cin>>B[i];
	}
	for(int i = 1; i < N; i++){
		cin>>C[i];
	}
	
	for(int i = 0; i < N; i++){
		ans += B[A[i]-1];
		if(i){
			if(A[i] == A[i-1]+1){
				ans += C[A[i-1]];
			}
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define Nmax 200010
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
 
int main() {
	int A,B;
	cin >> A >> B;
  	int ans=0;
  	if(B==100) B++;
  	ans=pow(100,A)*B;
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
def LI():return map(int,input().split())
while(True):
    n,l=LI()
    if n==0 and l==0:
        break
    cnt=0
    for i in range(1,n-1):
        for j in range(i+1,n):
            for k in range(j+1,n+1):
                if i+j+k==l:
                    cnt+=1
    print(cnt)


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

using ll = long long;
const int MAXN  = 2e5+10;
const int MAXM  = 1e5+10;

int N, M;

struct edge {
    int to, w;
};
vector<edge> G[MAXN];
int in[MAXN];
int d[MAXN];

void add(int u, int v, int w) {
    G[u].push_back({v, w});
}

int dp[MAXN];
int dfs(int s) {
    if(dp[s]) return dp[s];
    for(auto e : G[s]) {
        dp[s] = max(dp[s], dfs(e.to) + 1); 
    }
    return dp[s];
}
void solve() {
    int ans = 0;
    for(int v=1; v<=N; v++) {
        if(in[v] == 0){
            dp[v] = 0;
            ans = max(ans, dfs(v));
        } 
    }
    cout << ans << endl;
}

int main() {
    cin >> N >> M;
    int a, b;
    for(int i=1; i<=M; i++) {
        cin >> a >> b;
        in[b]++;
        add(a, b, 1);
    }
    /*
    // TLE
    int ans = 0;
    for(int i=1; i<=N; i++) {
        if(in[i] == 0) {
            d[i] = 0;
            ans = max(ans, bfs(i));
        }
    }
    cout << ans << endl;
    */
    
    /*
    // bfs
    queue<int> que;
    for(int i=1; i<=N; i++) {
        if(in[i] == 0) {
            d[i] = 0;
            que.push(i);
        }
    }
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = 0; i<G[u].size(); i++) {
            int v = G[u][i].to;
            --in[v];
            if(in[v]==0) {
                if(d[v] < d[u]+1) {
                    d[v] = d[u] + 1;
                }
                que.push(v);
            }
        }
    }

    int ans = 0;
    for(int i=1; i<=N; i++) {
        ans = max(ans, d[i]);
    }    
    cout << ans << endl;
    */
   // dfs
   solve();

    return 0;
}

Measured memory_bytes: 12288
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,w[N],b[N],x;
int dp[N][N],cw[N][N],cb[N][N];
int main()
{
    ios::sync_with_stdio(0);
	memset(cw,0,sizeof(cw));
	memset(cb,0,sizeof(cb));
	cin>>n;
	for(int i=1;i<=2*n;i++)
	{
		char op[2];
		cin>>op>>x;
		if(op[0]=='W')
			w[x]=i;
		else
			b[x]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)
			if(w[i]<w[j])
				cw[i][0]++;
		for(int j=1;j<=n;j++)
		{
			cw[i][j]=cw[i][j-1];
			if(w[i]<b[j])
				cw[i][j]++;	
		}
	}	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)	
			if(b[i]<b[j])
				cb[0][i]++;
		for(int j=1;j<=n;j++)
		{
			cb[j][i]=cb[j-1][i];
			if(b[i]<w[j])
				cb[j][i]++;
		}
	}
	int c1=0,c2=0;
	for(int i=1;i<=n;i++)
	{
		c1+=cw[i][0],c2+=cb[0][i];
		dp[i][0]=c1,dp[0][i]=c2;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dp[i][j]=min(dp[i-1][j]+cw[i][j],dp[i][j-1]+cb[i][j]);	
	cout<<dp[n][n];
	return 0;
}

Measured memory_bytes: 47360
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <map>
using namespace std;

int V, E, R, S[500010], T[500010], D[500010];
priority_queue< pair<int ,int>, vector< pair<int, int> >, greater< pair<int, int> > > W;
int C[100010];
const int Inf = 10000*100000+100;

int main() {
  cin >> V >> E >> R;
  for (int i=0; i<E; ++i) {
    cin >> S[i] >> T[i] >> D[i];
  }

  vector< vector<int> > edges(V);
  for (int i=0; i<E; ++i) {
    edges[S[i]].push_back(i);
  }

  for (int i=0; i<V; ++i) {
    C[i] = Inf;
  }
  C[R] = 0;
  for (int i=0; i<V; ++i) {
    W.push(make_pair(C[i], i));
  }

  unordered_set<int> q, doubled;
  for (int i=0; i<V; ++i)
    q.insert(i);

  while (!q.empty()) {
    int u = W.top().second;
    W.pop();
    if (doubled.find(u) != doubled.end())
      continue;
    doubled.insert(u);
    q.erase(u);
    for (const auto& e : edges[u]) {
      int v = T[e];
      if (C[u] + D[e] < C[v] && q.find(v) != q.end()) {
        C[v] = C[u] + D[e];
        W.push(make_pair(C[v], v));
      }
    }
  }

  for (int t=0; t<V; ++t) {
    if (C[t] == Inf)
      cout << "INF" << endl;
    else
      cout << C[t] << endl;
  }
}

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

count = 0

divide_two_num = []
for i in A:
    n = 0
    while i > 1:
        if i % 2 == 0:
            i //= 2
            n += 1
        else:
            break
    divide_two_num += [n]

print(min(divide_two_num))

Measured memory_bytes: 3060
import java.util.*;
public class Main{
	static long NumOfDiv(long n, long p){
		if(n<0)return 0;
      	else return n/p + 1;
	}

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long x = sc.nextLong();
		System.out.println(NumOfDiv(b, x)-NumOfDiv(a-1, x));
	}
}

Measured memory_bytes: 23508
n = int(input())
c = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7
ans = 0
for i,x in enumerate(c):
    ans += x * (n - i + 1)
    ans %= mod

ans *= pow(2,2*n-2,mod)

ans %= mod

print(ans)


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

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, N) FOR(i, 0, N)
#define RREP(i, N) RFOR(i, N, 0)
#define FILL(A,value) memset(A,value,sizeof(A))
#define endl '\n'

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pb push_back
#define mp make_pair
#define Pi 3.14159265358979
#define A first
#define B second

typedef long long ll;
typedef vector <int> vi;
typedef vector<ll> vl;
typedef pair <int, int> pi;
typedef pair <ll, int> pl;
typedef pair <ll, ll> pll;
typedef pair <double, double> pd;

//change these according to prob constraints
const int INF = 0x3f3f3f3f;
const int MAX = 100005;
const int MAX1 = 1005;
const int MAX2 = 105;
const int LEN = 105;
const int BASE = 1000000000;
const double EPS = 1e-7;
const int MOD = 1000000007;
//g++ -std=c++11 your_file.cpp -o your_program

ll mypow(ll a, ll b){
	ll ans=1;
	while(b){
		if(b&1)
			ans=(ans*a)%MOD;
		b/=2;
		a=(a*a)%MOD;
	}
	return ans;
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ifstream in("");
	ofstream out("");
	clock_t begin = clock();
	ll n;
  	cin >> n;
  	for (ll i = sqrt(n); i >= 1; i--){
      if (n % i == 0) {
        cout << (i + (n / i)) - 2 << endl;
        return 0;
      }
    }
	clock_t end = clock();
    double esecs = double(end - begin) / CLOCKS_PER_SEC;
    //cout << esecs << " seconds" << endl;
	return 0;	
}

Measured memory_bytes: 256
N = int(input())
S = list(input())

# 左から
l = 0
li = 0
lmax = -(10**8)
for i in range(N):
    if S[i] == 'W':
        l -= 1
    else:
        l += 1
    if l > lmax:
      lmax = l
      li = i

lans = 0
for i in range(N):
    if i < li:
        if S[i] == 'W':
            lans += 1
    if li < i:
        if S[i] == 'E':
            lans += 1

# 右から
r = 0
ri = 0
rmax = -(10**8)
for i in reversed(range(N)):
    if S[i] == 'E':
        r -= 1
    else:
        r += 1
    if r > rmax:
      rmax = r
      ri = i

rans = 0
for i in range(N):
    if i < ri:
        if S[i] == 'W':
            rans += 1
    if ri < i:
        if S[i] == 'E':
            rans += 1

# print(li, ri)
print(min(lans, rans))

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

int main()
{
  int N;
  cin >> N;
  vector<int> a(N);
  for(int i = 0;i<N;i++)cin>>a[i];
  auto b = a;
  sort(b.begin(),b.end());
  b.erase(unique(b.begin(),b.end()),b.end());
  for(int i=0;i<N;i++) a[i]=lower_bound(b.begin(),b.end(),a[i]) - b.begin();
  vector<int> cnt(b.size());
  for(int i=0;i<N;i++) cnt[a[i]] ^= 1;
  int res = 0;
  for(auto x : cnt) res += x;
  cout << res << endl;
}


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

int main() {
	int N; cin >> N;
	vector<int> vc;
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		vc.push_back(a);
	}
	int Min = 100000000;
	for (int j = -100; j <= 100; j++) {
		int cost = 0;
		for (int i = 0; i < N; i++) {
			int dif = vc[i] - j;
			cost += pow(dif, 2);
		}
		Min = min(Min, cost);
	}
	cout << Min << endl;
	//system("pause");
	return 0;
}

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

#define ll long long
#define FASTIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ii pair < ll , ll >
#define all(x) std::begin(x), std::end(x)

ll const MAX = 100005 ;
ll const INF = 1e9 ;
ll const mod = 1000000007 ;


ll dp[105][MAX] ;
ll a[105] , b[105] ;
ll n ;
int k ;

ll cost ( int ndx , int wgt )
{
    if ( ndx >= n || wgt > k )
        return 0 ;

    ll &ret = dp[ndx][wgt] ;
    if ( ret != -1 )
        return ret ;

    if ( wgt + a[ndx] > k )
        return ret = cost ( ndx + 1 , wgt ) ;

    return ret = max ( cost ( ndx + 1 , wgt ) , b[ndx] + cost ( ndx + 1 , wgt + a[ndx] ) ) ;
}


int main ()
{
    //freopen ( "input.txt" , "r" , stdin ) ;
    FASTIO ;

    cin >> n >> k ;
    memset ( dp , -1 , sizeof dp ) ;
    for ( int i = 0 ; i < n ; i ++ )
        cin >> a[i] >> b[i] ;
    cout << cost ( 0 , 0 ) ;


}


Measured memory_bytes: 82304
#include <bits/stdc++.h>
#define rep(i, n) for (long long i = 0, max_i = (n); i < max_i; i++)
#define repi(i, a, b) for (long long i = (a), max_i = (b); i < max_i; i++)
using namespace std;
typedef long long ll;

int main() {
  string S; cin >> S;
  int ans = 999;
  for(int i = 0; i + 2 < S.size(); i++) {
    int num = (S[i] - '0') * 100 + (S[i+1] - '0') * 10 +  S[i+2] - '0';
    ans = min(ans, abs(num-753));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
# 0<x<yだとインクリメント、などのような分岐

x, y = map(int, input().split())
if 0<=x<y:
  print(y-x)
elif y<x:
  print(min(2+abs(x-y), 1+abs(-x-y)))
else:
  print(min(abs(y-x), 1+abs(-y-x)))

Measured memory_bytes: 3060
s = input()
x, y = map(int, input().split())

# Tで区切り、各Tの前にFが何文字あるか数える
steps = []
cnt = 0
for i in range(len(s)):
    if s[i] == "F":
        cnt += 1
    elif s[i] == "T":
        steps.append(cnt)
        cnt = 0
# 最後のブロックについて
if cnt > 0:
    steps.append(cnt)

step_X = steps[0::2]
step_Y = steps[1::2]

# X軸方向の最大値
max_X = sum(step_X)
# dp_X[i][j] = X軸方向の移動をi回行って、jに到達できるか
# j = 0, 1, ..., 2*max_X だが、実際のX座標は -max_X, ..., 0, ..., max_X
# 原点(x=0)は、j = max_Xに相当する
dp_X = [[0 for _ in range(2 * max_X + 1)] for _ in range(len(step_X) + 1)]
dp_X[0][max_X] = 1
# 最初に右へ移動する場合
if s[0] == "F":
    dp_X[1][max_X + step_X[0]] = 1
    for i in range(1, len(step_X)):
        for j in range(2 * max_X + 1):
            if dp_X[i][j] == 1:
                # +X方向に移動
                if j + step_X[i] <= 2 * max_X:
                    dp_X[i + 1][j + step_X[i]] = 1
                # -X方向に移動
                if 0 <= j - step_X[i]:
                    dp_X[i + 1][j - step_X[i]] = 1
# 最初に回転する場合
else:
    for i in range(len(step_X)):
        for j in range(2 * max_X + 1):
            if dp_X[i][j] == 1:
                # +X方向に移動
                if j + step_X[i] <= 2 * max_X:
                    dp_X[i + 1][j + step_X[i]] = 1
                # -X方向に移動
                if 0 <= j - step_X[i]:
                    dp_X[i + 1][j - step_X[i]] = 1

# Y軸方向の最大値
max_Y = sum(step_Y)
# dp_Y[i][j] = Y軸方向の移動をi回行って、jに到達できるか
# j = 0, 1, ..., 2*max_Y だが、実際のY座標は -max_Y, ..., 0, ..., max_Y
# 原点(y=0)は、j = max_Yに相当する
dp_Y = [[0 for _ in range(2 * max_Y + 1)] for _ in range(len(step_Y) + 1)]
dp_Y[0][max_Y] = 1
for i in range(len(step_Y)):
    for j in range(2 * max_Y + 1):
        if dp_Y[i][j] == 1:
            # +Y方向に移動
            if j + step_Y[i] <= 2 * max_Y:
                dp_Y[i + 1][j + step_Y[i]] = 1
            # -Y方向に移動
            if 0 <= j - step_Y[i]:
                dp_Y[i + 1][j - step_Y[i]] = 1

if -max_X <= x <= max_X and -max_Y <= y <= max_Y:
    if dp_X[-1][x + max_X] == 1 and dp_Y[-1][y + max_Y] == 1:
        print("Yes")
        exit()
print("No")


Measured memory_bytes: 205932
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define sec second
#define pb push_back
#define ll long long int
#define mp make_pair
#define endl '\n'
#define rep(i,a,b)      for(int i=a;i<=b;i++)
#define revp(i,a,b)     for(int i=b;i>=a;i--)
void fast(){ ios::sync_with_stdio(false); cin.tie(NULL);}
void file(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);}

int k,n;
int main()
{
    fast();
    //file();
    cin>>k>>n;
    vector<int> v(n);
    rep(i,0,n-1)
        cin>>v[i];
    int ans = k-v[n-1]+v[0];
    rep(i,1,n-2)
        ans = max(ans,v[i+1]-v[i]);
    cout<<k-ans;
}


Measured memory_bytes: 3956
n, k, q, *a = map(int, open(0).read().split())
#n,k,q=map(int,input().split())
l=[0]*n
for i in a:
    l[i-1]+=1
print('\n'.join('Yes' if l[i]-q+k>0 else 'No' for i in range(n)))

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

int conv_string(char *str)
{
	char conved[102800] = {0};
	int i;
	int cnt;
	int len;

	len = strlen(str);
	for (i = 0; i < len; ){
		for (cnt = 0; cnt + i < len; cnt++){
			if (str[i + cnt] != str[i]) break;
		}
		sprintf(conved, "%s%d%c", conved, cnt, str[i]);
		i += cnt;
	}

	strcpy(str, conved);
	return (0);
}

int main(void)
{
	int n, i;
	char str[102800];

	while (scanf("%d", &n), n){
		scanf("%s", str);
		for (i = 0; i < n; i++){
			conv_string(str);
		}
		puts(str);
	}

	return (0);
}

Measured memory_bytes: 776
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF LLONG_MAX/5
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
int x[100010];
int mypow(int a,int b,int c){
	if(b==0)return 1;
	if(b%2)return mypow(a,b-1,c)*a%c;
	int z=mypow(a,b/2,c);
	return z*z%c;
}
signed main(){
	int n,ans=1;
	cin>>n;
	x[0]=3;
	f(i,n){
		int y;
		cin>>y;
		ans*=x[y]-x[y+1];
		x[y+1]++;
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1024
a,b = map(int,input().split())

c = list(map(int,input().split()))

aa = []
aa.append(0)
aa.append(c[0])

l = []
for i in range(1,a):
	aa.append(aa[i]+c[i])
d = 0
p = len(aa)
for i in range(p):
	for j in range(i+1,p):
		l.append(aa[j]-aa[i])
co = 0
la = 0
for i in range(40,-1,-1):
	for j in range(len(l)):
		if l[j] & (la + 2 ** i) == (la + 2 ** i):
			co += 1
	if co >= b:
		la += (2 ** i)
	co = 0

print(la)


Measured memory_bytes: 67324
w, h, n = map(int, input().split())
rect = []
for i in range(h):
    rect.append([0 for _ in range(w)])
for i in range(n):
    x, y, a = map(int, input().split())
    if a == 1:
        for i in range(h):
            for j in range(x):
                rect[i][j] = 1
    elif a == 2:
        for i in range(h):
            for j in range(w-1, x-1, -1):
                rect[i][j] = 1
    elif a == 3:
        for i in range(y):
            for j in range(w):
                rect[i][j] = 1
    else:
        for i in range(y, h):
            for j in range(w):
                rect[i][j] = 1
count = 0
for i in range(h):
    for j in range(w):
        if rect[i][j] == 0:
            count += 1
print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; i++)
#define RFOR(i, a, n) for (ll i = (ll)n - 1; i >= (ll)a; i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define bra(first, second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 1001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template <typename T>
void remove(std::vector<T> &vector, unsigned int index)
{
   vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

// MOD確認

int main(){
   ll N,X,T;
   cin >> N >> X >> T;
   cout << ((N + X - 1) / X) * T << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int main(void){
  double n; cin >> n;
  double x = n*100/108;
  double y = floor(x);
  double l = (y+1)*108/100;
  double k = floor(l);
  if(x == y){
    cout << x << endl;
  }
  else if(k != n) cout << ":(" << endl;
  else cout << y + 1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(){
	int N; 
	cin >> N; 
	long long int A[100010] = {}, B[100010] = {}; 
	for(int i = 0; i < N; i++){
		cin >> A[i]; 
	}
	sort(A, A+N); 
	for(int i = 0; i < N-1; i++){
		B[i] = A[i+1] - A[i]; 
	}
	long long int C[100010] = {}; 
	for(int i = 0; i < N; i++){
		C[i] = min(2 * (i + 1), 2 * (N - 1 - i)); 
	}
	long long int ans = 0; 
	for(int i = 0; i < N - 1; i++){
		ans += B[i] * C[i]; 
	}
	if(N % 2 == 0){
		cout << ans - B[N/2 - 1] << endl; 
	}
	else if(N % 2 == 1){
		cout << ans - min(B[N/2 - 1], B[N/2]) << endl; 
	}
}

Measured memory_bytes: 2688
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n, m; cin >> n >> m;
	vector<int>l;
	int point[110] = { 0 };
	for (int i = 0; i < m; i++){
		int a; cin >> a;
		l.push_back(a);
	}
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++) {
			int a; cin >> a;
			if (a == l[i])point[j]++;
			else point[l[i] - 1]++;
		}
	}
	for (int i = 0; i < n; i++){
		cout << point[i] << endl;
	}
}

Measured memory_bytes: 3156
n, x = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
bit = 0
for i in range(n):
    if a[i] <= x:
        x -= a[i]
        ans += 1
    else:
        bit = 1
if x != 0 and bit == 0:
    ans = max(0, ans - 1)
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <math.h>
#include <map>
#include <numeric>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	string s; cin >> s;
	for(int i=0;i<s.size();i++){
		cout << 'x';
	}
	cout << endl;
}

Measured memory_bytes: 256
from collections import defaultdict

def fctr1(n): 
    d = defaultdict(int)
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            d[i] = c
            c=0
    if n!=1:
        d[n] = 1
    return d

def main():
    N = int(input())
    primes = fctr1(N)
    d = defaultdict(int)
    ans = 0
    for i, j in primes.items():
        cnt = 1
        while True:
            if j - cnt < 0:
                d[i] = j
                break
            ans += 1
            j -= cnt
            cnt += 1

    print(ans)





if __name__ == "__main__":
    main()

Measured memory_bytes: 66420
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <tuple>
#include <climits>
#include <sstream>
using namespace std;

static const unsigned long long int MOD = 1000000007LL;

int main()
{
    int n, w[101], sum[101], res = 1000000;

    cin >> n;

    sum[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        sum[i] = sum[i - 1] + w[i];
    }

    for (int i = 1; i < n; i++)
    {
        int s1 = 0, s2 = 0;

        s1 = sum[i];
        s2 = sum[n] - sum[i];

        res = min(res, abs(s1 - s2));
    }

    cout << res;
    return 0;
}

Measured memory_bytes: 256
# D
import math
n, h = map(int, input().split())
max_a = 0
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
    if max_a < a[i]:
        max_a = a[i]
throw = []
for i in range(n):
    if b[i] > max_a:
        throw.append(b[i])
throw.sort(reverse=True)
damage = 0
count = 0
for i in range(len(throw)):
    damage += throw[i]
    count += 1
    if damage >= h:
        break
if damage < h:
    count += math.ceil((h - damage) / max_a)
print(count)

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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;

    if(a == b)
    {
        cout << c << endl;
    }
    else if (a == c)
    {
        cout << b << endl;
    }
    else
    {
        cout << a << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define LL long int
#define ULL unsigned long int
#define MOD (long int)10e9 + 7

int main(){
    LL n,k;
    cin >> n >> k;

    cout << (abs(n % k) < abs(k - (n % k)) ? abs(n % k) : abs(k - (n % k))) << endl;

    return 0;
}

Measured memory_bytes: 256
int main()
{
    char num[1005];
    int sum=0;
    while(1)
    {
        scanf("%s",num);
        sum=0;
        if (num[0]=='0') break;
        int i, sz=strlen(num);
        for(i=0;i<sz;i++)
 
        {
            sum+=num[i] - '0';
        }
 
    printf("%d\n",sum);
}
}


Measured memory_bytes: 2056
def modpow(a,p):
    mod = 1000000007
    if p==0:
        return 1
    elif p%2==0:
        halfP = p/2
        half = modpow(a,halfP)
        return half * half %mod
    else:
        return a * modpow(a,p-1) % mod
    
def calccomb(a,b):
    mod = 1000000007
    if b>a-b:
        return calccomb(a,a-b)
    ansMul = 1
    ansDiv = 1
    for i in range(b):
        ansMul *= a-i
        ansDiv *= i+1
        ansMul %= mod
        ansDiv %= mod
    #ansDivの逆元
    ans = ansMul * modpow(ansDiv, mod-2)
    return ans
  
import math
N ,M =map(int,input().split())
Mnokori = M
ans = 1
for i in range(2,int(math.sqrt(Mnokori))+1):
    if Mnokori % i == 0:
        cnt = 0
        while Mnokori % i == 0:
            cnt = cnt + 1
            Mnokori /= i
        ans *= calccomb(N+cnt-1,N-1)
        ans %= 1000000007
if Mnokori != 1:
    ans *= calccomb(N+1-1,N-1)
    ans %=  1000000007
print(ans)

Measured memory_bytes: 3064
#include <vector>
#include <iostream>

using namespace std;
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

#define MOD 1000000007

int main() {

	int n; cin >> n;
	vector<vector<int>> a(n, vector<int>(n, 0));
	for (int i = 0; i <= n - 1; i++) for (int j = 0; j <= n - 1; j++) cin >> a[i][j];

	vector<long long> dp(1 << n, 0);
	long long ans = 0;

	for (int mask = 1; mask <= (1 << n) - 1; mask++) {
		int cnt = __builtin_popcount(mask);

		for (int j = 0; j <= n - 1; j++) {

			if (a[cnt - 1][j] == 1 and (mask & (1 << j)) != 0) {

				if (cnt == 1) dp[mask] += 1;

				else {
					dp[mask] += dp[mask - (1 << j)];
					if (dp[mask] >= MOD) dp[mask] %= MOD;
				}

			}
		}

		if (cnt == n) {
			ans += dp[mask];
			if (ans >= MOD) ans %= MOD;
		}
	}

	cout << ans;
	return 0;
}

Measured memory_bytes: 19540
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define REPA(i, v) for(auto&& i : v)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> void pr_vec(vector<T> &v, char ep=' '){int n=v.size();REP(ni,n){cout<<v[ni];if(ni!=n-1)cout<<ep;}cout<<endl;};
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int N;
    cin >> N;
    vector<vector<int>> E(N);
    REP(i, N-1){
        int a,b;
        cin >> a >> b;
        a--;b--;
        E[a].pb(b);
        E[b].pb(a);
    }
    vector<pii> C(N, {-1,-1});
    queue<int> q1, q2;
    q1.push(0);
    while(!q1.empty()){
        auto f = q1.front(); q1.pop();
        REPA(c, E[f]){
            if(C[c].fi==-1){
                C[c].fi = C[f].fi + 1;
                q1.push(c);
            }
        }
    }
    q2.push(N-1);
    while(!q2.empty()){
        auto f = q2.front(); q2.pop();
        REPA(c, E[f]){
            if(C[c].se==-1){
                C[c].se = C[f].se + 1;
                q2.push(c);
            }
        }
    }

    int f = 0, s = 0;
    REPA(ci,C){
        if(ci.fi <= ci.se) f++;
        else s++;
    }
    if(f>s) pr("Fennec");
    else pr("Snuke");
}

Measured memory_bytes: 9596
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<deque>
using namespace std;

using ll = long long;
const int INF = 1001001001;

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

int main()
{
    ll en;
    cin >> en;
    ll numA = en / 500;
    ll numB = (en - numA * 500) / 5;
    cout << numA * 1000 + numB * 5 << endl;
}


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

using namespace std;

int n, k, d[10];
bool isLike[10];

bool isGood(int x) {
    while (x > 0) {
        if (!isLike[x % 10]) {
            return false;
        }

        x /= 10;
    }

    return true;
}

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

    for (int i = 0; i < k; i++) {
        cin >> d[i];
    }

    for (int i = 0; i < 10; i++) {
        isLike[i] = true;
    }

    for (int i = 0; i < k; i++) {
        isLike[d[i]] = false;
    }

    int i = n;
    while (!isGood(i)) {
        i++;
    }

    cout << i << '\n';

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        string s = Console.ReadLine();
        int r = 0;
        int b = 0;
        for (int i = 0; i < n; i ++) {
            if (s[i] == 'R') r ++;
            else b ++;
        }
        Console.WriteLine(r > b ? "Yes" : "No");
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

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

const int INF = 1 << 24;

typedef unsigned long long ull;

int main(){
    int A, B;
    std::vector<int> S, T;

    std::cin >> A >> B;
    
    REP(i, A){
        int s;
        std::cin >> s;
        
        S.push_back(s);
    }

    REP(i, B){
        int t;
        std::cin >> t;
        
        T.push_back(t);
    }

    int res = 0;
    REP(i, B){
        int counter = 0;
        REP(j, A){
            int index = i + counter;
            if(T[index] == S[j]){
                counter++;
            }

            if(counter >= B - i + 1){
                break;
            }
        }

        res = std::max(res, counter);
    }

    std::cout << res << std::endl;
}

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

using namespace std;

typedef long long ll;

int main() {
  int N;
  cin>>N;
  for (int i = 0; i <= N / 7; i++) {
    for (int j = 0; j <= N / 4; j++) {
      int tmp = 7 * i + 4 * j;
      if (tmp == N) {
        cout<<"Yes"<<endl;
        return 0;
      }
    }
  }
  cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <map>
#define INF 100000000
#define rep(i,a) for(int i=0;i<(a);i++)

using namespace std;
typedef long long ll;


int main(){
    int map[3]={};

    map[0]=1;
    char a,b;
    char hoge;
    while(cin>>a>>hoge>>b){
        swap(map[a-'A'],map[b-'A']);
    }
    rep(i,3){
        if(map[i])cout<<(char)(i+'A')<<endl;
    }
    return 0;
}

Measured memory_bytes: 1136
from fractions import gcd
from functools import reduce, lru_cache

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

def lcm(x, y):
    return int(x*y)//int(gcd(x, y))

B = [1 for i in range(N)]
global_lcm = reduce(lcm, A) % MOD
ans = 0
for i in range(N):
    ans += (global_lcm*pow(A[i], MOD-2, MOD)) % MOD
    ans %= MOD

print(ans)

Measured memory_bytes: 6108
x1,y1,x2,y2 = map(int,input().split())

x3 = x2-(y2-y1)
y3 = y2+(x2-x1)
x4 = x1-(y2-y1)
y4 = y1+(x2-x1)

print(x3,y3,x4,y4)


Measured memory_bytes: 9072
#ABC092-B
n = int(input())
d,x = map(int,input().split())
a = []
for _ in range(n):
    a.append(int(input()))
    
cnt = 0
tmp = 0

for i in range(n):
    tmp = 1
    while True:
        if tmp <= d:
            cnt += 1
            tmp += a[i]
        else:
            break
            
            
print(cnt + x)

Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct Edge {
  int src;
  int dest;
  ll cost;
  Edge() {;}
  Edge(int src, int dest, ll cost) : src(src), dest(dest), cost(cost) {;}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int n, m, q;
Graph g;
int visit[100010];
ll dist[100010];
ll base[100];

void Push(ll v) {
  int first = -1;
  for (int i = 60; i >= 0; i--) {
    if (v & (1LL << i)) {
      v ^= base[i];
      if (v & (1LL << i)) { first = max(first, i); }
    }
  }
  assert(first != -1 || v == 0);
  if (first != -1) { base[first] = v; }
}

void dfs(int from, int parent, ll cost) {
  if (visit[from] == 2) { return; }
  if (visit[from] == 1) {
    Push(cost ^ dist[from]);
    return;
  }
  visit[from] = 1;
  dist[from] = cost;
  FORIT(it, g[from]) {
    int to = it->dest;
    if (to == parent) { continue; }
    dfs(to, from, cost ^ it->cost);
  }
  visit[from] = 2;
}

int main() {
  while (scanf("%d %d %d", &n, &m, &q) > 0) {
    MEMSET(visit, 0);
    MEMSET(dist, -1);
    MEMSET(base, 0);
    g = Graph(n);
    REP(i, m) {
      int f, t;
      ll w;
      int v = scanf("%d %d %lld", &f, &t, &w);
      assert(v == 3);
      g[f].push_back(Edge(f, t, w));
      g[t].push_back(Edge(t, f, w));
    }
    dfs(0, 0, 0);
    REP(iter, q) {
      int f, t;
      int v = scanf("%d %d", &f, &t);
      assert(v == 2);
      ll ans = dist[f] ^ dist[t];
      for (int i = 60; i >= 0; i--) {
        if (!(ans & (1LL << i))) { ans ^= base[i]; }
      }
      printf("%lld\n", ans);
    }
  }
}

Measured memory_bytes: 16000
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    if ((S[0] == S[S.length() - 1]) ^ (S.length() % 2 == 0)) {
        cout << "Second" << endl;
    } else {
        cout << "First" << endl;
    }

    return 0;
}




Measured memory_bytes: 512
using System;
using System.Linq;
using System.Numerics;

    class Program
    {
        static void Main(string[] args)
        {
            var NT = Console.ReadLine().Split(' ').Select(s=>BigInteger.Parse(s)).ToList();
            var T = NT[1];
            var ts = Console.ReadLine().Split(' ').Select(s=>BigInteger.Parse(s)).ToList();

            BigInteger sum = T *ts.Count;
            for(var i = 1;i<ts.Count;i++)
            {
                var tmp = (ts[i] - ts[i - 1]);
                if(T>tmp)sum-= T - tmp;
            }

            Console.WriteLine(sum);
        }
    }

Measured memory_bytes: 40704
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

int main()
{
	FILE *fin = NULL, *fout = NULL;
	//fin = freopen("input.txt", "r", stdin);
	//fout = freopen("output.txt", "w", stdout);
	
	int W, H, x, y; scanf("%d%d%d%d", &W, &H, &x, &y);
	long long int S = (long long int)W*(long long int)H;
	if (0 == S % 2){
		printf("%lld ", S / 2);
	}
	else{
		printf("%lld.5 ", S / 2);
	}

	if (W  == x*2 && H == y*2){
		printf("1");
	}
	else{
		printf("0");
	}


	//finalize
	if (NULL != fin) fclose(fin);
	if (NULL != fout) fclose(fout);

	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

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 SORT(c) sort((c).begin(), (c).end())

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

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

// clear memory
#define CLR(a) memset((a), 0, sizeof(a))

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                                               \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"                       \
       << " " << __FILE__ << endl;

void solve(long long A, long long B) {
  long long X;
  if(A>=B){
    X+=A;
    A--;
  }
  else{
    X+=B;
    B--;
  }

  if(A>=B){
    X+=A;
    A--;
  }
  else{
    X+=B;
    B--;
  }
  cout<<X<<endl;
}

int main() {
  long long A;
  scanf("%lld", &A);
  long long B;
  scanf("%lld", &B);
  solve(A, B);
  return 0;
}


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

using namespace std;

int main() {
    int n; cin >> n;
    string s; cin >> s;
    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        int x = c - 'A';
        x += n;
        x %= 26;
        c = 'A' + x;
        s[i] = c;
    }
    cout << s << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;
using vpii=vector<pair<int,int>>;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
//試験導入
#define irep(i, end_i, begin_i) for (ll i = (ll)begin_i-1; i >= (ll)end_i; i--)

long long INF = 1LL<<60;
int main( ){
    ll k;
    cin>>k;
    queue<ll> q;
    rep(i,1,10){
        if(--k){
            q.push(i);
        }
        else{
            cout<<i<<endl;
            return 0;
        }
    };
    int way[]={-1,0,1};
    while(!q.empty()){
        ll v=q.front();
        q.pop();
        int lid=v%10;
        rep(i,0,3){
            if(lid+way[i]<0||lid+way[i]>9)continue;
            else{
                if(--k)q.push(v*10+(lid+way[i]));
                else {cout<<v*10+(lid+way[i])<<endl;return 0;}
            }
        }
    }
    return 0;
}




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

int main()
{
	ios_base::sync_with_stdio(false),cin.tie(NULL);
	int n=0,k=0;
	cin>>n>>k;
	vector<int> v(n+1);
	for(int i=1;i<n+1;i++) cin>>v[i];

	vector<int> dp(n+1,numeric_limits<int>::max());
	dp[1]=0;
	for(int i=2;i<=k;i++) dp[i]=min(dp[i],abs(v[1]-v[i]));
	for(int j=k+1;j<=n;j++) for(int t=1;t<=k;t++) dp[j]=min(dp[j],dp[j-t]+abs(v[j]-v[j-t]));

	cout<<dp[n];
		
	
	return 0;
}

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

int main(){
  int n, m, x;
  cin >> n >> m >> x;
  vector<int>c(n);
  vector<vector<int>>a(n, vector<int>(m));
  for(int i=0; i<n; i++){
    cin >> c[i];
    for(int j=0; j<m; j++)cin >> a[i][j];
  }
  int ret=1000000000;
  for(int i=0; i<1<<n; i++){
    vector<int>u(m, 0);
    int cs=0;
    for(int j=0; j<n; j++){
      if((i&(1<<j))>0){
        cs+=c[j];
        for(int k=0; k<m; k++)u[k]+=a[j][k];
      }
    }
    bool flag=true;
    for(int k=0; k<m; k++){
      if(u[k]<x){
        flag=false;
        break;
      }
    }
    if(flag)ret=min(ret, cs);
  }
  if(ret==1000000000)cout << -1;
  else cout << ret;
  return 0;
}
    

Measured memory_bytes: 3200
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#include <cassert>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using namespace std;

int gcd(int a, int b) {
    if(a < b) {
        swap(a, b);
    }
    if(b < 1)
        return -1;
    if(a % b == 0)
        return b; 
    return gcd(b, a % b);
}

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

    if(A.size() == 1) {
        if(A[0] != K) {
            cout << "IMPOSSIBLE" << endl;
        } else {
            cout << "POSSIBLE" << endl;
        }
        return 0;
    }

    sort(A.begin(), A.end());
    if(A.back() < K) {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }

    int gcd_val = A[0];
    for(int i=1; i<N; ++i) {
        gcd_val = gcd(gcd_val, A[i]);
    }

    rep(i, N) {
        if(A[i] == K) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
        if(A[i] < K) {
            continue;
        }
        A[i] -= K;

        if( A[i] % gcd_val == 0) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
        cout << "IMPOSSIBLE" << endl;

    return 0;
}



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

ll solve(ll n){
	ll rpta;
	if(n==0){
		return 0;
	}
	else{
		return n/5+solve(n/5);
	}
	return rpta;
}

int main(){
	
	ll n,m;
	cin>>n;
	if(n%2==1){
		cout<<"0"<<endl;
	}
	else{
			m=n/10;
		m+=solve(n/10);
		cout<<m<<endl;
	}
	
	
	
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
long long s[2000000], t[2000000], e[2000000], f[20000], g[20000];
int main() {
	int c = 0; long long n, m;
	cin >> n >> m;
	while (true) {
		cin >> s[c] >> t[c] >> e[c];
		if (s[c] == 0 && t[c] == 0 && e[c] == 0) { break; }
		c++;
	}
	int l; cin >> l;
	for (int i = 0; i < l; i++) {
		for (int j = 0; j < 20000; j++)g[j] = 0;
		for (int j = 1; j <= m; j++)cin >> f[j];
		for (int j = 0; j < c; j++) {
			g[s[j]] += f[t[j]] * e[j];
		}
		for (int j = 1; j <= n; j++) {
			if (j >= 2) { cout << ' '; }
			cout << g[j];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 5888