akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <stdio.h>
#define llint long long

using namespace std;

string us = "999999999", ls = "1";

bool check(int n)
{
	char rep, rep2;
	cout << "? " << n << endl;
	cin >> rep;
	
	char tmp[20]; string s;
	sprintf(tmp, "%d", n);
	s = tmp;
	
	if(s >= us){
		if(rep == 'Y') return true;
		else return false;
	}
	if(s < ls){
		if(rep == 'N') return true;
		else return false;
	}
	
	string t = s;
	while(t.size() < 15) t += "0";
	cout << "? " << t << endl;
	cin >> rep2;
	
	if(rep2 == 'Y') us = s;
	else ls = t;
	
	if( (rep == 'Y') == (rep2 == 'Y') ) return true;
	else return false;
}

int main(void)
{
	int lb = 0, ub = 1000000005, mid;
	while(ub - lb > 1){
		mid = (lb + ub) / 2;
		if(check(mid)) ub = mid;
		else lb = mid;
	}
	cout << "! " << ub << endl;
	
	return 0;
}

Measured memory_bytes: 692
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef struct _maze {
  int i;
  int j;
} Maze;

int main(void) {
  int h = 0, w = 0;
  cin >> h;
  cin >> w;
  vector<vector<int>> map(h+2, vector<int>(w+2, 0));
  
  // set map
  for(int i = 0; i < h+2; i++) {
    map[i][0] = -1;
    map[i][w+1] = -1;
  }
  for(int j = 0; j < w+2; j++) {
    map[0][j] = -1;
    map[h+1][j] = -1;
  }
  for(int i = 1; i < h+1; i++) {
    for(int j = 1; j < w+1; j++) {
      char ch;
      cin >> ch;
      if(ch == '#') map[i][j] = -1;
    }
  }
  
  int max = 0;
  
  // BFS
  for(int i = 1; i < h+1; i++) {
    for(int j = 1; j < w+1; j++) {
      if(map[i][j] == -1) continue;
      vector<vector<int>> bfs_map(h+2, vector<int>(w+2, -1));
      queue<Maze> que;
      que.push(Maze{i, j});
      bfs_map[i][j] = 0; // set start position
      while(!que.empty()) {
        Maze m = que.front();
        que.pop();
        if(map[m.i-1][m.j] == 0 && bfs_map[m.i-1][m.j] == -1) {
          bfs_map[m.i-1][m.j] = bfs_map[m.i][m.j]+1;
          if(bfs_map[m.i-1][m.j] > max) max = bfs_map[m.i-1][m.j];
          que.push(Maze{m.i-1, m.j});
        }
        if(map[m.i+1][m.j] == 0 && bfs_map[m.i+1][m.j] == -1) {
          bfs_map[m.i+1][m.j] = bfs_map[m.i][m.j]+1;
          if(bfs_map[m.i+1][m.j] > max) max = bfs_map[m.i+1][m.j];
          que.push(Maze{m.i+1, m.j});
        }
        if(map[m.i][m.j-1] == 0 && bfs_map[m.i][m.j-1] == -1) {
          bfs_map[m.i][m.j-1] = bfs_map[m.i][m.j]+1;
          if(bfs_map[m.i][m.j-1] > max) max = bfs_map[m.i][m.j-1];
          que.push(Maze{m.i, m.j-1});
        }
        if(map[m.i][m.j+1] == 0 && bfs_map[m.i][m.j+1] == -1) {
          bfs_map[m.i][m.j+1] = bfs_map[m.i][m.j]+1;
          if(bfs_map[m.i][m.j+1] > max) max = bfs_map[m.i][m.j+1];
          que.push(Maze{m.i, m.j+1});
        }
      }
    }
  }
  cout << max;
  return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

sA = sorted(A)
l = sA[N//2 - 1]
r = sA[N//2]

median = defaultdict(int)
m = N // 2 - 1
for i,a in enumerate(sA):
  if i <= m and not median[a]:
    median[a] = sA[m+1]
  elif m < i and not median[a]:
    median[a] = sA[m]

ans = []
for a in A:
  ans.append(median[a])
  
print("\n".join(map(str,ans)))

Measured memory_bytes: 43812
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n;
int a[20][20];
ll cost[(1 << 16) + 5];
ll dp[(1 << 16) + 5];
vector<int> v;
int tren;

void rek(int x, int mask) {
	if (x == v.size()) {
		dp[tren] = max(dp[tren], dp[tren-mask]+cost[mask]);
		return;
	}
	
	rek(x+1, mask);
	rek(x+1, mask|(1 << v[x]));
}

int main () {

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < n; j++) {
			for (int k = j+1; k < n; k++) {
				if ((i&(1 << j)) > 0 && (i&(1 << k)) > 0) {
					cost[i] += a[j][k];
				}
			}
		}
	}
	
	for (int i = 0; i < (1 << n); i++) {
		v.clear();
		for (int j = 0; j < n; j++) {
			if ((i&(1 << j)) > 0) {
				v.push_back(j);
			}
		}
		
		tren = i;
		rek(0, 0);
	}
	
	cout << dp[(1 << n)-1];

	return 0;
}


Measured memory_bytes: 4608
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long

const long long MOD = 998244353;

int fact[300010], invfact[300010];

long long powmod(long long a, long long k) {
    int r = 1;
    while(k > 0) {
        if (k & 1) {
            r = (r * a) % MOD;
        }
        a = (a * a) % MOD;
        k /= 2;
    }
    return r;
}

long long invmod(long long a, const long long mod) {
    return powmod(a, mod - 2);
}

const long long comb(long long n, long long i) {
    if (i > n) {
        return 0;
    }
    return (fact[n] * invfact[i]) % MOD * invfact[n-i] % MOD;
}

void solve(long long N, long long A, long long B, long long K){
    fact[0] = invfact[0] = 1;
    for(int i = 1; i < 300010; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
        invfact[i] = invmod(fact[i], MOD);
    }

    int res = 0;
    for(int i = 0; i <= N; ++i) {
        int L = K - A * i;
        int j = L / B;
        if (L < 0 || L % B != 0 || j > N) {
            continue;
        }
        res += comb(N, i) * comb(N, j) % MOD;
        res %= MOD;
    }
    cout << res << endl;
}

signed main(){
	ios::sync_with_stdio(false);
    long long N;
    scanf("%lld",&N);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long K;
    scanf("%lld",&K);
    solve(N, A, B, K);
    return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
    int n, h,nw, katanas;
    cin>>n>>h;
    int w[n], t[n], st=0, nt=0, lw=0;
    for(int i=0;i<n;i++){
        cin>>w[i]>>t[i];
        if(w[i]>lw)
            lw=w[i];
    }
    sort(t,t+n);
    for(int i=n-1; i>=0; i--){
        if(t[i]>=lw&&st<h){
            st+=t[i];
            nt++;
        }
 
    }
    if(st>=h){
        cout<<nt;
    }
    else{
     nw=(h-st)/lw;

     katanas=nw+nt;
        if(nw*lw+st>=h)
        cout<<katanas;
        else cout<<katanas+1;
    }
	return 0;
}

Measured memory_bytes: 1024
N = int(input())
A_list = list(map(int, input().split()))

dic = {4: 0, 2: 0, 1: 0}
for i in A_list:
    if i % 4 == 0:
        dic[4] += 1
    elif i % 2 == 0:
        dic[2] += 1
    else:
        dic[1] += 1
dic[4] += dic[2] // 2

if len(A_list) // 2 <= dic[4]:
    print('Yes')
else:
    print('No')


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

int main(){

    int a,b,c;
    cin >> a >>b >> c;

    int ans=(a+b)*c/2;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>

using namespace std;

struct comp {
    bool operator()(const pair<string, int>& a, const pair<string, int>& b) const {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n, p;
    string s;
    map< pair<string, int>, int, comp > m;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s >> p;
        m[{s, p}] = i;
    }
    for (auto i = m.begin(); i != m.end(); ++i) printf("%d\n", (*i).second);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int main(){
	string s;
	while(cin >> s){
		map<char, int> mp;
		set<char> st;
		for(int i = 0; i < s.size(); i++){
			mp[s[i]]++;
			st.insert(s[i]);
		}
		//cout << (*st.begin()) << ' ' << (*st.rbegin()) << endl;
		if(st.size() == 2 && mp[*st.begin()] == 2 && mp[*st.rbegin()] == 2){
			cout << "Yes" << endl;
		}
		else cout << "No" << endl;
	}
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    long long int k;
    cin >> n >> k;
    int a[n+5][2]={0};
    int b[n+5];
    b[1]=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i][0]);
    }
    int p=1;
    int ret=0;
    while(a[p][1]!=1&&k>0){
    	a[p][1]=1;
        p=a[p][0];
        k--;
        ret++;
        if(a[p][1]!=1)
        b[p]=ret;
    }
    if(k==0)
    cout << p;
    else{
    int x = ret-b[p];
    k%=x;
    while(k!=0){
        p=a[p][0];
        k--;
    }
    cout << p;}
    return 0;
}


Measured memory_bytes: 6008
#!/usr/bin/env python
#-*- coding: utf-8 -*-

import sys

w = int(input())
n = int(input())

lst = range(1, w+1)

for num in sys.stdin:
    nums = num.split(",")
    a1 = int(nums[0]) - 1
    b1 = int(nums[1]) - 1

    a2 = lst[a1]
    b2 = lst[b1]
    lst[a1] = b2
    lst[b1] = a2

for i in lst:
    print(i)

Measured memory_bytes: 6240
#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

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

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template<class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl;exit(0);}else return;}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
void YN(bool flg) {cout << ((flg) ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << ((flg) ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << ((flg) ? "yes" : "no") << endl;}

int main() {
	int ans = 0;
	string s; cin >> s; REP(i, 4) if (s[i] == '2') ans++;
	cout << ans << endl;

}



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

int main() {
    int n, m, x, y, *xArray, *yArray;

    scanf("%d %d %d %d", &n, &m, &x, &y);

    xArray = new int[n + 1];
    yArray = new int[m + 1];

    for(int i = 0; i < n; i++) scanf("%d", &xArray[i]);
    for(int i = 0; i < m; i++) scanf("%d", &yArray[i]);

    xArray[n] = x;
    yArray[m] = y;

    sort(xArray, xArray + n + 1);
    sort(yArray, yArray + m + 1);

    if(xArray[n] < yArray[0]) printf("%s\n", "No War");
    else printf("%s\n", "War");

    delete [] xArray;
    delete [] yArray;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;


int main(){
    int a;
    cin>>a;
    int wer = -1;
    for(int i=1;i < a+1;i++){
        int ans = 0;
        int p = i;
        while(p%2 ==0){
            p /= 2;
            ans++;
        }
        if (ans > wer){
            wer = ans;
        }

    }
    cout<<pow(2,wer)<<endl;
    
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+1;

int n,a[N];
ll b[N],ans=1e18;

void Solve(int x){
	int l=1,r=x-1;
	while(l!=r){
		int mid=l+r+1>>1;
		if(b[mid]<=b[x]-b[mid])l=mid;
		else r=mid-1;
	}
	int L=x+1,R=n-1;
	while(L!=R){
		int mid=L+R+1>>1;
		if(b[mid]-b[x]<=b[n]-b[mid])L=mid;
		else R=mid-1;
	}
	ll f[5];
	f[0]=0;
	for(int i=-2;i<=2;++i)
	for(int j=-2;j<=2;++j){
		f[1]=l+i,f[2]=x,f[3]=L+j,f[4]=n;
		for(int k=4;k;--k)if(f[k]-f[k-1]>=1)f[k]=b[f[k]]-b[f[k-1]];
		sort(f+1,f+5);
		ans=min(ans,f[4]-f[1]);
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),b[i]=b[i-1]+a[i];
	for(int i=2;i<=n-2;++i)Solve(i); 
	printf("%lld\n",ans);
}

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

int main(void)
{
  int n;
  double total = 0;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    double x;
    char u[4];
    scanf("%lf %3s", &x, u);
    total += strcmp("JPY", u) == 0 ? x : x * 380000.0;
  }
  printf("%f\n", total);
}


Measured memory_bytes: 128
def slove():
    import sys
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    b = 0
    cnt1 = 0
    cnt2 = 0
    for i in range(len(s)):
        if b == int(s[i]):
            cnt1 += 1
        if b != int(s[i]):
            cnt2 += 1
        b = 1 if b == 0 else 0
    print(min(cnt1, cnt2))


if __name__ == '__main__':
    slove()


Measured memory_bytes: 42604
#include <iostream>

using namespace std;

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

  int h[4][3][10];
  for (int i = 0; i < 4; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      for (int k = 0; k < 10; k++)
      {
        h[i][j][k] = 0;
      }
    }
  }

  for (int i = 0; i < n; i++)
  {
    int b, f, r, v;
    cin >> b >> f >> r >> v;
    b--;
    f--;
    r--;
    h[b][f][r] += v;
  }

  for (int i = 0; i < 4; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      for (int k = 0; k < 10; k++)
      {
        cout << " " << h[i][j][k];
      }
      cout << endl;
    }
    if (i != 3)
    {
      cout << "####################" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3104
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>

using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

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

int main(){
	string s[3];
	cin>>s[0]>>s[1]>>s[2];
	queue<int> q[3];
	rep(i, 3){
		rep(j, s[i].size()){
			q[i].push(s[i][j]-'a');
		}
	}
	int nxt = 0;
	while(1){
		if(q[nxt].empty()){
			cout<<(char)('A'+nxt)<<endl;
			return 0;
		}
		int t = q[nxt].front();
		q[nxt].pop();
		nxt = t;
	}

}

Measured memory_bytes: 256
/*
    Author : Nishant Gupta 2.0
*/
#include<bits/stdc++.h>

#define LL long long int
#define getcx getchar_unlocked
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define MAX 3005
#define LOG_MAX 20
#define MOD 998244353
#define INF 0x3f3f3f3f
#define INFL (LL(1e18))
#define chk(a) cerr << endl << #a << " : " << a << endl
#define chk2(a,b) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << endl
#define chk3(a,b,c) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << endl
#define chk4(a,b,c,d) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << "\t" << #d << " : " << d << endl
#define rep(i, a, n) for(i=a;i<n;i++)
#define rev(i, a, n) for(i=a;i>=n;i--)
#define MSV(A,a) memset(A, a, sizeof(A))
#define rep_itr(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)

using namespace std;

inline void inp( int &n ) { 
	n=0;    int ch=getcx();int sign=1;   
	while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();} 
	while(  ch >= '0' && ch <= '9' )    
	n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
	n=n*sign;
}

inline void inp1( LL &n ) { 
	n=0;    LL ch=getcx();LL sign=1;   
	while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();} 
	while(  ch >= '0' && ch <= '9' )    
	n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
	n=n*sign;
}

int a[MAX];
int dp[MAX][MAX];

/* Modulo exponentiation */
LL power(LL base, LL exp, LL ans) {
	if(!exp) return ans % MOD;
	if(exp&1) ans = (ans * base) % MOD;
	return power((base * base) % MOD, exp>>1, ans);
}

int solve(int pos, int sum, int n) {
	if(sum < 0) return 0;
		
	if(sum == 0) return power(2, n-pos, 1);
	
	if(pos == n) return 0;
	
	if(dp[pos][sum] != -1) return dp[pos][sum];
	
	dp[pos][sum] = ((2 * solve(pos+1, sum, n)) % MOD + solve(pos+1, sum-a[pos], n)) % MOD;
	
	return dp[pos][sum];
}

int main() {
	int n, s;	
	cin>>n>>s;
	MSV(dp, -1);
	for(int i=0;i<n;i++) cin>>a[i];
	
	cout<<solve(0, s, n)<<endl;
    return 0;
}



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

#define fi first
#define se second
#define ll long long

const int N = 200200;

using namespace std;

int n, m;
long long a[N];
int res = 1;
long long L, R;
bool used[N];
vector < pair < int, int > > v[N];

void dfs(int x, long long c)
{
        if(used[x]){
                res &= (a[x] == c);
                return;
        }
        used[x] = 1;
        L = min(L, c);
        R = max(R, c);
        a[x] = c;
        for(auto y: v[x]){
                dfs(y.fi, c + y.se);
        }
}

int main()
{
        ios_base::sync_with_stdio(0);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

        cin >> n >> m;
        for(int i = 1; i <= m; i++){
                int a, b, d;
                cin >> a >> b >> d;
                v[a].push_back({b, d});
                v[b].push_back({a, - d});
        }
        long long inf = 1e9;
        for(int i = 1; i <= n; i++){
                if(!used[i]){
                        L = R = 0;
                        dfs(i, 0);
                        res &= (R - L <= inf);
                }
        }
        cout << (res ? "Yes" : "No") << "\n";
}


Measured memory_bytes: 17120
#include <bits/stdc++.h>
using namespace std;
#define iinf 2000000000
#define linf 1000000000000000000LL
#define ulinf 10000000000000000000ull
#define MOD1 1000000007LL
#define mpr make_pair
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned long UL;
typedef unsigned short US;
typedef pair < int , int > pii;
clock_t __stt;
inline void TStart(){__stt=clock();}
inline void TReport(){printf("\nTaken Time : %.3lf sec\n",(double)(clock()-__stt)/CLOCKS_PER_SEC);}
template < typename T > T MIN(T a,T b){return a<b?a:b;}
template < typename T > T MAX(T a,T b){return a>b?a:b;}
template < typename T > T ABS(T a){return a>0?a:(-a);}
template < typename T > void UMIN(T &a,T b){if(b<a) a=b;}
template < typename T > void UMAX(T &a,T b){if(b>a) a=b;}
int k;
LL mul[20];
vector < LL > res;
void go(int len,int trl,int sum,LL val,bool ldz){
	if(len>15 || val>mul[trl]*(LL)sum) return;
	if(!ldz) res.push_back(val);
	int i;
	for(i=0;i<10;++i){
		go(len+1,trl+(int)(trl==len && i==9),sum+i,val+(LL)i*mul[len],!i);
	}
}
int main(){
    // inputting start
    // 数据结构记得初始化！ n，m别写反！
    scanf("%d",&k);
    #ifdef LOCAL
        TStart();
    #endif
    // calculation start
    // 数据结构记得初始化！ n，m别写反！
	int i;
	mul[0]=1LL;
	for(i=1;i<20;++i) mul[i]=mul[i-1]*10LL;
	go(0,0,0,0LL,1);
    sort(res.begin(),res.end());
	for(i=0;i<k;++i) printf("%lld\n",res[i]);
    #ifdef LOCAL
        TReport();
    #endif
    return 0;
}

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

using namespace std;

int calc_min(int x, int y)
{
    return x % y == 0 ? y : calc_min(y, x % y);
}


int main(void)
{
	int n;
	int mon[100000];
	int min = 1000000000;
	int fmin = 0;
	
	scanf("%d", &n);
	for(int num = 0; num<n; num++)
	{
		scanf("%d", &mon[num]);
	}

	for(int a = 1; a < n; a++)
	{
		fmin = calc_min(max(mon[a],mon[a-1]), std::min(mon[a],mon[a-1]));
		if(fmin < min)min = fmin;
		
		if(min == 1)break;
	}

	printf("%d", min);

	scanf("%d");
	return 0;
}


Measured memory_bytes: 640
#include<stdio.h>

int main(){
    int x[10],y,z,i;
    for(y=0;y<10;y++){
        scanf("%d",&x[y]);
    }
    for(y=0;y<1000;y++){
        for(z=1;z<10;z++){
           if(x[z]>x[z-1]){
            i=x[z-1];
            x[z-1]=x[z];
            x[z]=i;
           }
        }
    }
    for(y=0;y<3;y++){
    printf("%d\n",x[y]);
    }
    return 0;
}


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

// H0 = 0 として、入力は H1 から始まるとする
// DP[i][j][k]： 1～i列の範囲で、j列採用した場合で、左の採用列の一番近い列が k の最小値
// DP[0][][] = 0
// 採用しない場合は変わらず
// 	DP[1][0][k] = DP[0][0][k]
// 採用する場合
// 	DP[1][1][1] = DP[0][0][0] + (H1 > H0) ? (H1 - H0) : 0
// 汎用化すると
// j <= i, k < i
// 採用しない場合
// 	DP[i][j][k] = min( DP[i-1][j][k], DP[i][j][k])
// 採用する場合
// 	DP[i][j][i] = min( DP[i-1][j-1][k] + (Hi > Hk) ? (Hi - Hk) : 0, DP[i][j][i] )

ll dp[305][305][305];

const ll INF = 1LL << 60;

int main() {
  ll N, K;
  cin >> N >> K;
  vector<ll> H(N+1);
  H[0] = 0;
  REP(i,N) {
    cin >> H[i+1];
  }
  
  REP(i,N+1) REP(j,N+1) REP(k,N+1) dp[i][j][k] = INF;
  dp[0][0][0] = 0;
  
  for ( int i=1; i<N+1; ++i ) {
    REP(j,i+1) {
      REP(k,i) {
        // i列目を採用しない
        dp[i][j][k] = min( dp[i-1][j][k], dp[i][j][k]);
        if ( j > 0 ) {
          // i列目を採用する
          dp[i][j][i] = min( dp[i-1][j-1][k] + ((H[i] > H[k]) ? (H[i] - H[k]) : 0), dp[i][j][i] );
        }
      }
    }
  }
  ll ans = INF;
  for ( int j=N-K; j<=N; ++j ){
    REP(k,N+1) {
      ans = min( ans, dp[N][j][k]);
    }
  }
//   REP(i,N+1) {
//     REP(j,N+1) {
//       REP(k,N+1) {
//         if ( dp[i][j][k] == INF ) 
//           cout << "***" << " ";
//         else
//           cout << setw(3) << dp[i][j][k] << " ";
//       }
//       cout << " : ";
//     }
//     cout << endl;
//   }

  cout << ans << endl;
}


Measured memory_bytes: 219520
#include<stdio.h>
int main(void)
{
	int a,b,c;
	int n,i;
	
	while (scanf ("%d",&n)!=EOF) {
		for (i=0; i<n; i++) {
			scanf ("%d %d %d",&a,&b,&c);
			if(c*c==a*a+b*b || a*a==b*b+c*c || b*b==a*a+c*c) {
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}
		}
	}
	
	return 0;
}

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

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

void solve(){
    int n,a,b; cin>>n>>a>>b;

    int tot = a+b;

    int comp = n/tot; int left = n%tot;

    int ba = comp*a + min(left,a);
    cout<<ba<<endl;
}

signed main(){

   FastRead;    


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

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

int gcd(int a, int b){
	if(a < b)
		gcd(b,a);
	int r;
	while((r=a%b)){
		a = b;
		b = r;
	}
	return b;
}

int main(){
	int N, X;
	cin >> N >> X;
	int a[N];
	for(int i = 0; i < N; i++){
		cin >> a[i];
		a[i] = abs(a[i] - X);
	}
	int ans = a[0];
	for(int i = 0; i < N; i++)
		ans = gcd(ans,a[i]);
	cout << ans << endl;
	return 0;
}

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

int main(){
    string s;
    cin>>s;
    ll n = s.size();
    vector<ll> l(n+1),r(n+1);
    for(ll i=1; i<=n; i++) {
        if(s[i-1] == '<') l[i] = l[i-1]+1;
    }
    for(ll i=n-1; i>=0; i--) {
        if(s[i] == '>') r[i] = r[i+1]+1;
    }
    vector<ll> a(n+1);
    for(ll i=0; i<=n; i++) {
        a[i] = max(l[i],r[i]);
    }
    cout<<accumulate(a.begin(),a.end(),0LL);
}

Measured memory_bytes: 12548
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k,n;
    cin>>k>>n;
    if(n==0)
    {
        cout<<k<<endl;
        return 0;
    }
    set<int> s;
    for(int i = 0;i<n;i++)
    {
        int x;
        cin>>x;
        s.insert(x);
    }
    int i = k,j = k;
    int ans;
    int m = INT_MAX;
    int flag  = 1;
    while(flag)
    {
        if(abs(k-i)<m)
        {
            if(s.find(i)==s.end())
            {
            flag = 0;
            m = abs(k-i);
            ans = i;
            }
            i--;
        }
        if(abs(k-j)<m)
        {
                 if(s.find(j)==s.end())
        {
        flag = 0;
        m = abs(k-j);
            ans = j;
            }
            j++;

            }
            
        }

    
    cout<<ans;
    
    
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>

using namespace std;

int main(){
    long n,t,a,count=0;
    long h[100001];
    bool c = false;
    bool d = false;
    cin >> n;
    for (int i=0;i<n;i++){
        cin >> h[i] ;
    }
    if(n==1){
        cout << "Yes" << endl;
    }


    else{
        for (int i=0;i<n-1;i++){
            t = h[i] - h[i+1];
            if(t==1){
                if(c==true && a > h[i+1]){
                    cout << "No" << endl;
                    d = true;
                    break;
                }
                a=h[i+1];
                c=true;
            }
            else if(t>1){
                cout << "No" << endl;
                d = true;
                break;
            }
        }
        if(d == false){
            cout << "Yes" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
	double r, menn, syuu;
	scanf("%lf", &r);
	menn=3.141592653589*r*r;
	syuu=2*3.141592653589*r;
	printf("%f %f\n", menn, syuu);
		
	return 0;
}


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

int main()
{
	int N;
	string S;	
	cin >> N;
	
	while ( N ) {
		if ( N % 2 ) {
			S += '1';
			N -= 1;
		} else {
			S += '0';
		}
		N /= -2;
	}

	reverse(begin(S), end(S));
	
	if ( S == "" ) {
		cout << 0 << endl;
	} else {
		cout << S << endl;
	}

	return ( 0 );
}


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

const long long INF = 9223372036854775807;

int main()
{
    int N, M, X;
    cin >> N >> M >> X;
    int C[N], A[N][M];
    for (int i = 0; i < N; i++) {
        cin >> C[i];
        for (int j = 0; j < M; j++) {
            cin >> A[i][j];
        }
    }

    long long res = INF;
    for (int bit = 0; bit < (1<<N); bit++) {
        long long price = 0;
        long long understand[M] = {0};

        for(int i = 0; i < N; i++) {
            if (bit & (1<<i)) {
                price += C[i];
                for (int j = 0; j < M; j++) {
                    understand[j] += A[i][j];
                }
            }
        }

        long long *min_X = min_element(understand, understand+M);
        if (*min_X >= X) res = min(res, price);
    }

    if (res == INF) cout << -1 << endl;
    else cout << res << endl;
}

Measured memory_bytes: 3640
n, m = list(map(int, input().split()))
h = list(map(int, input().split()))
path = [[] for _ in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    if h[a - 1] < h[b - 1]:
        path[a - 1].append(False)
        path[b - 1].append(True)
    elif h[a - 1] == h[b - 1]:
        path[a - 1].append(False)
        path[b - 1].append(False)
    else:
        path[a - 1].append(True)
        path[b - 1].append(False)
ans = 0
for i in path:
    if all(i):
        ans += 1
print(ans)


Measured memory_bytes: 23004
use num::Num;
use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input! {
        n: usize,
        q: usize,
        c: [usize; n],
        queries: [(Usize1, Usize1); q],
    }
    let mut pi: Vec<Option<usize>> = vec![None; n+1];
    let mut ps = vec![vec![]; n];
    for i in 0..n {
        if let Some(num) = pi[c[i]] {
            ps[num].push(i);
        }
        pi[c[i]] = Some(i);
    }
    let mut qs = vec![vec![]; n];
    for i in 0..q {
        let (l, r) = queries[i];
        qs[l].push((r, i));
    }

    let mut ans = vec![0; q];
    let mut d: BIT<usize> = BIT::new(n);
    for x in (0..n).rev() {
        for &y in &ps[x] {
            d.add(y, 1);
        }
        for &query in &qs[x] {
            let r = query.0;
            let i = query.1;
            ans[i] = (r-x+1) - d.sum(r);
        }
    }

    for &a in &ans {
        println!("{}", a);
    }
}

struct BIT<T> {
    n: usize,
    d: Vec<T>,
}

impl<T> BIT<T>
where
    T: Num + Copy + Clone,
{
    fn new(n: usize) -> Self {
        BIT {
            n: n,
            d: vec![T::zero(); n + 1],
        }
    }

    fn add(&mut self, mut i: usize, x: T) {
        i += 1;
        while i <= self.n {
            self.d[i] = self.d[i] + x;
            i += (i as isize & (i as isize * -1)) as usize;
        }
    }

    fn sum(&self, mut i: usize) -> T {
        let mut x = T::zero();
        i += 1;
        while i != 0 {
            x = x + self.d[i];
            i -= (i as isize & (i as isize * -1)) as usize;
        }
        x
    }

    fn sums(&self, l: usize, r: usize) -> T {
        self.sum(r - 1) - self.sum(l - 1)
    }
}


Measured memory_bytes: 90932
n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)

o = [*1..n]
x = y = 0
o.permutation.to_a.sort.each_with_index do |arr, i|
  if arr == a
    x = i + 1
  end
  if arr == b
    y = i + 1
  end
end

p (x - y).abs

Measured memory_bytes: 7384
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    string s;
    int r = 0;
    cin >> s;
    for(int i = 0; i < 4; i++){
        if(s[i] == '+'){
            r++;
        }
        else
        {
            r--;
        }   
    }
    cout << r;
    cout << endl;
}


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

int H, N, Q, p[30][30]; vector<int>r[30], J; string c[30]; string S;

vector<int>amida_add(vector<int>a, vector<int>b) {
	vector<int>c = a, p = a, q = a;
	for (int i = 0; i < a.size(); i++)p[a[i]] = i;
	for (int i = 0; i < b.size(); i++)q[b[i]] = i;
	for (int i = 0; i < a.size(); i++)c[q[p[i]]] = i;
	return c;
}

vector<int> amida_rep(vector<int>a, int rep) {
	vector<int>dp[32], res = J;
	for (int i = 0; i < 32; i++) { dp[i].resize(a.size(), 0); }
	dp[0] = a;
	for (int i = 0; i < 31; i++) dp[i + 1] = amida_add(dp[i], dp[i]);
	for (int i = 0; i < 31; i++) {
		if ((rep / (1 << i)) % 2 == 1) res = amida_add(res, dp[i]);
	}
	return res;
}

vector<int>solve(int L, int R) {
	if (L == R) {
		for (int i = 0; i < N; i++) { if (S[L] == c[i][0])return r[i]; }
	}
	vector<int>D; D.push_back(L - 1); int depth = 0;
	for (int i = L; i <= R; i++) { if (S[i] == '(')depth++; if (S[i] == ')')depth--; if (S[i] == '+' && depth == 0) D.push_back(i); } D.push_back(R + 1);
	if (D.size() >= 3) {
		vector<int> T = J;
		for (int i = 0; i < D.size() - 1; i++) { vector<int>U = solve(D[i] + 1, D[i + 1] - 1); T = amida_add(T, U); }
		return T;
	}
	int cl = -1, cr = -1;
	for (int i = L; i <= R; i++) { if (S[i] == '(') { cl = i; break; } }
	for (int i = R; i >= L; i--) { if (S[i] == ')') { cr = i; break; } }
	if (cl != -1) {
		int P = stoi(S.substr(L, cl - L));
		vector<int>U = solve(cl + 1, cr - 1);
		U = amida_rep(U, P);
		return U;
	}
	int PP = stoi(S.substr(L, R - L));
	vector<int>UU = solve(R, R);
	UU = amida_rep(UU, PP);
	return UU;
}

int main() {
	cin >> H >> N;
	for (int j = 0; j < H; j++) J.push_back(j);
	for (int i = 0; i < N; i++) {
		int w = 0; cin >> c[i] >> w; r[i] = J;
		for (int j = 0; j < w - 1; j++) {
			for (int k = 0; k < H - 1; k++) {
				cin >> p[j][k]; if (p[j][k] == 1) swap(r[i][k], r[i][k + 1]);
			}
		}
	}
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		cin >> S;
		vector<int>ans = solve(0, S.size() - 1);
		for (int j = 0; j < ans.size(); j++) { if (j)cout << " "; cout << ans[j] + 1; }cout << endl;
	}
	return 0;
}


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

using namespace std;



#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define euc_dis(x, y) sqrt(x*x + y*y)

#define pb push_back
#define mp make_pair
#define INF 999999999
#define sp ' '

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

typedef long long ll;
typedef pair<int, int> pint;
typedef vector<int> vint;
typedef vector<string> vstr;

vector<string> split(const string &str, char sep)
{
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.pb(buffer);
    }
    return v;
}




int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;
    int x[n];
    int sum = 0;
    rep(i, n){
        cin >> x[i];
    }


    rep(i, n){
        sum += min(x[i], k-x[i]);
    }

    cout << sum*2 << endl;




    return 0;
}


Measured memory_bytes: 256
DIVS = 1000000007
def LI(): return [int(x) for x in input().split()]

N,M=LI()
SS=LI()
TT=LI()

dp=[[0]*(M+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(1,M+1):
        if SS[i-1] != TT[j-1]:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] + 1) % DIVS

print((dp[N][M]+1)%DIVS)

Measured memory_bytes: 330500
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i < int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

int SURP = 1000000007;

int main(){
	int N;
	cin >> N;
	int t[N+1], x[N+1], y[N+1];

	t[0] = 0;
	x[0] = 0;
	y[0] = 0;
	FOR(i,1,N+1){
		cin >> t[i] >> x[i] >>  y[i];
	}

	bool isPos = true;

	FOR(i,1,N+1){
		int td = t[i] - t[i-1];
		int xd = abs(x[i]-x[i-1]);
		int yd = abs(y[i]-y[i-1]);
		if (td > xd + yd){
			if((td - xd - yd)%2 != 0){
				isPos = false;
				break;
			}
		}else if (td < xd + yd){
			isPos = false;
			break;
		}
	}

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

	return 0;

}

Measured memory_bytes: 1408
h1,m1,h2,m2,k=map(int,input().split())

if m2>=k%60:
  m_limit=m2-k%60
  h_limit=h2-int(k/60)
elif m2<k%60:
  m_limit=m2+60-k%60
  h_limit=h2-1-int(k/60)


if m_limit>=m1:
  ans=(m_limit-m1)+(h_limit-h1)*60
elif m_limit<m1:
  ans=(m_limit+60-m1)+(h_limit-h1-1)*60
print(ans)

Measured memory_bytes: 9200
import Control.Applicative
import Control.Monad
import Data.Char

solver :: String -> Integer  -> Char
solver (x:xs) k =
    let l = digitToInt x
        n = fromIntegral l :: Integer
        m = n^5000
        in if m < k then solver xs (k-m) else x

main :: IO ()
main = do
    s <- getLine
    k <- read <$> getLine
    putChar $ solver s k
    putChar '\n'


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

using namespace std;
#define inf 1000000000
#define unvisited -1
#define visited 1
#define eps 1e-9
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define uint64 unsigned long long
#define FastSlowInput ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define debug if(true)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

const ll mod = 1e9 + 7;
const int maxn = 1e6 + 6;
ll fac[maxn];
ll invFac[maxn];

ll modPow(ll a, ll b) {
	if(b == 0){return 1;}
	else{
		if(b%2 == 1){return a*modPow(a,b-1)%mod;}
		else{
			ll temp = modPow(a,b/2);
			return temp*temp%mod;
		}
	}
}

ll modInv(ll a){
	return modPow(a,mod-2);
}

ll c(int a, int b){
	return (fac[a]*invFac[b]%mod)*invFac[a-b]%mod;
}

int main(){
	int n,m,i,j;
	scanf("%d %d",&n,&m);
	fac[0] = 1, invFac[0] = 1;
	for(i=1;i<maxn;i++){
		fac[i] = i*fac[i-1];
		fac[i] %= mod;
		invFac[i] = modInv(fac[i]);
	}
	ll ans = 0;
	for(i=0;i<=n;i++){
		int sisa = n-i;
		int banyak1 = i;
		if(sisa % 2 == 1){continue;}
		int banyak2 = sisa/2;
		int banyak = banyak1 + banyak2;
		int totY = banyak1*2 + banyak2;
		if(totY == m){
			ans += c(banyak, banyak1);
			ans %= mod;
		}
	}
	printf("%lld\n",ans);
	return 0;
};

Measured memory_bytes: 15872
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
#define FAST  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long int 
#define ar array
#define pb push_back
#define fi(a,b) for(int i=a;i<(b);i++)
#define fj(a,b) for(int j=a;j<(b);j++)
#define fk(a,b) for(int k=a;k<(b);k++)
#define lb lower_bound
#define ub upper_bound
//hash base 177013



int main()
{
	FAST;
	//#ifndef ONLINE_JUDGE
	//	freopen("input.txt","r",stdin);
	//	freopen("output.txt","w",stdout);
	//#endif
	//ll testcase;
	//cin>>testcase;
	//while(testcase--)
	{
		int n;
		cin>>n;
		int a[n];
		fi(0,n) cin>>a[i];
		int dp[n];
		fill(dp,dp+n,1000000000);
		dp[0]=0;
		fi(1,n)
		{
			if(i-1>=0)
			dp[i]=min(dp[i],dp[i-1]+abs(a[i]-a[i-1]));
			if(i-2>=0)
			dp[i]=min(dp[i],dp[i-2]+abs(a[i]-a[i-2]));
		}
		cout<<dp[n-1];
		
		
		
	}
}


Measured memory_bytes: 4420
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
typedef string::const_iterator State;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int timer = 0;

int f(State &itr) {
    timer += 1;
    //if(timer >= 10) return -1;
    //cerr << "----" << timer << "----" << endl;
    //cerr << *itr << endl;
    if(*itr <= '9' && *itr >= '0') {
        //cerr << "hoge " << *itr << endl;
        int num = 0;
        while(*itr <= '9' && *itr >= '0') {
            num *= 10;
            num += (int)(*itr - '0');
            itr++;
        }
        //cerr << *itr << " " << num << endl;
        return (num + 1) / 2;
    }
    vector<int> now;
    itr++;
    while((*itr) != ']') {
        int num = f(itr);
        //cerr << num << endl;
        now.push_back(num);
        //cerr << now.size() << endl;
    }
    itr++;
    sort(now.begin(), now.end());
    int sum = 0;
    //cerr << "SIZE: " << now.size() << endl;
    for(int i = 0; i * 2 < now.size(); i++) sum += now[i];
    return sum;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    cin.ignore();
    while(n--) {
        string S;
        getline(cin, S);
        State itr = S.begin();
        cout << f(itr) << endl;
    }
    return 0;
}


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

int main(int argc, const char * argv[]) {
    int a,b,c;
    cin >> a >> b >> c;
    if (a == b + c || b == a + c || c == a + b ){
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
} 

Measured memory_bytes: 256
import java.util.Scanner;


public class Main {

	public static void main(String[] args)  {

		Scanner sc = new Scanner(System.in);
		int n =  Integer.parseInt(sc.next());		
		int m =  Integer.parseInt(sc.next());		
		int[] h = new int[n];
		boolean[] low = new boolean[n];
		for(int i = 0 ; i < n; i++) {
			h[i] = Integer.parseInt(sc.next());
		}

		for(int i = 0 ; i < m; i++) {
			int a =  Integer.parseInt(sc.next())-1;
			int b =  Integer.parseInt(sc.next())-1;

			if(h[a] == h[b]) {
				low[a] = true;
				low[b] = true;
			}else if(h[a] > h[b]) {
				low[b] = true;
			}else{
				low[a] = true;
			}
		}

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

		System.out.println(ans);
	}
}


Measured memory_bytes: 49860
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            new Main().solve(sc);
        }
    }

    void solve(Scanner sc) {
        int n = sc.nextInt();
        int d = sc.nextInt();
        int x = sc.nextInt();
        int count = 0;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            for (int j = 0;; j++) {
                if (a * j + 1 > d) {
                    break;
                }
                count++;
            }
        }
        System.out.println(count + x);
    }
}

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

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

int main(){
  int h,w;
  cin >> h >> w;

  vector<vector<char>> grid(h+1,vector<char>(w));
  rep(i,h)rep(j,w) cin >> grid.at(i).at(j);

  rep(i,h) grid.at(i).push_back('.');
  rep(i,w) grid.at(h).at(i) = '.';

  int nowx=0, nowy=0;
  int pass=0;
  bool check1=false;
  while(1){
    //cout << nowx << " " << nowy << endl;
    if(nowx==h-1&&nowy==w-1){check1=true; pass++; break;}

    if(grid.at(nowx).at(nowy+1)=='#'&&grid.at(nowx+1).at(nowy)=='#') break;
    else if(grid.at(nowx).at(nowy+1)=='#'){nowy=nowy+1; pass++; continue;}
    else if(grid.at(nowx+1).at(nowy)=='#'){nowx=nowx+1; pass++; continue;}
    
    break;
  }

  bool check2=false;
  int count=0;
  rep(i,h)rep(j,w){
    if(grid.at(i).at(j)=='#') count++;
  }
  if(pass==count) check2=true;
  //cout << pass << " " << count;

  if(check1&&check2) cout << "Possible";
  else cout << "Impossible";
  
}

Measured memory_bytes: 3636
#include<stdio.h>

int main(void)
{
  int a,b,c,d,ans,x,y;
  scanf("%d %d %d %d",&a,&b,&c,&d);
  if(a < c)
    {
      x = c;
    }
  else
    {
      x = a;
    }
  if(b < d)
    {
      y = b;
    }
  else
    {
      y = d;
    }
  ans = y - x;
  if(ans < 0)
    {
      ans = 0;
    }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>

using namespace std;

int n, k;
long long maxsum, minsum, sum[200001], r;
int mod = 1000000007;

int main()
{
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
    sum[i] = sum[i - 1] + i;
  for (int i = k; i <= n + 1; i++) {
    minsum = sum[i - 1];
    maxsum = sum[n] - sum[n - i];
    r += (maxsum - minsum + 1);
    r %= mod;
  }
  cout << r % mod;
  return 0;
}


Measured memory_bytes: 5112
#include<iostream>
using namespace std;
int main() {

	//C
	int n, m;
	cin >> n >> m;
	int AC[100000];
	int WA[100000];
	int i, p;
	for (i = 0; i < n; i++) {
		AC[i] = 0;
		WA[i] = 0;
	}

	string s;
	for (i = 0; i < m; i++) {
		cin >> p;
		cin >> s;
		if (s == "AC") {
			AC[p - 1]++;
		}else{
			if(AC[p-1]==0)WA[p - 1]++;
		}
	}
	int pn = 0, sc = 0;
	for (i = 0; i < n; i++) {
		if (AC[i] > 0) {
			sc++;
			pn += WA[i];
		}
	}
	cout << sc << ' ' << pn << endl;
	return 0;

	//B
	/*int n, k, m;
	cin >> n >> k >> m;
	int sum = 0, a, i;
	for (i = 0; i < n - 1; i++) {
		cin >> a;
		sum += a;
	}
	for (i = 0; i <= k; i++) {
		if (sum + i >= n * m) {
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
*/	
	
	
	
	//A

	/*char c;
	cin >> c;
	cout << (char)(c + 1) << endl;
	return 0;*/
}

Measured memory_bytes: 4348
#include<bits/stdc++.h>
/*
g++ -std=c++11 -Wall -g -fsanitize=undefined -D_GLIBCXX_DEBUG aising/a.cpp
*/
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define INF (1e16)
typedef long long ll;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);//おまじないでcin, cout早くする
    int n, h, w;
    cin >> n >> h >> w;
    cout << (n - h + 1) * (n - w + 1) << "\n";
    return 0;
}

Measured memory_bytes: 256
#2,3
#3,4

def main():
    N = int(input())
    A = [int(_n) for _n in input().split()]
    B = [int(_n) for _n in input().split()]
    max_h = [10**10]*N
    min_h = [1]*N
    prev = -1
    for i in range(N):
        a = A[i]
        if prev != a:
            max_h[i] = a
            min_h[i] = a
        else:
            max_h[i] = max_h[i-1]
            min_h[i] = 0
        prev = a
    prev = -1
    res = 1
    MOD = 10**9+7
    for i in reversed(range(N)):
        a = B[i]
        new_range = [0,0]
        if prev != a:
            new_range[0] = a
            new_range[1] = a
        else:
            new_range[0] = max_h[i+1]
            new_range[1] = 1
        if max_h[i] < new_range[1] or min_h[i] > new_range[0]:
            print(0)
            return
        max_h[i] = min(max_h[i], new_range[0])
        min_h[i] = max(min_h[i], new_range[1])
        # print(max_h[i],min_h[i])
        res = (max_h[i]-min_h[i]+1) * res % MOD
        prev = a
    print(res)



main()

Measured memory_bytes: 82916
#include <iostream>
#include <cmath>

int main(){
  int A, B, C, X, Y;
  std::cin >> A >> B >> C >> X >> Y;    
  long long M = 0;
  int min = std::min(X, Y);
  if(2 * C >= A + B){
    M = min * A + min * B;
  }else{
    M = min * 2 * C;
  }

  int left = 0;
  left = std::max(X - min, Y - min);

  if(Y >= X){
    if(2 * C >= B){
      M += B * left;
    }else{
      M += 2 * C * left;
    }
  }else{
    if(2 * C >= A){
      M += A * left;
    }else{
      M += 2 * C * left;
    }
  }
  std::cout << M << std::endl;
  return 0;
}


Measured memory_bytes: 256
A,B=map(int,input().split())
B+=1
Abit=[0]*41
for j in range(41):
    bitp=A//(2*(2**j))
    bitm=A%(2*(2**j))
    Abit[j]+=bitp*(2**j)
    Abit[j]+=max(0,bitm-2**j)
Bbit=[0]*41
for j in range(41):
    bitp=B//(2*(2**j))
    bitm=B%(2*(2**j))
    Bbit[j]+=bitp*(2**j)
    Bbit[j]+=max(0,bitm-2**j)
res=0
for j in range(41):
    Bbit[j]-=Abit[j]
    res+=(Bbit[j]%2)*(2**j)
print(res)


Measured memory_bytes: 3188
s = input()
q = int(input())
query_list = [input().split() for _ in range(q)]

front = []
back = []
is_reverse = False

for query in query_list:
    if query[0] == '1':
        is_reverse = not is_reverse
    elif query[0] == '2':
        key = int(query[1])
        value = query[2]
        if (key == 1 and not is_reverse) or (key == 2 and is_reverse):
            front.append(value)
        else:
            back.append(value)

ans = ''
if is_reverse:
    ans = back[::-1]+list(s)[::-1]+front
else:
    ans = front[::-1]+list(s)+back
print(''.join(ans))


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

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

ll sum(ll n) {
    string s = to_string(n);
    ll res = 0;
    rep(i, s.size()) res += s[i] - '0';
    return res;
}

ll f(ll n) {
    string s = to_string(n);
    ll sn = sum(n);
    double mn = 1e18;
    ll next = -1;
    rep(i, s.size()) {
        rep(d, 10) {
            string t = s;
            t[i] = d + '0';
            for (int j=i+1; j<s.size(); ++j) t[j] = '9';
            ll m = stoll(t);
            if (m < n) continue;
            ll sm = sum(m);
            if (mn > (double)m/sm) {
                mn = (double)m/sm;
                next = m;
            }
        }
    }
    return next;
}

int main() {
    ll K;
    cin >> K;
    ll a = 1;
    rep(i, K) {
        cout << a << endl;
        a = f(a + 1);
    }
}


Measured memory_bytes: 256