akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>
#include <deque>
#include <map>
#include <cmath>
#include <type_traits>
using namespace std;

#define INF 1e18
#define int long long

template<typename T>
void printVec(vector<T>& v) {
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

signed main() {
    int n, m; cin >> n >> m;
    vector<int> x(m), y(m), cnt(n, 1);
    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        x[i] = a; y[i] = b;
    }

    vector<bool> flag(n, false);
    flag[0] = true;

    for(int i = 0; i < m; i++) {
        cnt[x[i]]--;
        cnt[y[i]]++;
        if(flag[x[i]]) flag[y[i]] = true;
        if(cnt[x[i]] == 0) flag[x[i]] = false;
    }

    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(flag[i]) ans++;
    }

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


Measured memory_bytes: 2560
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
const int MAXN =1e3+5;
int n,m,x_1,y_1,x_2,y_2;
char s[MAXN][MAXN];
int vis[MAXN][MAXN];
int move_1_x[10]={0,1,0,-1,0};
int move_1_y[10]={0,0,1,0,-1};
struct node{
	int x,y,step;
	node(){}
	node(int X,int Y,int STEP){
		x=X;
		y=Y;
		step=STEP;
	}
	friend bool operator < (node X,node Y){return X.step > Y.step;}
};
priority_queue<node> que;
bool check(int x,int y,int time){
	if(x<1 || y<1 || x>n || y>m || vis[x][y]<=time || s[x][y]=='#'){
		return false;
	}
	return true;
}
int main(){
	scanf("%d %d %d %d %d %d",&n,&m,&x_1,&y_1,&x_2,&y_2);
	for(int i=1;i<=n;i++){
		getchar();
		for(int j=1;j<=m;j++){
			scanf("%c",&s[i][j]);
		}
	}
	int step=0x3f3f3f3f;
	memset(vis,0x3f,sizeof(vis));
	que.push(node(x_1,y_1,0));
	vis[x_1][y_1]=0;
	while(!que.empty()){
		node f=que.top();
		que.pop();
		for(int i=1;i<=4;i++){
			int nx=f.x+move_1_x[i];
			int ny=f.y+move_1_y[i];
			int time=f.step;
			if(check(nx,ny,time)){
				vis[nx][ny]=time;
				if(nx==x_2 && ny==y_2){
					step=min(step,time);
				}
				que.push(node(nx,ny,time));
			}
		}
		for(int i=-2;i<=2;i++){
			for(int j=-2;j<=2;j++){
				if(i==0 && j==0)
				continue;
				int nx=f.x+i;
				int ny=f.y+j;
				int time=f.step+1;
				if(check(nx,ny,time)){
					vis[nx][ny]=time;
					if(nx==x_2 && ny==y_2){
						step=min(step,time);
					}
					que.push(node(nx,ny,time));
				}
			}
		}
	}
	if(step==0x3f3f3f3f){
		printf("-1");
	}
	else{
		printf("%d",step);
	}
	return 0;
}

Measured memory_bytes: 8104
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

//?£wi + (n - 2) * min(wi)
//or
//?£wi + min(wi) + (n+1) * x

int main() {
	int MAX = 1000;
	int VMAX = 10000;

	int A[MAX];
	int B[MAX];
	bool V[MAX];
	int T[VMAX];

	int n;
	scanf("%d", &n);

	int s = VMAX;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &A[i]);
		B[i] = A[i];
		V[i] = false;
		s = min(s, A[i]);
	}

	sort(B, B + n);
	for (int i = 0; i < n; ++i) {
		T[B[i]] = i;
	}

	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (V[i]) {
			continue;
		}
		int cur = i;
		int S = 0;
		int m = VMAX;
		int an = 0;
		while (1) {
			V[cur] = true;
			m = min(m, A[cur]);
			int v = A[cur];
			S += v;
			++an;
			cur = T[v];
			if (V[cur] == true) {
				break;
			}
		}
		ans += min(S + (an - 2) * m, S + m + (an + 1) * s);
	}

	cout << ans << endl;

	return 0;
}

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

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        int firstInputNumber  = scan.nextInt();
        int secondInputNumber = scan.nextInt();
        int thirdInputNumber  = scan.nextInt();
        
        List<Integer> minList = new ArrayList<Integer>(Arrays.asList(firstInputNumber, secondInputNumber, thirdInputNumber));
        
        Collections.sort(minList);
        for(int listCount = 0; listCount < minList.size(); listCount++){
            if(listCount == minList.size()-1){
                System.out.println(minList.get(listCount));
                break;
            }
            System.out.print(minList.get(listCount) + " ");
        }
    }
}


Measured memory_bytes: 26128
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include<algorithm>
#include<sstream>
#include<iomanip>
#include<deque>
#include<list>


using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const ll MOD_CONST = 1000000007;
const ll BIG_NUM = 1000000000000000000;
const int BIG_INT = 1000000000;

int main() {
	ll s;
	cin >> s;

	cout << 0 << " " << 0<< " ";
	cout << BIG_INT << " " << 1 << " ";
	int x = (BIG_INT - s % BIG_INT) % BIG_INT;
	int y = (s + x) / BIG_INT;
	cout << x << " " << y << " ";

}

Measured memory_bytes: 256
f=input
from collections import deque
s=deque(f())
n=int(f())
t=0
for i in range(n):
  q=f()
  if q[0]=='1': t^=1 #control the t, kalo t=1 reverse , t=0 no change
  else:
    if int(q[2])==1 and t==1: #t=1 and q[2]=1 , so append from end , krn q[2]=1 append from start 
      s.append(q[4])
    elif int(q[2])==2 and t==1: #t=1 and q[2]=1 , so  append from front , krn q[2]=2 from end
      s.appendleft(q[4])
    elif int(q[2])==1 and t==0: #t=1 and q[2]=1 , sono mama
      s.appendleft(q[4])
    elif int(q[2])==2 and t==0: #t=1 and q[2]=1 , sono mama
      s.append(q[4])
print(''.join([s,list(s)[::-1]][t])) 
#to get first when nothing change or end when t=1 so exchange

Measured memory_bytes: 10484
s = input()
n = len(s)
ans = [0] * n
Rlen = 1
RLlen = 1
for i in range(1, n):
    if s[i] == "R":
        if s[i - 1] == "L":
            Rpoint = (RLlen - Rlen) // 2 + (Rlen - 1) // 2 + 1
            ans[i - (RLlen - Rlen) - 1] = Rpoint
            ans[i - (RLlen - Rlen)] = RLlen - Rpoint
            Rlen = 1
            RLlen = 0
        else:
            Rlen += 1
    RLlen += 1
Rpoint = (RLlen - Rlen) // 2 + (Rlen - 1) // 2 + 1
ans[n - (RLlen - Rlen) - 1] = Rpoint
ans[n - (RLlen - Rlen)] = RLlen - Rpoint
print(*ans)

Measured memory_bytes: 6400
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;

lli mod197 = 1000000007LL;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

int main(void) {
	lli N,t = 0;

	cin >> N;

	for (int i = 0; i < N; i++) {
		lli A;
		cin >> A;

		if (t - 1 > A) {
			COUT("No");
			return 0;
		}

		CHMAX(t, A);
	}

	COUT("Yes");

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using namespace std::chrono;
int arr[100005];
int n;
long long dp[100005];

int main(){
    //auto start = high_resolution_clock::now();
	cin >> n;
  	for(int i = 1 ; i <= n ; i++)	cin >> arr[i];
  	dp[0] = 100000;
  	dp[1] = 0;
    for(int i = 2 ; i <= n ; i++){
        dp[i] = min(dp[i-2] + abs(arr[i-2] - arr[i]) , dp[i-1] + abs(arr[i-1] - arr[i]));
    }
    cout<<dp[n];
}


Measured memory_bytes: 1408
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N = sc.nextInt()
  val D = sc.nextLong()
  println(List.fill(N)(sc.nextLong() -> sc.nextLong()).count {
    case (x, y) => x * x + y * y <= D * D
  })
}


Measured memory_bytes: 77868
#include<stdio.h>
#define NUM 100

int main(void) {
  int i,n;
  int a[NUM];
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&a[n-i]);
  for(i=1;i<=n;i++){
    printf("%d",a[i]);
    if(i<n)
      printf(" ");
    else break;
  } 
  printf("\n");
  return(0);
}

Measured memory_bytes: 600
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = lr()
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0, 0] = 0
    for i in range(N):
        for j in range(max(i//2-1, 0), i//2+2):
            dp[i+1, j+1, 1] = dp[i, j, 0]+A[i]
            dp[i+1, j, 0] = max(dp[i, j, 0], dp[i, j, 1])
    # print(dp)
    print(max(dp[N, N//2, 1], dp[N, N//2, 0]))
resolve()

Measured memory_bytes: 365480
a, b = map(int, input().split())
if 2 in [a, b]:
    print("No")
elif a in [1, 3, 5, 7, 8, 10, 12] and b in [1, 3, 5, 7, 8, 10, 12]:
    print("Yes")
elif a in [4, 6, 9, 11] and b in [4, 6, 9, 11]:
    print("Yes")
else:
    print("No")


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

using namespace std;

const int N=1e6+5,MOD=1e9+7;

typedef long long ll;

int n,c,u,v,k,tc,ans;

char s[N];

int cnt(int x){
	int ret = 0;
	while(x<k){
		x*=2;
		ret++;
	}
	return ret;
}
double prob(int x){
	double ret = 0.5;

	for(int i=1;i<x;i++)ret*=0.5;
	return ret;
}
int main(){
    scanf("%d%d",&n,&k);
	double ans = 0;
	for(int i=1;i<min(k,n+1);i++){
		int x = cnt(i);
		ans+=(1.0/n)*prob(x);
	}

	if(n>=k)
        for(int i=k;i<=n;i++)ans+=1.0/n;


	printf("%.9f\n",ans );
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int N; 
    long long sum = 0;
    cin >> N;

    for (int i = 1; i < N+1; i++)
    {
        if (i % 3 != 0 && i % 5 != 0)
            sum += i;
    }

    cout << sum;

    return 0;
}

Measured memory_bytes: 3604
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#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 gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("0"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}

const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;

int main() {
  int n, m;
  scanf("%d%d",&n,&m);
  vi a(m), b;
  rep(i,m) {
    scanf("%d",&a[i]);
  }
  int cnt = 0;
  rep(i,m) cnt += a[i]&1;
  if (cnt > 2) {
    puts("Impossible");
    return 0;
  }
  sort(rng(a), [&](int i, int j){ return i%2 > j%2;});
  rotate(a.begin(),a.begin()+1,a.end());
  if (m == 1 && a[0] != 1) {
    b.pb(1);
    b.pb(a[0]-1);
  } else {
    b = a;
    b[0]++; b.back()--;
    if (b.back() == 0) b.pop_back();
  }
  cout<<a<<endl;
  cout<<sz(b)<<endl;
  cout<<b<<endl;
  return 0;
}








Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
     int n,t;
     cin>>n>>t;
     long long ans=0;
     int c=0;
     vector<int>a(n);
     cin>>a[0];
     for(int i=1;i<n;i++)
     {
         cin>>a[i];
         ans=a[i]-a[i-1];



     if(ans<t)
     {
         c+=ans;
     }
     else
     {
         c+=t;
     }
     }
     c+=t;

     cout<<c;
}


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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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; }

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

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int gcd(int a, int b){ return b ? gcd(b, a%b) : a; }

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  int n,m; cin>>n>>m;
  string s,t; cin>>s>>t;
  int g = gcd(n,m);
  ll ans = (ll)n/g*m;
  bool ok = true;
  rep(i,g){
    if(s[i*n/g]!=t[i*m/g]) ok=false;
  }
  if(!ok) cout<<-1<<endl;
  else cout<<ans<<endl;
}

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

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

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

  int H,W;
  cin >> H >> W;
  string M[51];
  int white = 0;
  rep(h, H) {
    cin >> M[h];
    rep(w, W) {
      if(M[h][w] == '.') white++;
    }
  }

  queue<pair<int,int>> Q;
  Q.push(make_pair(0, 0));
  int D[51][51];
  rep(i, 51) rep(j, 51) D[i][j] = -1;
  D[0][0] = 0;

  while(!Q.empty()) {
    auto cur = Q.front(); Q.pop();
    rep(i, 4) {
      int nh = cur.first + dy[i];
      int nw = cur.second + dx[i];
      if(nh >= 0 && nh < H && nw >= 0 && nw < W && M[nh][nw] == '.') {
        if(D[nh][nw] != -1) continue;
        D[nh][nw] = D[cur.first][cur.second] + 1;
        Q.push(make_pair(nh, nw));
      }
    }
  }

  if(D[H-1][W-1] != -1) {
    cout << white - D[H-1][W-1] - 1 << endl;
  } else {
    cout << -1 << endl;
  }

  return 0;
}


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

#define fi first
#define se second
#define FO(x, n) for (int x = 0; x < n; ++x)
#define FOR(x, a, b) for (int x = a; x < b; ++x)
#define RFO(x, n) for (int x = n - 1; x >= 0; --x)
#define RFOR(x, a, b) for (int x = b - 1; x >= a; --x)
#define FOR_ITER(x, a) for(auto x = a.begin(); x != a.end(); ++x)



using namespace std;
typedef unsigned char byte;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<string, string> pss;
typedef pair<ll, ll> pll;
inline bool feq(const double& a, const double& b) { return fabs(a - b) < 1e-10; }

using namespace std;


int main(){
//    int n, l;
//    cin >> n >> k;
//    vector<bool> dislike(10, false);
//
//    FOR(i, 0, k) {
//        int t;
//        cin >> t;
//        dislike[t] = true;
//    }




int a,b,c,d;
cin >>a>>b>>c>>d;
cout << max(a*b,c*d)<< endl;
    return 0;
}


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

using namespace std;
using ll = long long;

int main(){
    int n,m;
    int ai;
    int s = 0;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> ai;
        s+=ai;
    }
    if(s>n){
        cout << -1 << endl;
    }else{
        cout << n-s << endl;
    }
}

Measured memory_bytes: 3632
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
/*--Input//////////////////////////////////////////////////*/
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
#define SS(T, ...)      T __VA_ARGS__; IN(__VA_ARGS__);
#define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i;
/*--Output/////////////////////////////////////////////////*/
inline int p(void){cout << endl; return 0;}
template<class Head> int p(Head&& head){cout << head;p();return 0;} template<class Head,class... Tail> int p(Head&& head,Tail&&... tail){cout<<head<<" ";p(forward<Tail>(tail)...);return 0;}
struct ProconInit {
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(n))
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; }
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.second < b.second; }

int main() {
    SS(ll,n);
    bool flag=true; 
    SV(ll,a,n);
    sort(a.begin(),a.end());
    if(n%2==0){
        for(int i=0;i<n-1;i+=2)if(a[i]!=a[i+1])flag=false;
        if(a[0]==0)flag=false;
    }else{
        if(a[0]!=0)flag=false;
        if(n>1)for(int i=1;i<n-1;i+=2)if(a[i]!=a[i+1])flag=false;
    }
    ll ans=1;
    rep(i,n/2)ans=ans*2%1000000007;
    if(flag)cout<<ans<<endl;
    else cout<<0<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll inf  = 1e9+5;
typedef pair<int, bool> pib;

int main() {
  int n; cin >> n;
  vector<int> heights (n);
  for (int i = 0; i < n; i++){
      cin >> heights[i];
  }
  vector<int> dp (n, inf);
  dp[0] = 0;
  for (int i = 0; i < n; ++i){
        for (int j : {i +1, i +2}){
            if (j < n){
                dp[j] = min(dp [j], dp [i] + abs(heights[j] - heights[i]));
            }
        }
  }
  cout << dp[n-1];
}



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

using namespace std;
using ll = long long;

const int MAX { 100010 };
ll MOD { 1000000007 };

ll dp[MAX];
bitset<MAX> trap;

ll solve(int N)
{
    dp[0] = 1;
    dp[1] = (trap[1] ? 0 : 1);

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

    return dp[N];
}

int main()
{
    ios::sync_with_stdio(false);

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

    for (int i = 0; i < M; ++i)
    {
        int t;
        cin >> t;
        trap[t] = true;
    }

    auto ans = solve(N);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#define int long long
using namespace std;
int F[3005][3005],i,j,n,m,A[3005];
bool cal[3005][3005];
int dp(int i, int j)
{
    int res;
    if ((n - j + i -1) % 2 == 0) res=1; else res=-1;
    if (i >= j)
    {
        if (i == j) return A[i]*res;
        else return 0;
    }
    if (cal[i][j]) return F[i][j];
    if (res==1) {
        F[i][j]=max(dp(i+1,j) + A[i] , dp(i,j-1) + A[j]);
    } else {
        F[i][j]=min(dp(i+1,j) - A[i] , dp(i,j-1) - A[j]);
    }
    cal[i][j]=true;
    return F[i][j];
}
signed main()
{
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> A[i];
    }
    cout << dp(1,n);
    return 0;
}


Measured memory_bytes: 78464
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <utility>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <cmath>

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vec vector
#define INF INT_MAX
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

using namespace std;

int main(){
    int h,w,d;
    int q;
    cin>>h>>w>>d;
    vec<vec<int>> v(h,vec<int>(w));
    vec<pair<int,int>> p(h*w+1);
    vec<int> di(h*w+1,0);
    rep(i,0,h)rep(j,0,w){
        cin>>v[i][j];
        p[v[i][j]]=MP(i,j);
    }
    rep(i,d,h*w+1){
        di[i]=di[i-d]+abs(p[i].fi-p[i-d].fi)+abs(p[i].se-p[i-d].se);
    }
    
    cin>>q;
    rep(i,0,q){
        int x,y;
        cin>>x>>y;
        cout<<di[y]-di[x]<<endl;
    }

    return 0;
}


Measured memory_bytes: 2560
#include <algorithm>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <regex>
#include <sstream>
#include <string>
#include <thread>
#include <tuple>
#include <type_traits>
#include <vector>

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

int main() {
    ios::sync_with_stdio(false);

    long double a, b;
    cin >> a >> b;
    cout << ll(floor(a * b)) << endl;
    return 0;
}


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

int main() {
    int N;
    string S;
    cin >> N;
    cin >> S;
    int res = 1;
    for (int i = 1; i < N; ++i){
        if (S[i-1] != S[i]){
            res += 1;
        }
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 512
#include <vector>
#include <functional>
#include <set>
using namespace std;

struct edge_base {
  int from;
  int to;
};

template<class E>
struct graph_base {
  virtual void add_edge(E e) = 0;
  virtual const vector<E>& operator[](int i) const = 0;
  virtual int N() const = 0;
};

template<class E>
struct graph : graph_base<E> {
  vector<vector<E>> G;
  graph(int n) : G(n) {}
  void add_edge(E e) {
    G[e.from].push_back(e);
  }
  const vector<E>& operator[](int i) const { return G[i]; }
  int N() const { return G.size(); }
};

struct grid : public graph<edge_base> {
  using P = pair<int,int>;
  using Delta = function<vector<P>(P,int,int)>;
  Delta delta;
  int n;
  int m;
  grid(int n , int m ,Delta d) : graph<edge_base>(n * m), n(n) , m(m), delta(d) {
    for(int x = 0;x < n;x++) {
      for(int y = 0;y < m;y++) {
        vector<P> res = std::move(delta({x,y},n,m));
        for(auto& v : res) {
          this->add_edge({en({x,y}), en(v)});
        }
      }
    }
  }
  int N() const { return n * m; }
  int en(P p) const { return p.first * m + p.second; }
  P de(int i) const { return {i / m , i % m}; }
};

function<vector<pair<int,int>>(pair<int,int>,int,int)> cross_delta = [](pair<int,int> p,int n,int m) {
  vector<pair<int,int>> vec;
  int d[] = {1,0,-1,0};
  int x = p.first;
  int y = p.second;
  for(int i = 0;i < 4;i++) {
    if(x + d[i] < 0 || x + d[i] >= n) continue;
    if(y + d[i ^ 1] < 0 || y + d[i ^ 1] >= m) continue;
    vec.push_back({x + d[i] , y + d[i ^ 1]});
  }
  return move(vec);
} ;
function<vector<pair<int,int>>(pair<int,int>,int,int)> eight_delta = [](pair<int,int> p,int n,int m) {
  vector<pair<int,int>> vec;
  int x = p.first;
  int y = p.second;
  for(int i = -1;i <= 1;i++) {
    for(int j = -1;j <= 1;j++){
      if(i == 0 && j == 0) continue;
      if(x + i < 0 || x + i >= n) continue;
      if(y + j < 0 || y + j >= m) continue;
      vec.push_back({x + i , y + j});
    }
  }
  return move(vec);
} ;


#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int fie[404 * 404];
i64 cnt[2];

void dfs(int v,int c, grid& g) {
  cnt[c]++;
  fie[v] = -1;
  for(auto & e : g[v]) {
    if(fie[e.to] == (c ^ 1)) {
      dfs(e.to,c ^ 1,g);
    }
  }
}

int main() {
  int h,w;
  cin >> h >> w;
  grid g(h,w,cross_delta);
  rep(i,0,h - 1) {
    string s;
    cin >> s;
    rep(j,0,w - 1) {
      if(s[j] == '.') fie[g.en({i,j})] = 1;
    }
  }
  i64 ans = 0;
  rep(i,0,h - 1) {
    rep(j,0,w - 1) {
      if(fie[g.en({i,j})] == 0) {
        cnt[0] = 0;
        cnt[1] = 0;
        dfs(g.en({i,j}),0,g);
        ans += cnt[0] * cnt[1];
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 19584
#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,n) for(int i=0; i<(n); i++)
    using ll = long long;
    using P = pair<int,int>;
    const int INF = 1001001001;
    int main()
    {
        int n,k,c;
        cin >>n >> k >> c;
        vector<int> right(n),left(n);
        string s;cin >> s;
        int p = 0;
        
        rep(i,n){
            //left
            if (i-c-1 >= 0)p = max(p,left[i-c-1]);
            if(s[i] == 'x')continue;
            
            left[i] = p +1;
        }
        p = 0;
        for(int i = n-1;i >= 0;i--){
            //right
            if(i+ c+ 1 <=n-1)p = max(p,right[i+c+1]);   
            if(s[i] == 'x')continue;
            
            right[i] = p +1;
        }    
        int work = 1;



        vector<int> l(n,-INF),r(n,-INF);
        rep(i,n){
            if(left[i] == work){
                l[i] = work++;
                
            }
            

        }
        work = 1;
        for(int i = n-1; i>= 0;i--){
            if(right[i] == work){
                r[i] = work++;
            }
            
        }
        
        vector<int> ans;
        rep(i,n){
            if(l[i] + r[i] == k+1)ans.push_back(i+1);
        }
        for(auto p:ans)cout << p << endl;

        return 0;
    }

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

const int N=5e2+5;
const int L=3e7;
int n,pr[L+1], npr[L+1];
LL a[N][N],b[N][N];
map <LL,bool> S;
inline bool is_pr(int t) {
	for(int i=2;(LL)i*i<=t;++i) if(!(t%i)) return false;
	return true;
}
inline int nxt_prime() {
	static int hd=2;
	while(!is_pr(hd)) ++hd;
	return hd++;
}
inline LL lcm(LL x,LL y) {
	return (!x || !y) ? (x+y) : (x/__gcd(x,y)*y);
}
int main() {
	cin>>n;
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=n;j++)
			if(((i+j)&1)==((n+1)&1)) {
				if(i==1 || j==1) a[i][j]=nxt_prime();
				else a[i][j]=a[i-1][j-1];
			}
	for(int i=1;i<=n;i++)
		for(int j=n;j>=1;j--)
			if(((i+j)&1)==((n+1)&1)) {
				if(i==1 || j==n) b[i][j]=nxt_prime();
				else b[i][j]=b[i-1][j+1];
				a[i][j]*=b[i][j];
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) if(!a[i][j]) {
			LL v=lcm(lcm(lcm(a[i-1][j],a[i+1][j]),a[i][j-1]),a[i][j+1]);
			LL nowval=v;
			while(S[nowval]) nowval+=v;
			a[i][j]=nowval+1;  S[nowval]=1;
		}
	for(int i=1;i<=n;cout<<'\n',i++)
		for(int j=1;j<=n;cout<<a[i][j++]<<' ');
} 

Measured memory_bytes: 14976
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>

#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <iterator>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define INF (1 << 30)
#define ALEN(ARR) (sizeof(ARR) / sizeof((ARR)[0]))
#define MP make_pair
#define mp make_pair
#define pb push_back
#define PB push_back

#if DEBUG
#define _DEBUG(x) cout << #x << ": " << x << endl
#define _DDEBUG(x, y) cout << #x << ": " << x << ", " << #y << ": " << y << endl
#else
#define _DEBUG(x) ;
#define _DDEBUG(x, y) ;
#endif

#define ll long long
#define ull unsigned long long
#define MOD 1000000007

/** FOR VECTOR DEBUG */
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v)
{
    if (!v.empty())
    {
        out << '[';
        copy(v.begin(), v.end(), ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}

/* template end */

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

    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }

    set<string> st;
    for (int i = 0; i < n; i++)
    {
        string elem = s[i];
        if (st.count(elem) > 0)
        {
            cout << "No" << endl;
            return 0;
        }
        st.insert(elem);
        if (i > 0)
        {
            string before = s[i - 1];
            if (before[before.length() - 1] != elem[0])
            {
                cout << "No" << endl;
                return 0;
            }
        }
    }

#if DEBUG
    cout << "** RESULT **" << endl; // debug
#endif
    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int arr[101][101];
  int flag[101][101];
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      flag[i][j]=0;
    }
  }
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      scanf("%d",&arr[i][j]);
    }
  }
  int a;
  scanf("%d",&a);
  for(int i=0;i<a;i++){
    int x;
    scanf("%d",&x);
    for(int j=0;j<3;j++){
      for(int k=0;k<3;k++){
        if(x==arr[j][k])
          flag[j][k]=1;
    }
  }
}
int flg=0;
for(int i=0;i<3;i++){
  if(flag[0][i]&&flag[1][i]&&flag[2][i]){
    flg=1;
  }
}
for(int i=0;i<3;i++){
  if(flag[i][0]&&flag[i][1]&&flag[i][2]){
    flg=1;
  }
}
if(flag[0][0]&&flag[1][1]&&flag[2][2]){
  flg=1;

}if(flag[0][2]&&flag[1][1]&&flag[2][0]){
  flg=1;
}
(flg)?puts("Yes"):puts("No");
  return 0;
}


Measured memory_bytes: 2072
n = int(input())
lst = [[-1 for _ in range(n)] for _ in range(n)]
for _ in range(n):
    c = int(input())
    for c1 in range(c):
        x, y = map(int, input().split())
        x -= 1
        lst[_][x] = y
        
ans = 0
for bit in range(2**n):
    flg = True
    for a in range(n):
        if (bit >> a) & 1:
            for x in range(n):
                if lst[a][x] != -1:
                    if ((bit >> x) & 1) != lst[a][x]:
                        flg = False
                        break
    if flg:
        ans = max(ans, bin(bit).count('1'))
print(ans)


Measured memory_bytes: 3064
a = gets.to_i
b = gets.to_i
c = gets.to_i
d = gets.to_i
e = gets.to_i
k = gets.to_i

answer = "Yay!"
array = [a,b,c,d,e]

array.combination(2) do |first, second|
  if second - first > k
    answer = ":("
  end
end

puts answer


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

using namespace std;

#define fRead(x)        freopen(x,"r",stdin)
#define fWrite(x)       freopen (x,"w",stdout)

#define LL              long long
#define ULL             unsigned long long
#define ff              first
#define ss              second
#define pb              push_back
#define PI              acos(-1.0)
#define mk              make_pair
#define pii             pair<int,int>
#define pll             pair<LL,LL>


#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(a,min(b,min(c,d)))
#define max4(a,b,c,d)   max(a,max(b,max(c,d)))
#define SQR(a)          ((a)*(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define MEM(a,x)        memset(a,x,sizeof(a))
#define ABS(x)          ((x)<0?-(x):(x))

#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define FastRead        ios_base::sync_with_stdio(0);cin.tie(nullptr);
#ifdef VAMP
     #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template < typename Arg1 >
    void __f(const char* name, Arg1&& arg1){
        cout << name << " = " << arg1 << std::endl;
    }
    template < typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names+1, ',');
        cout.write(names, comma - names) << " = " << arg1 <<" | ";
        __f(comma+1, args...);
    }
#else
    #define debug(...)
#endif

const int N = 200005;

int main()
{

    #ifdef VAMP
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int k , l  , r;
    cin >> k >> l >> r;

    int d = (l/k) * k;
    bool ok = 0;
    if(d == l)ok = 1;
    else{
        if(d + k <= r)ok = 1;
    }
    if(ok)cout << "OK\n";
    else cout << "NG\n";
    #ifdef VAMP
        fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
}


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

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

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
int n, m, q;
int a[51], b[51], c[51], d[51];
int v[11];
 
int main() {
    string S;
    cin >> S;
    bool isfind = false;
    rep(i, 0, S.size()-1){
        if(S[i] == S[i+1]){
            cout << i+1<<" "<<i+2 << endl;
            isfind = true;
            break;
        }
    }
    if (!isfind){
        rep(i, 0, S.size()-2){
            if(S[i] == S[i+2]){
                cout << i+1<<" "<<i+3 << endl;
                isfind = true;
                break;
            }
        }
    }
    if (!isfind){
       cout << "-1"<<" "<<"-1" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>

int main()
{
    int n,m,tf = 0;
    int i,j,k,l;
    scanf("%d %d",&n,&m);

    char a[50][51],b[50][51];

    for (i = 0; i < n; i++)
    {
        scanf("%s",a[i]);
    }
    for (i = 0; i < m; i++)
    {
        scanf("%s",b[i]);
    }

    for (i = 0; i <= n - m; i++)
    {
        for (j = 0; j <= n - m; j++)
        {
            for (k = 0; k < m; k++)
            {
                for (l = 0; l < m; l++)
                {
                    if(a[i + k][j + l] != b[k][l])break;
                }
                if(l != m)break;
            }
            if(k == m)tf = 1;
        }
    }
    if(tf == 1){
        printf("Yes");
    }else{
        printf("No");
    }
    
}


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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

vector<ll>d;

void dfs(string s){
	if(s.size()==10)d.PB(stol(s));
	else{
		if(!s.empty())d.PB(stol(s));
		dfs(s+'3');
		dfs(s+'5');
		dfs(s+'7');
	}
}

int main(){
	ll n;cin>>n;
	dfs("");
	sort(all(d));
	int cnt=0;
	rep(i,d.size()){
		bool a=false,b=false,c=false;
        string t=to_string(d[i]);
        if(d[i]>n)break;
		rep(j,t.size()){
			if(t[j]=='3')a=true;
			if(t[j]=='5')b=true;
			if(t[j]=='7')c=true;
		}
		if(a&&b&&c)cnt++;
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 1400
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    int[] hillHeights = new int[10];
    //Input.
    for (int i = 0; i < 10; i++)
      hillHeights[i] = Integer.parseInt(reader.readLine());
    
    //Sort.
    Arrays.sort(hillHeights);

    //Output.
    for (int i = 0; i < 3; i++)
      System.out.println(hillHeights[hillHeights.length - i - 1]);

  }

}

Measured memory_bytes: 17060
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define ll long long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e9;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

    int N,M; cin >> N >> M;
    int dis[N][N],A[N][N];
    rep(i,N) rep(j,N){
        dis[i][j] = INF;
        A[i][j] = INF;
        if(i==j) dis[i][j]=0;
    }

    rep(i,M){
        int a,b,c; cin >> a >> b >> c;
        a--; b--;
        dis[a][b]=c;
        dis[b][a]=c;
        A[a][b]=c;
        A[b][a]=c;
    }

    rep(i,N) rep(j,N) rep(k,N) {
        dis[j][k] = min(dis[j][k],dis[j][i]+dis[i][k]);
    }

    int ans=0;
    rep(i,N){
        rep(j,N){
            if(i>=j || A[i][j]==INF) continue;
            if(dis[i][j] < A[i][j]) ans++;
        }
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-5;

struct uf {
private:
	vector<int> par, ran;
public:
	uf(int n) {
		par.resize(n, 0);
		ran.resize(n, 0);
		rep(i, n) {
			par[i] = i;
		}
	}
	int find(int x) {
		if (par[x] == x)return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y)return;
		if (ran[x] < ran[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (ran[x] == ran[y])ran[x]++;
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

int ans[1 << 21];
int fakeans[1 << 21];
uf u(1 << 21);
void solve() {
	int n; cin >> n;
	vector<int> a(n);
	rep(i, n-1) {
		cin >> a[i];
	}
	int loc= 0;
	for (int i = n - 2; i >= 2;i--) {
		Rep(j, loc, loc + a[i]) {
			int to = 2 * (loc + a[i])-j;
			u.unite(j, to);
		}
		loc += a[i];
	}
	Rep(i, loc, (1 << 21)) {
		int memo = i - loc;
		int p = u.find(i);
		fakeans[p] = memo;
		ans[i] = memo;
	}
	rep(i, loc) {
		ans[i] = fakeans[u.find(i)];
	}
	int m; cin >> m;
	rep(i, m) {
		int x; cin >> x;
		int out;
		if (x >= loc) {
			out = x - loc;
		}
		else {
			out = ans[x];

		}
		cout << out + a[0] - a[1] << endl;
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(5);
	//init();
	solve();

	//cout << "finish" << endl;
	//stop
	return 0;
}

Measured memory_bytes: 35328
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double EPS=1e-10;
const double PI=acos(-1);

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll x,n;
    cin>>x>>n;
    set<ll> st;
    rep(i,n){
        ll a;
        cin>>a;
        st.insert(a);
    }
    ll mi=inf,ans;
    FOR(i,-100000,100000){
        if(st.count(i)) continue;
        if(chmin(mi,abs(i-x))){
            ans=i;
        }
    }
    cout<<ans<<endl;
}

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

#define F first
#define S second
#define PB push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 100010, M = 1010;

int a, b, c, d, e, f;
int xx, yy;

bool check(int x, int y)
{
	bool flag = false;
	for (int i = 0; i * 100 * a <= x; i ++ )
		for (int j = 0; j * 100 * b <= x - i * 100 * a; j ++ )
			if (!flag && i * a * 100 + j * b * 100 == x)
			{
				flag = true;
				break;
			}
	if (!flag) return false;
	
	flag = false;
	for (int i = 0; i * c <= y; i ++ )
		for (int j = 0; j * d <= y - i; j ++ )
			if (!flag && i * c + j * d == y)
			{
				flag = true;
				break;
			}
	return flag;
}

int main()
{
	cin >> a >> b >> c >> d >> e >> f;
	
	double res = 0;
	for (int x = 0; x <= f / 100; x ++ )
		for (int y = 0; y <= x * e; y ++ )
			if (x * 100 + y <= f && check(100 * x, y))
				if (res <= (double)y / (100 * x + y))
				{
					res = (double)y / (100 * x + y);
					xx = x, yy = y;
				}
				
	cout << xx * 100 + yy << ' ' << yy << endl;
	return 0;
}

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

int main() {
    int n, idx = 0;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
    }
    for (int i = 0; i < n; i++) {
        if (a.at(i) == idx + 1) {
            idx++;
        }
    }
    cout << (idx != 0 ? n - idx : -1) << endl;
}

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

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(obj) obj.begin(), obj.end()

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;
}

const int iINF = 1e9;
const long long llINF = 1e18;
const int MOD = 1e9 + 7;

using namespace std;

int main() { 
    double a, b, x, theta;
    cin >> a >> b >> x;
    if (x > a * a * b / 2) {
        theta = atan(2 * (a * a * b - x) / (a * a * a));
    } else {
        theta = atan((a * b * b) / (2 * x));
    }

    theta = theta * 180 / acos(-1);
    printf("%.12f\n", theta);
    return 0; 
}

Measured memory_bytes: 256
while True :
	x = raw_input().split()
	a = int(x[0])
	b = int(x[2])

	if x[1] == '+' :
		print a + b
	elif x[1] == '-' :
		print a - b
	elif x[1] == '*' :
		print  a * b 
	elif x[1] == '/' :
		print a / b
	elif x[1] == '?' :
		break

Measured memory_bytes: 6392
#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
        int n,m;
        cin >> n;
        string s[n];
        map<string,int> mp;
        for(int i=0;i<n;i++){
                cin >> s[i];
                auto itr = mp.find(s[i]);
                if( itr != mp.end()){
                        mp[s[i]]++;
                }else{
                        mp[s[i]] = 1;
                }
        }
        cin >> m;
        string t[m];
        for(int i=0;i<m;i++){
                cin >> t[i];
                mp[t[i]]--;
        }
        int max=0;
        for(auto itr=mp.begin();itr!=mp.end();++itr){
                if(itr->second>max){
                        max=itr->second;
                }
        }
        cout << max << endl;
        return 0;
}

Measured memory_bytes: 256
while True:  

 H, W = map(int,raw_input().split())
 if (H ==0 and W == 0):
   break
 for i in range(H):
  if i%2==0:
   if W%2==0:
    print "#."*(W/2)
   elif W%2==1:
    print "#."*(W/2)+"#"

  elif i%2==1:
   if W%2==0:
    print ".#"*(W/2)
   elif W%2==1:
    print ".#"*(W/2)+"."
 print ""

Measured memory_bytes: 6364
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int i,j,l,cnt=0;
    cin>>s;
    l=s.size();
    j=l-1;
    for(i=0;i<l/2;i++)
    {
        if(s[i]!=s[j])
            cnt++;
        j--;
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256