akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=1e9+7;
ll linf=(1LL<<31)-1LL;
ll n;
vector<ll>RMQ(1<<21);
void init(ll n_){
    n=1;
    while(n<n_){
        n*=2;
    }
    rep(i,n*2-1){
        RMQ[i]=linf;
    }
}
void update(ll k,ll a){
    k+=n-1;
    RMQ[k]=a;
    while(k>0){
        k--;
        k/=2;
        RMQ[k]=min(RMQ[2*k+1],RMQ[2*k+2]);
    }
}
ll query(ll a,ll b,ll k,ll l,ll r){
    if(r<=a||l>=b)return linf;
    if(l>=a&&r<=b)return RMQ[k];
    else {
        return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
    }
}
int main(){
    ll n_;cin>>n_;
    init(n_);
    ll q;cin>>q;
    rep(i,q){
        ll a,x,y;cin>>a>>x>>y;
        if(a)cout<<query(x,y+1,0,0,n)<<endl;
        else update(x,y);
    }
}


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

int main() {
    int N;
    cin>>N;
    vector<int> A(N);
    for (int i = 0; i < N; i++)cin>>A[i];
    sort(A.begin(),A.end(),greater<int>());
    ll ans=-A[0];
    for (int i = 0; i < N/2; i++){
        ans+=2*A[i];
    }
    if(N%2==1)ans+=A[N/2];
    cout<<ans<<endl;
}

Measured memory_bytes: 4100
#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 PI (acos(-1))

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
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 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=1e15;
const int INF=1e9;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int r,d,x;
	cin>>r>>d>>x;
	FOR(i,1,11){
		x=r*x-d;
		cout<<x<<endl;
	}
}

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

#define maxn 100010
#define INF 1e15
#define ff first
#define ss second
#define endl '\n'
typedef long long ll;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); 
  int n;
  cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; ++i) cin >> v[i];
  sort(v.begin(), v.end());
  int ans = 0;
  for (int i = 0; i < n - 1; ++i) {
    for (int j = i + 1; j < n; ++j) {
      int idx = lower_bound(v.begin() + j, v.end(), v[i] + v[j]) - v.begin();
      ans += max(0, idx - j - 1);
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
while True:
    p=int(input())
    
    if p==0:
        break
    else:
        list1=[]

        for i in range(p):
            a=int(input())
            list1.append(a)
            i+=1

        min1=min(list1)
        max1=max(list1)

        list1.remove(min1)
        list1.remove(max1)

        sum1=sum(list1)

        men=p-2
        print(sum1//men)




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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    int l, r, d; cin >> l >> r >> d;

    int ans = 0;
    for (int i = 1; i <= 1000; ++i) {
        if (l <= d * i && d * i <= r) {
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3608
#include <iostream>
using namespace std;
void whatday(int year, int month, int date) {
  string day[7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
  if(month == 1 || month == 2) {
	year--;
	month += 12;
  }
  int YEAR = year / 100;
  int h = (year + (year >> 2) - YEAR + (YEAR >> 2) + (13*month + 8)/5 + date) % 7;
  cout << day[h] << endl;
}
int main() {
  int month, day;
  while(cin >> month >> day) {
	if(month == 0 && day == 0) break;
	whatday(2004, month, day);
  }

  return 0;
}

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
char s[2333][2333];
void gao(int x)
{
	for(int i=1;i<=x;i++)for(int j=1;j<=x;j++)s[i][j]='.';
	s[1][1]=s[2][1]='z';s[1][x]=s[2][x]='z';s[x][x]=s[x-1][x]='z';s[x][1]=s[x][2]='z';
	s[3][1]=s[3][2]='y';
	for(int i=1;i<=x-2;i++)
	{
		s[i][i+1]=s[i][i+2]='a'+(i%2);
	}
	for(int i=3;i<=x-1;i++)
	{
		s[i][i]=s[i+1][i]='c'+(i%2);
	}
}
int n,k;
int main()
{
	ios_base::sync_with_stdio(false);
	cin>>n;
	if(n==2)
	{
		puts("-1");
	}
	else if(n==3)
	{
		puts("aa.");
		puts("..a");
		puts("..a");
	}
	else if(n==4)
	{
		puts("aabc");
		puts("ddbc");
		puts("bcaa");
		puts("bcdd");
	}
	else if(n==6)
	{
		puts("aabb..");
		puts("b..zz.");
		puts("ba....");
		puts(".a..aa");
		puts("..a..b");
		puts("..a..b");
	}
	else if(n%2==0)
	{
		if(n%4!=0)
		{
			gao(n/2);
			for(int i=1;i<=n/2;i++)
			{
				for(int j=1;j<=n/2;j++)
				{
					putchar(s[i][j]);
				}
				for(int j=1;j<=n/2;j++)
				{
					putchar('.');
				}
				puts("");
			}
			for(int i=1;i<=n/2;i++)
			{
				for(int j=1;j<=n/2;j++)
				{
					putchar('.');
				}
				for(int j=1;j<=n/2;j++)
				{
					putchar(s[i][j]);
				}
				puts("");
			}
		}
		else
		{
			s[1][1]=s[1][2]=s[3][3]=s[3][4]='a';
			s[2][1]=s[2][2]=s[4][3]=s[4][4]='b';
			s[3][1]=s[4][1]=s[1][3]=s[2][3]='c';
			s[3][2]=s[4][2]=s[1][4]=s[2][4]='d';
			for(int i=1;i<=n/4;i++)
			{
				for(int t=1;t<=4;t++)
				{
					for(int j=1;j<=i*4-4;j++)
					{
						putchar('.');
					}
					for(int j=1;j<=4;j++)
					{
						putchar(s[t][j]);
					}
					for(int j=i*4+1;j<=n;j++)
					{
						putchar('.');
					}
					puts("");
				}
				
			}
		}
	}
	else
	{
		gao(n);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				putchar(s[i][j]);
			}
			puts("");
		}
	}
	return 0;
}

Measured memory_bytes: 5376
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  string s;
  cin>>s;
  string t = s;
  reverse(t.begin(),t.end());
  for(int i = 0; t.size() > i; i++){
    if(t[i] == 'b')t[i] = 'd';
    else if(t[i] == 'd')t[i] = 'b';
    else if(t[i] == 'q')t[i] = 'p';
    else t[i] = 'q';
  }
  if(s==t)cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n, k;
    cin >> n >> k;
    char a[n];
    for (int i = 0; i < n; i++){
        cin >> a[i];
        if (i == k-1) {
            if (a[k-1] == 'A') {
                a[k-1] = 'a';
            } else if (a[k-1] == 'B') {
                a[k-1] = 'b';
            } else {
                a[k-1] = 'c';
            }
        }
        cout << a[i];
    }
    cout <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <vector>
#include <cmath>
#include <stdlib.h>
#include <unordered_map>
#define ll long long
using namespace std;
int a[110];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int i;
    for( i=0;i<n;i++){
        if(a[i]<=k){
            k-=a[i];
        }
        else
            break;
    }
    if(i==n&&k>0)
        i--;
    cout<<i;
}


Measured memory_bytes: 256
function parse_table(N)
    local tbl = {}
    for i=1,N do
        table.insert(tbl, io.read("n"))
    end
    return tbl
end

function find_leftmost_ge(a, x)
    local i, j = 1, #a + 1
    while i < j do
        m = (i + j) // 2
        if a[m] < x then
            i = m + 1
        else
            j = m
        end
    end
    return i
end

function main()
    local A, B, Q = io.read("n", "n", "n")
    local S = parse_table(A)
    local T = parse_table(B)
    local function search(x, sl_i, tl_i)
        local cur_min = 100000000000
        for _, si in ipairs({sl_i - 1, sl_i}) do
            for _, ti in ipairs({tl_i - 1, tl_i}) do
                if si >= 1 and si <= #S
                    and ti >= 1 and ti <= #T then
                    local sv = S[si]
                    local tv = T[ti]
                    local d = math.abs(tv - sv) + math.min(math.abs(sv - x), math.abs(tv - x))
                    cur_min = math.min(cur_min, d)
                end
            end
        end
        return cur_min
    end
    for i=1,Q do
        x = io.read("n")
        local sl_i = find_leftmost_ge(S, x)
        local tl_i = find_leftmost_ge(T, x)
        print(search(x, sl_i, tl_i))
    end
end

main()


Measured memory_bytes: 16376
#include <iostream>/*{{{*/
#include <iomanip>
#include <string>
#include <map>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <bits/stdc++.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <queue>
#include <sstream>
#include <stack>
#include <deque>
#include <memory.h>
#include <exception>
#include <ctime>
#include <climits>
#include <list>
#include <bitset>
#include <cassert>
using namespace std;
#define rep_n(i, a, b) for (int i=(a); i<(b); i++)
#define rep(i, n) rep_n(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define ci1(a) cin>>a 
#define ci2(a, b) cin>>a>>b
#define ci3(a, b, c) cin>>a>>b>>c
#define ci4(a, b, c, d) cin>>a>>b>>c>>d
#define co1(a) cout<<a<<endl;
#define co2(a, b) cout<<a<<" "<<b<<endl;
#define co3(a, b, c) cout<<a<<" "<<b<<" "<<c<<endl;
#define co4(a, b, c, d) cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
typedef long long ll;/*}}}*/

int main() {
    int n, h;
    ci2(n, h);
    int a[n], b[n], amax=0;
    rep(i, n) ci2(a[i], b[i]), amax=max(amax, a[i]);
            ///*debug*/printf("%d\n", amax);

    sort(b, b+(sizeof(b)/sizeof(int)));
    ///*debug*/rep(i, n) co1(b[i]);

    int sum=0, cnt=0;

    for (int i=n-1; i>=0; i--) {
        if (b[i] > amax) {
            sum += b[i];
            cnt++;
            ///*debug*/printf("plus b %d\n", b[i]);
            if (sum>=h) {
                co1(cnt);
                goto END;
            }
        }
    }
            while(h>sum) {
                sum += amax;
                cnt++;
            ///*debug*/printf("plus a %d\n", amax);
                if (sum>=h) {
                    co1(cnt);
                    goto END;
                }
            }

END: return 0;


}


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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

template<typename T1,typename T2> using P = pair< T1, T2 >;
using Pii = P<int,int>;
using Pdd = P<double,double>;

struct edge{
    int src; int dst; int weight;
    edge() : src(0), dst(0), weight(0) {}
    edge(int s, int d, int w) : src(s), dst(d), weight(w) {}
};

using edges = V<edge>;
using graph = V<edges>;

void add_edge(edges &g,int s, int d, int w=1){g.pb(edge(s,d,w));}
void add_edge(graph &g,int s, int d, int w=1){g[s].pb(edge(s,d,w));}

int main(){
    int n,q;
    cin>>n>>q;
    graph G(n);
    Vi v(n,0);
    REP(i,n-1){
        int a,b;
        cin>>a>>b;
        a--; b--;
        add_edge(G,a,b);
        add_edge(G,b,a);
    }
    Vi p(q),x(q);
    REP(i,q) {
        cin>>p[i]>>x[i];
        p[i]--;
    }

    REP(i,q){
        v[p[i]] += x[i];
    }

    queue<Pii> que;
    que.push(mp(0,-1));
    while(!que.empty()){
        Pii node = que.front();
        int now_v = node.fi;
        int pre_v = node.se;
        que.pop();
        REP(i,G[now_v].size()){
            if(G[now_v][i].dst==pre_v) continue;
            v[G[now_v][i].dst] += v[G[now_v][i].src];
            que.push(mp(G[now_v][i].dst,now_v));
        }
    }

    REP(i,n) cout<<v[i]<<" ";
    cout<<endl;

    return 0;
}

Measured memory_bytes: 19632
inputLine = input().split()

X = int(inputLine[0])
Y = int(inputLine[1])

no = "No"
yes = "Yes"

if Y%2 == 1 :
  print(no)
else :
  table = [i*2+(X-i)*4 for i in range(X+1)] 
  if Y in table :
    print(yes)
  else:
    print(no)

Measured memory_bytes: 9188
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)


//0-index ??????????????¶?????°?????????(???????????? , ???) verified AOJ DSL_2_G, CODEFESTIVAL2015-D
template<class T>
class segtree{
private:
	vector<T> dat;
	vector<T> lazy;
	int _size;  //the number of leaves
	T _init;
	
public:
	segtree(int __size=0 , T init=numeric_limits<T>::max() ):_size(__size), _init(init), dat(4*__size,init), lazy(4*__size,init){
		if(__size==0)return ;
		int x=1;
		while(x<_size)x*=2;
		_size = x;
	}
	
	
	void update(int s,int t, T x ,int num=1,int a=0,int b=-1){
		if(b==-1)b=_size-1; //I couldn't "int b=_size".
		if(b<s||t<a)return ;
		if(s<=a&&b<=t){
			lazy[num]+=x;	//addition
			
			//dat[num] += x;					//minimum	isn't verified
			//dat[num] += x;					//maximum
			dat[num]+=x*(b-a+1);	//sum
			return ;
		}
		update(s,t,x,num*2+0,a,(a+b)/2);
		update(s,t,x,num*2+1,(a+b)/2+1,b);
		//dat[num] = lazy[num]+min(dat[num*2],dat[num*2+1]);	//minimum	isn't verified
		//dat[num] = lazy[num]+max(dat[num*2],dat[num*2+1]);	//maximum
		dat[num] = dat[num*2]+dat[num*2+1]+lazy[num]*(b-a+1);	//sum
	}
	
	
	// call find(s,t)
	T find(int s,int t,int num=1,int a=0,int b=-1){
		if(b==-1)b=_size-1; //I couldn't "int b=_size".
		if(b<s||t<a)return _init;
		if(s<=a&&b<=t)return dat[num];
		T l = find(s,t,num*2,a,(a+b)/2);
		T r = find(s,t,num*2+1,(a+b)/2+1,b);
		//return lazy[num]+min(l,r);					//minimum	isn't verified
		//return lazy[num]+max(l,r);					//maximum
		return l+r+lazy[num]*(min(b,t)-max(a,s)+1);	//sum
	}
	
	int size(){return _size;}
};


int main(){
	int n,q;
	cin>>n>>q;
	segtree<ll> st(n,0);
	
	rep(i,q){
		int p;
		cin>>p;
		if(!p){
			int s,t,x;
			cin>>s>>t>>x;
			s--,t--;
			st.update(s,t,x);
			//          rep(i,n)cout<<st.find(i,i)<<" ";cout<<endl;
		}else{
			int s,t;
			cin>>s>>t;
			s--,t--;
			cout<<st.find(s,t)<<endl;
		}
	}
}

Measured memory_bytes: 9164
n,a,b =map(int, input().split())
if (b-a)%2==0:
    print((b-a)//2)
else:
    if b-a==1:
        print(min(b-1,n-a))
    else:
        if (b-1)>=n-a:
            print((n-b)+1+((n-(a+n+1-b))//2))
        else:            
            print(a+((b-a-1)//2))

Measured memory_bytes: 3060
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

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

    int N = scanner.nextInt();
    int C = scanner.nextInt();

    List<int[]>[] lists = new List[C];
    for (int i = 0; i < C; i++) lists[i] = new ArrayList<>();
    for (int i = 0; i < N; i++) {
      int s = scanner.nextInt();
      int t = scanner.nextInt();
      int c = scanner.nextInt();
      lists[c - 1].add(new int[]{s, t});
    }

    List<Point> points = new ArrayList<>();
    for (List<int[]> l : lists) {
      l.sort(Comparator.comparingInt(o -> o[0]));
      for (int i = 0; i < l.size(); i++) {
        int[] seg = l.get(i);
        if (i == 0 || seg[0] != l.get(i - 1)[1]) {
          points.add(new Point(true, seg[0] - 1));
        }
        if (i == l.size() - 1 || seg[1] != l.get(i + 1)[0]) {
          points.add(new Point(false, seg[1]));
        }
      }
    }
    Collections.sort(points);

    int max = 0;
    int count = 0;
    for (Point p : points) {
      if (p.up) count++;
      else count--;
      if (count > max) max = count;
    }
    System.out.println(max);
  }

  static class Point implements Comparable<Point> {
    public final boolean up;
    public final int t;

    Point(boolean up, int t) {
      this.up = up;
      this.t = t;
    }

    @Override public int compareTo(Point o) {
      return t != o.t ? (t - o.t) : up ? 1 : -1;
    }

    @Override public String toString() {
      return "[" +  t + ", " + up + ']';
    }
  }
}


Measured memory_bytes: 95776
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

a,b=map(int,input().split())
if 1<=a<=9 and 1<=b<=9:
    print(a*b)
else:
    print(-1)


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

using namespace std;

#define pb push_back
#define mp make_pair
#define MOD ((int)(1e9) + 7)
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define filename "lynext"
#define freop freopen(filename ".cik","w",stdout);freopen(filename ".gir","r",stdin)
const long long int N = ((long long int)1e5) + 5;
const long long int M = ((long long int)1e3) + 5;
const long long int llinf = (long long int)1e18;
const int inf = INT_MAX;
typedef long long int lli;

lli n;
lli arr[N][3];
lli dp[N][3];

lli f (lli i, lli last)
{
	if (dp[i][last] != -1)
		return dp[i][last];
	lli t = -llinf;
	if (i == 1)
	{
		for (int j = 0; j < 3; j++)
		{
			t = max(t,f(i + 1,j) + arr[i][j]);
		}
		return dp[i][last] = t;
	}
	for (int j = 0; j < 3; j++)
	{
		if (last != j)
			t = max(t,f(i + 1,j) + arr[i][j]);
	}
	return dp[i][last] = t;
}

int main ()
{
	fast;
	//freop;
	cin >> n;
	memset(dp, -1, sizeof dp);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
			cin >> arr[i][j];
	}
	cout << f(1,0) << "\n";
}


Measured memory_bytes: 11264
#include <iostream>
using namespace std;
static const int MAX=100;
static const int INFTY=(1<<21);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int n,M[MAX][MAX];
int prim(){
    int minv;
    int d[MAX],color[MAX];
    for(int i=0;i<n;i++){
        d[i]=INFTY;
        color[i]=WHITE;
    }
    d[0]=0;
    color[0]=GRAY;
    while(1){
        minv=INFTY;
        int u=-1;
        for(int i=0;i<n;i++){
            if(minv>d[i]&&color[i]!=BLACK){
                u=i;
                minv=d[i];
            }
        }
        if(u==-1)break;
        color[u]=BLACK;
        for(int v=0;v<n;v++){
            if(color[v]!=BLACK&&M[u][v]!=INFTY){
             if(d[v]>d[u]+M[u][v]){
                 d[v]=d[u]+M[u][v];
                 color[v]=GRAY;
               }
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<i<<" "<<(d[i]==INFTY ? -1: d[i])<<endl;
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            M[i][j]=INFTY;
        }
    }
    int k,c,u,v;
    for(int i=0;i<n;i++){
        cin>>u>>k;
        for(int j=0;j<k;j++){
            cin>>v>>c;
            M[u][v]=c;
        }
    }
    prim();
    return 0;
}


Measured memory_bytes: 3120
/*
[agc036] C - GP 2
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int MAX_N = 1e6;
const int MAX_M = 5e5;
const int MOD = 998244353;

class gf {
public:
    int n;
    static int extgcd(int a, int b, int& x, int& y) {
        int d = a;
        if (b != 0) {
            d = extgcd(b, a % b, y, x);
            y -= (a / b) * x;
        } else {
            x = 1;
            y = 0;
        }
        return d;
    }
    static int mod_inv(int a, int m) {
        int x, y;
        extgcd(a, m, x, y);
        return (m + x) % m;
    }
    gf() : n(0) {}
    gf(int n) : n(n % MOD) {}
    gf operator+(const gf x) const { return gf((n + x.n) % MOD); }
    gf operator-(const gf x) const { return gf((n - x.n + MOD) % MOD); }
    gf operator*(const gf x) const { return gf((1LL * n * x.n) % MOD); }
    gf operator/(const gf x) const { return *this * x.inv(); }
    gf& operator+=(const gf x) { return *this = (*this + x); }
    gf inv() const { return gf(mod_inv(n, MOD)); }
};

int N, M;
gf fact[3 * MAX_M + MAX_N + 1];

gf combi(int n, int k) {
    return (n < 0 || k < 0 || n - k < 0) ? 0
                                         : fact[n] / (fact[k] * fact[n - k]);
}

gf calc(int s, int m, int n) {
    gf ret = 0;
    for (int i = 0; i <= m; i++) {
        if ((s - i) % 2 != 0) {
            continue;
        }
        ret += combi(n, i) * combi((s - i) / 2 + n - 1, n - 1);
    }
    return ret;
}

ll solve() {
    fact[0] = 1;
    for (int i = 1; i <= 3 * MAX_M + MAX_N; i++) {
        fact[i] = fact[i - 1] * i;
    }

    gf ans = calc(3 * M, M, N) - (calc(M, M, N) - calc(M, M, N - 1)) * N;

    return ans.n;
}

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

    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 9984
from collections import deque

s=input()
q=int(input())
d=deque()
d.append(s)
m=1
for i in range (q):
    a=list(input().split())
    if a[0]=="1":
        m=m*(-1)
    else:
        if m==1:
            if a[1]=="1":
                d.appendleft(a[2])
            else:
                d.append(a[2])
        else:
            if a[1]=="2":
                d.appendleft(a[2])
            else:
                d.append(a[2])
s="".join(d)


print(s[::m])


Measured memory_bytes: 67160
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define taskname "A"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 5e3 + 5;
const int logn = log2(maxn) + 1;
const int inf = 1e9 + 1;
int n,a[maxn];
vector<int> adj[maxn];
ll dp[maxn][maxn];
bool dp1[maxn][maxn];
ll tmp[maxn];
bool tmp1[maxn];
int sub[maxn];

void dfs(int u , int par){
    dp1[u][0] = (a[u] > 0);
    dp[u][0] = a[u];
    sub[u] = 1;
    for(auto c : adj[u]){
        if(c == par)continue;
        dfs(c , u);
        fill_n(tmp,maxn,1e18);
        fill_n(tmp1,maxn,0);
        for(int i = 0 ; i <= sub[u] ; ++i){
            for(int j = 0 ; j <= sub[c] ; ++j){
                if(dp[c][j] < 0 || dp1[c][j])tmp[i + j + 1] = min(tmp[i + j + 1] , dp[u][i]);
                tmp[i + j] = min(tmp[i + j] , dp[u][i] + dp[c][j]);
                if(dp1[c][j] && dp1[u][i])tmp1[i + j] = 1;
                if(dp1[u][i] && (dp[c][j] < 0 || dp1[c][j]))tmp1[i + j + 1] = 1;
            }
        }
        sub[u] += sub[c];
        for(int i = 0 ; i <= sub[u] ; ++i){
            dp[u][i] = tmp[i];
            dp1[u][i] = tmp1[i];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP" , "r")){
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    fill_n(&dp[0][0],maxn*maxn,1e18);
    memset(dp1,0,sizeof dp1);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)cin >> a[i];
    for(int i = 1 ; i < n ; ++i){
        int u , v;cin >> u >> v;
        adj[u].pb(v);adj[v].pb(u);
    }
    dfs(1,0);
//    cout << dp[1][2] << " " << dp1[1][2] << endl;
    for(int i = 0 ; i <= n ; ++i){
        if(dp[1][i] < 0 || dp1[1][i])return cout << i , 0;
    }
}


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

int main(){
    long long n;
    cin >> n;
    long long ans = 0;
    rep(i,n+1){
        if(i % 3 != 0 && i % 5 != 0){
            ans += i;
        }
    }
    cout << ans << endl;
}

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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

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

#ifdef DEBUG
#define DBG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)
#else
#define DBG(fmt, ...)
#endif

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    ll X;

    cin >> X;
    if( X >= 30 ){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3632
#include<iostream>
using namespace std;
class itp1_2c{
public:void sort(int first,int second,int third){
  int tmp;
  if(first>second){
    tmp=first;
    first=second;
    second=tmp;
  }
  if(second>third){
    tmp=second;
    second=third;
    third=tmp;
  }
  if(first>second){
    tmp=first;
    first=second;
    second=tmp;
  }
  cout<<first<<" "<<second<<" "<<third<<endl;
}
};
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  itp1_2c run;
  run.sort(a,b,c);
  return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <list>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

int n;

struct Point 
{
	double x, y;
};

void kock(int n, Point p1, Point p2) {
	if (n == 0) return;

	Point s, u, t;
	double sixty = M_PI *60/180;

	s.x = (2 * p1.x + p2.x) / 3;
	s.y = (2 * p1.y + p2.y) / 3;
	t.x = (p1.x + 2 * p2.x) / 3;
	t.y = (p1.y + 2 * p2.y) / 3;
	u.x = (t.x - s.x)*cos(sixty) - (t.y - s.y)*sin(sixty) + s.x;
	u.y = (t.x - s.x)*sin(sixty) + (t.y - s.y)*cos(sixty) + s.y;

	kock(n - 1, p1, s);
	printf("%.8f %.8f\n", s.x, s.y);
	kock(n - 1, s, u);
	printf("%.8f %.8f\n", u.x, u.y);
	kock(n - 1, u, t);
	printf("%.8f %.8f\n", t.x, t.y);
	kock(n - 1, t, p2);

}

int main(void) {

	Point a, b;
	a.x = 0;
	a.y = 0;
	b.x = 100;
	b.y = 0;

	cin >> n;

	printf("%.8f %.8f\n", a.x, a.y);
	kock(n, a, b);
	printf("%.8f %.8f\n", b.x, b.y);

	return 0;
}

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

using namespace std;

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pi >
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define all(n) n.begin(), n.end()

#define FROMTO(var, from, to) for (register int var = (from), var##down = ((int)(to)) < ((int)(from));var##down ? (var >= (int)(to)) : (var <= (int)(to));var##down ? var-- : var++)
#define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
#define DOWNTO(var, from, to) for (register int var = (from); var >= ((int)to); var--)
#define FOR(var, to)          UPTO(var, 0, (to)-1)
#define DOWN(var, from)       DOWNTO(var, (from)-1, 0) 

#define INIT(var, val) FOR(i,countof(var)) var[i] = val
#define INPUT(var) FOR(i,countof(var)) cin >> var[i]
#define INPUT1(var) FOR(i,countof(var)) cin >> var[i], var[i]--

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)

#define MOD 1000000007
#define INF ((1 << 30)-1)
#define LINF ((1LL << 62)-1)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

struct Comb {
    vector<vector<s64> > data;
    Comb(int n) { // O(n^2)
        data = vector<vector<s64> >(n+1,vector<s64>(n+1,1));
        UPTO(i,1,n) {
            FOR(j,i+1) {
                if (!j || j == i) data[i][j] = 1;
                else data[i][j] = data[i-1][j-1] + data[i-1][j];
            }
        }
    }
    
    s64 ncr(int n, int r) {
        return data[n][r];
    }
};

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

int int_less(const void *a, const void *b) {
  return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
  return (*((const int*)b) - *((const int*)a));
}

int main() {
    int n = ri();
	int k = ri();
	int a[n];
	INPUT(a);
	SORT(a);
	int res = INF;
	FOR(i,n) {
		if (i + k > n) break;
		res = min(res,a[i+k-1] - a[i]);
	}
	cout << res << endl;
    return 0;
}


Measured memory_bytes: 1020
#include<iostream>

using namespace std;

int main()
{
     int n, count = 0;
     cin >> n;
     string s;
     cin >> s;
     for(int i = 0; i < n-2; i++)
     {
         if(s[i] == 'A')
         {
             if(s[i+1] == 'B' && s[i+2] == 'C')
                count++;
         }
     }
     cout << count;
}


Measured memory_bytes: 3592
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>

#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
using namespace std;

char s[100001];

signed main()
{
	cin >> s;
	int N = strlen(s);

	vector<int> v;
	for (int i = 0; i < N; i++)
	{
		if (s[i] != 'x')
		{
			v.push_back(i);
		}
	}

	if (v.size() == 0)
	{
		cout << 0 << endl;
		return 0;
	}

	int vsize = v.size();

	for (int i = 0; i < vsize / 2; i++)
	{
		if (s[v[i]] != s[v[vsize - 1 - i]])
		{
			cout << -1 << endl;
			return 0;
		}
	}

	int ans = 0;

	int a0 = v[0];
	int b0 = (N - 1) - v[vsize - 1];
	ans += abs(a0 - b0);
	int loop = vsize / 2 + ((vsize % 2 == 1) ? 1 : 0);
	for (int i = 1; i < loop; i++)
	{
		int a = v[i] - v[i - 1] - 1;
		int b = v[(vsize - 1) - i + 1] - v[(vsize - 1) - i] - 1;
		ans += abs(a - b);
	}

	cout << ans << endl;
}



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

int main(){
    int a,b,c,k;
    cin >> a >> b >> c;
    cin >> k;
    if(a >= b && a >= c){
        cout << a*pow(2,k) + b + c;
    }else if(b >= c){
        cout << a + b*pow(2,k) + c;
    }else{
        cout << a + b + c*pow(2,k);
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;

double dist(int i, int j, double x[], double y[]);

double dist(int i, int j, double x[], double y[]) {
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return sqrt(dx * dx + dy * dy);
}

int main(){
	/*input*/
	int n;
	cin >> n ;
	double x[8];
	double y[8];
	for(int i =0; i < n; i++) cin >> x[i] >> y[i];

	/*calc*/
	int fact=1;
	double sum = 0.0;
	double ans = 0.0;
	for(int i=2; i<=n; i++) {
	    fact *= i;
	 }
	vector<int> v(n);
	for(int i = 0; i < n; i++) v[i] = i;
	do {
		for(int i = 0; i < n-1; i++) {
			sum += dist(v[i],v[i+1],x,y);
		}
	} while(next_permutation(v.begin(), v.end()));
	ans = sum / fact;

    /*output*/
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>

using namespace std;

int main(){
	while(true){
		int n, x;
		cin >> n >> x;
		if(n==0){
			break;
		}
		int cnt = 0;
		for(int i = 1; i <= n; i++){
			for(int j = i+1; j <= n; j++){
				for(int k = j+1; k <= n; k++){
					if(i+j+k==x){
						cnt++;
					}
				}
			}
		}
		cout << cnt << "\n";
	}
}


Measured memory_bytes: 3116
n = int(input())
t,a = map(int,input().split())
h = list(map(int,input().split()))
temp = []
ans = []
for i in range(n):
    temp += [t - 0.006*h[i]]
    ans += [abs(a - (t - 0.006*h[i]))]
print(ans.index(min(ans))+1)


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

typedef long long ll;
typedef pair<int,int> P;
typedef map<int,int> M;
typedef vector<int> V;
typedef queue<int> Q;
typedef pair<long,long> PLL;
typedef map<long,long> MLL;
typedef vector<long> VLL;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
/*--------------------------------------------*/

int main(){
    string s;cin>>s;
    int flag=0;
    rep(i,26){
        int flag2=0;
        rep(j,s.size()){
            if(i==s[j]-'a')flag2=1;
        }
        if(flag2==0){
            flag=1;
            char c=i+'a';
            printf("%c\n",c);
            return 0
;
        }
    }
    if(flag==0)printf("None");
}


Measured memory_bytes: 512
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

int main() {
    int n;
    cin >> n;
    vi a(n);
    rep(i,n) cin >> a[i];
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if((i + 1) % 2 == 1 && a[i] %2 == 1) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define fi first
#define se second
#define INF 1000000009
#define LLINF 1000000000000000009LL
using ll = long long;

int dp[100009];

int main(){
  int n;
  cin>>n;
  vector<int>h(n);
  rep(i,n)cin>>h[i];
  rep(i,n)dp[i]=INF;
  dp[0]=0;
  rep(i,n){
    if(i+1<n)dp[i+1]=min(dp[i+1],dp[i]+abs(h[i]-h[i+1]));
    if(i+2<n)dp[i+2]=min(dp[i+2],dp[i]+abs(h[i]-h[i+2]));
  }
  cout<<dp[n-1]<<endl;
  return(0);
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
#define REP(i,n) for(int i=0; i<n;i++)
int main(){
    char n[3];
    cin >> n ;
    REP(i,3){
        if(n[i] == '1')
            n[i] = '9';
        else if(n[i] == '9')
            n[i] = '1';
    }
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <bitset>
#include <time.h>
#include <set>
#include <algorithm>
#define ll long long
using namespace std;


int main() {
    ll A,B,C;
    cin>>A>>B>>C;
    
    ll d1 = (A&1 ? 1 : 0);
    ll d2 = (B&1 ? 1 : 0);
    ll d3 = (C&1 ? 1 : 0);
    
    cout << min(B*C*d1, min(A*C*d2, A*B*d3)) << endl;
    
    
}

Measured memory_bytes: 256
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1

if 1 not in a:
	dp[1] = 1
    
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])

Measured memory_bytes: 18888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n;
    cin >> n;
    ll a[n], b[n];
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, n) cin >> b[i];
    int d[n];
    ll sum = 0;
    rep(i, 0, n) {
        d[i] = a[i] - b[i];
        sum += d[i];
    }

    if (sum < 0) {
        cout << -1 << endl;
        return 0;
    }

    sort(d, d + n, greater<int>());
    int check[n];
    rep(i, 0, n) check[i] = d[i];

    int to = n - 1;
    rep(i, 0, n) {
        while (d[i] > 0) {
            if (d[to] < 0) {
                int tmp = min(d[i], -d[to]);
                d[i] -= tmp;
                d[to] += tmp;
            }
            if (d[to] >= 0) to--;
            if (to == -1) break;
        }
        if (to == -1) break;
    }

    int ans = 0;
    rep(i, 0, n) {
        if (d[i] != check[i]) ans++;
    }

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


Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <cmath>
#include <climits>
int main(){
   int a[100];
   int n,ans=INT_MAX;

   std::cin>>n;

   for(int i=0;i<n;++i){
       std::cin>>a[i];
   }

   for(int i=-100;i<=100;++i){
       int tmp=0;
       for(int j=0;j<n;++j){
            tmp+=std::pow(i-a[j],2);                
       }
       if(ans>tmp){
           ans=tmp;

       }

   }
   std::cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const double PI=acos(-1);

template<typename T>
istream& operator>> (istream& is, vector<T> &vec){
    for(T& x: vec) is >> x;
    return is;
}

int main(){
    ll  h, w; cin >> h >> w;
    char field[101][101];
    ll fcnt[101][101];
    fill(fcnt[0], fcnt[101], 999);
    
    rep(i, h+1){
        rep(j, w+1){
            if(i == h || j == w) field[i][j] = 'X';
            else cin >> field[i][j];
        }
    }

    if(field[h-1][w-1] == '#') fcnt[h-1][w-1] = 1;
    else fcnt[h-1][w-1] = 0;
    for(ll x = w-1; x >= 0; --x){
        for(ll y = h-1; y >= 0; --y){
            if(x == w-1 && y == h-1) continue;
            char now = field[y][x], down = field[y+1][x], right = field[y][x+1];
            if(now == '#'){
                if(right == down){
                    fcnt[y][x] = min(fcnt[y+1][x], fcnt[y][x+1]);
                    if(right == '.') 
                        fcnt[y][x]++;
                }else if(now == right && now != down) 
                    fcnt[y][x] = min(fcnt[y][x+1], fcnt[y+1][x]+1);
                else if(now != right && now == down) 
                    fcnt[y][x] = min(fcnt[y][x+1]+1, fcnt[y+1][x]);
                else if(right == 'X'){
                    if(now == down) 
                        fcnt[y][x] = fcnt[y+1][x];
                    else 
                        fcnt[y][x] = fcnt[y+1][x] + 1;
                }else if(down == 'X'){
                    if(now == right) 
                        fcnt[y][x] = fcnt[y][x+1];
                    else 
                        fcnt[y][x] = fcnt[y][x+1] + 1;
                }
            }
            else{
                if(right == 'X') 
                    fcnt[y][x] = fcnt[y+1][x];
                else if(down == 'X') 
                    fcnt[y][x] = fcnt[y][x+1];
                else 
                    fcnt[y][x] = min(fcnt[y+1][x], fcnt[y][x+1]);
            }
        }
    }

    /*
    rep(i, h){
        rep(j, w){
            printf("%c(%2lld)", field[i][j], fcnt[i][j]);
        }
        cout << "\n";
    }
    */
    
    printf("%lld\n", fcnt[0][0]);
        
    return 0;
}

Measured memory_bytes: 384
using System;
class Program
{
	static void Main(string[] args)
	{
		string[] input = Console.ReadLine().Split(' ');
		int a = int.Parse(input[0]);
		int b = int.Parse(input[1]);
        if(a >= b){
          Console.WriteLine("10");
        }else{
          Console.WriteLine("0");
        }
	}
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
using ll = long long;
const int INF = 1e9;
double temp_start = 100.0;
double temp_end = 0.001; 
int climb_loop = 300000;
double temp;

int main(){
  int seed = 12345;
  mt19937 eng(seed);
  uniform_real_distribution<> uniform_01;

  // input
  int D;
  cin >> D;
  int c[26];
  rep(i,26) cin >> c[i];
  int s[D+1][26];
  rep(i,D) rep(j,26) cin >> s[i+1][j];
  
  // define parameter
  int last[D+1][26];
  int t[D+1];
  rep(i,D+1) rep(j,26) last[i][j] = 0;
  
  // calculate initial content climbing
  int content = 0;
  for(int day = 1; day <= D; day++) {
    int content_after = -INF;
    int best_kind = 0;
    rep(kind,26) {
      int res = content + s[day][kind];
      rep(j,26) {
        if(j == kind) last[day][j] = day;
        else last[day][j] = last[day-1][j];
        res -= c[j] * (day - last[day][j]);
      }
      if(res > content_after) {
        best_kind = kind;
        content_after = res;
      }
    }
    t[day] = best_kind;
    content = content_after;
    rep(j,26) {
      if(j == t[day]) last[day][j] = day;
      else last[day][j] = last[day-1][j];
    }
  }
   
  // simulated annealing
  rep(x,climb_loop) {
    int d = (eng() % D) + 1;
    int q = eng() % 26;
    temp = temp_start + (temp_end - temp_start)*x/climb_loop;
    int diff = s[d][q] - s[d][t[d]];
    int cur = d;
    while(cur <= D && last[cur][t[d]] == d) {
      diff -= c[t[d]] * (d - last[cur-1][t[d]]);
      last[cur][t[d]] = last[cur-1][t[d]];
      cur++;
    }
    cur = d;
    while(cur <= D && last[cur][q] < d) {
      diff += c[q] * (d - last[cur][d]);
      last[cur][q] = d;
      cur++;
    }
    if(diff > 0 || uniform_01(eng) < exp((double)diff/temp)) {
      t[d] = q;
      content += diff;
    } else {
      int day = d;
      while(day <= D && last[day][t[d]] < d) {
        last[day][t[d]] = d;
        day++;
      }
      day = d;
      while(day <= D && last[day][q] == d) {
        last[day][q] = last[day-1][q];
        day++;
      }
    }
  }
  // output
  for(int day = 1; day <= D; day++) cout << t[day]+1 << endl;
  return 0;
}


Measured memory_bytes: 4328
// Author: getharshkumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll l, r, m = M;
    cin >> l >> r;
    if (r - l > 3000)
        return cout << 0, 0;
    for (ll i = l; i < r; i++)
        for (ll j = i + 1; j <= r; j++)
            m = min(m, (i * j) % 2019);
    cout << m;
    return 0;
}

Measured memory_bytes: 256
#include <stack>

#include <stdio.h>

int main(int argc, char** argv)
{
  std::stack<int> stack;

  int i;

  while (fscanf(stdin, "%d", &i) == 1) {
    if (i) {
      stack.push(i);
    }
    else {
      fprintf(stdout, "%d\n", stack.top());
      
      stack.pop();
    }
  }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 20;
int n,a[N];

map<pa,ll>f[N][N];
inline ll dfs(int l,int r,int x,int y){
	if (f[l][r].count(mp(x,y))) return f[l][r][mp(x,y)];
	if (l+1==r) return 0;
	ll ret=1e18;
	For(i,l+1,r-1) ret=min(ret,dfs(l,i,x,y+x)+dfs(i,r,x+y,y)+1ll*a[i]*(x+y));
	return f[l][r][mp(x,y)]=ret;
}

int main(){
	n=read();
	For(i,1,n) a[i]=read();
	printf("%lld\n",dfs(1,n,1,1)+a[1]+a[n]);
}

Measured memory_bytes: 20060
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

ll N, X;

ll gcd(ll a, ll b) {
	if(b == 0) return -a + N;
	else return gcd(b, a % b) + a / b * b * 2;
}

void solve() {
	cin >> N >> X;
	cout << gcd(N - X, X) << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 256
def resolve():
    N = int(input())
    X = list(map(int, input().split()))

    ans = 100000000000

    for p in range(1, 101):
        tmp = 0
        for x in X:
            tmp = tmp + ((x - p) ** 2)

        ans = min(tmp, ans)

    print(ans)
    
resolve()

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

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



template<class T>
void printarray(vector<T> a){
	REP(i,a.size())cout << a[i] << " ";
	cout<< endl;
}

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

void solvecase(){
	string s,t;
	int n;
	cin >> n;
	cin >> s >> t;
	VI p;
	p = prefix_function(t+"#"+s);
	cout << 2*n - p[2*n] << endl;


}
int main(){
	int cases = 1;
	while(cases--){
		solvecase();
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int ll
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define rev(a) (a).rbegin(),(a).rend()
#define pll pair<ll,ll>
#define rep(i,a,b) for(long long i = (a); i < (b); i++)
#define derep(i,a,b) for(long long i = (a); i>=(b); i--)
ll modi = 1000000007;

bool cp(ll n){
    if(n == 1)return false;
    else if(n == 2)return true;
    else if(n ==3)return true;
    for(int i  = 2; i*i<=n; i++){
        if(n%i == 0){
            return false;
        }
    }
    return true;
}
void SforPrime(int n)
{
	bool prime[n+1];
	memset(prime, true, sizeof(prime));

	for (int p=2; p*p<=n; p++)
	{
		if (prime[p] == true)
		{
			for (int i=p*p; i<=n; i += p)
				prime[i] = false;
		}
	}
}
ll calPower(ll val, ll n){
    ll i = 1;
    ll ind = 1;
    ll prev = val;
    while(val<=n){
        if(n%val == 0)ind = i;
        val  = val*prev;
        i++;
    }
    return i-1;
}
int32_t main(){
    //130016239756757
    int n;
    cin>>n;
    int divi = n/500;
    divi *= 1000;
    int rem = (n%500)/5;
    rem *= 5;
    cout<<rem + divi<<endl;
}

Measured memory_bytes: 256