akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

using namespace std;

typedef long double ld;
typedef long long ll;

#define sz(x) (int)(x).size()
#define pb push_back
#define mp make_pair
#define f first
#define s second

template<typename T, typename U> bool ckmin(T &a, U b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool ckmax(T &a, U b){ return b > a ? a = b, true : false; }

const ll MOD = 1e9 + 7;

ll n, k, res = 0;
vector<ll> pos, neg, zer;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for(int i = 0; i < n; ++i){
        ll cur; cin >> cur;
        if(cur > 0) pos.pb(cur);
        else if(cur < 0) neg.pb(cur);
        else zer.pb(cur);
    }
    if(sz(pos) + sz(neg) < k){
        cout << 0;
        return 0;
    }
    bool high = false;
    for(ll i = min(sz(pos) * 1LL, k); i >= 0; --i){
        if(k - i <= sz(neg) && (k - i)%2 == 0) high = true;
    }
    sort(pos.begin(), pos.end(), greater<ll>());
    sort(neg.begin(), neg.end());
    // for(auto i : neg) cout << i << " ";
    // cout << "\n";
    if(high == false){
        if(sz(zer)){cout << 0; return 0;}
        ll res = 1, p1 = 0, p2 = 0;
        reverse(pos.begin(), pos.end());
        reverse(neg.begin(), neg.end());
        while(p1 + p2 < k){
            if(p1 == sz(pos)){
                res *= neg[p2];
                p2++;
                res %= MOD;
                continue;
            }
            if(p2 == sz(neg)){
                res *= pos[p1];
                p1++;
                res %= MOD;
                continue;
            }
            if(pos[p1] < abs(neg[p2])){
                res *= pos[p1];
                p1++;
                res %= MOD;
            }
            else{
                res *= neg[p2];
                p2++;
                res %= MOD;
            }
        }
        // cout << res;
        cout << ((res%MOD) + MOD)%MOD;
        return 0;
    }
    // num neg, num pos
    ll cur2 = 0, cur = 0;
    while(cur2 + 2 <= sz(neg) && cur2 + 2 <= k) cur2 += 2;
    for(int i = 0; i < sz(pos); ++i){
        if(cur2 + cur < k) cur++;
        else break;
    }
    while(cur2 - 2 >= 0 && cur + 2 <= sz(pos)){
        if(pos[cur] * pos[cur + 1] >= neg[cur2 - 2] * neg[cur2 - 1]){
            cur2 -= 2;
            cur += 2;
        }
        else break;        
    }
    ll res = 1;
    for(int i = 0; i < cur; ++i){
        res *= pos[i];
        res %= MOD;
    }
    for(int j = 0; j < cur2; ++j){
        res *= neg[j];
        res %= MOD;
    }
    cout << ((res%MOD) + MOD)%MOD;
    return 0;
}

Measured memory_bytes: 5592
N=int(input())
A=sorted(map(int,input().split()))
MAX=A[-1]
divisor=[0]*(MAX+1)
for a in A:
    if divisor[a]!=0:
        divisor[a]=2
    for i in range(a,MAX+1,a):
        divisor[i]+=1
count=0
for a in A:
    if divisor[a]==1:
        count+=1
print(count)

Measured memory_bytes: 32376
#pragma region RegionDefs
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,l,r) for(int i=(l),i##_len=(r);i<i##_len;++i)
#define repr(i,l,r) for(int i=(r)-1,i##_left=(l);i>=i##_left;--i)
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
const ll INF = 1e9;
template<class T=ll> using V = vector<T>;
template<class T=ll> using PQ = priority_queue<T>;
template<class T=ll> using PQG = priority_queue<T, V<T>, greater<T>>;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail) { cin >> head; in(move(tail)...); }
#define IN(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
template<class T>bool chmax(T &a, const T &b) {if (a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a>b) {a=b; return 1;} return 0;}
template<class T>
string join(vector<T>& v, string delim="") { ostringstream os; rep(i,v.size())i?os<<delim<<v[i]:os<<v[0]; return os.str(); }
#pragma endregion RegionDefs

void solve()
{
    IN(a, b, c, k);
    while (b <= a) {
        b *= 2;
        --k;
    }
    while (c <= b) {
        c *= 2;
        --k;
    }
    if (k < 0) cout << "No" << endl;
    else cout << "Yes" << endl;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

Measured memory_bytes: 3648
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;

int main() {
  string S; cin >> S;
  if (S[2] == S[3] && S[4] == S[5]) cout  << "Yes" << endl;
  else                              cout  << "No" << endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define REP(i, n) for(long long i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
 
int main() {
  char a;
  cin >> a;
  if (a == 'a' || a == 'i' || a == 'u' || a == 'e' || a== 'o') {
    cout << "vowel";
  } else {
    cout << "consonant";
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

struct edge {
    int a,b; // from a to b
    ll len;
    edge(int a,int b,ll l):a(a),b(b),len(l) {}
};

// return value is {} if there is a negative cycle.
/* detect only if a certain node(goal) is reachable
      from a negative cycle (if goal != -1) */
// detect any negative cycles (if goal == -1)
vector<ll> bellman_ford(int n,const vector<edge>& v,int start,int goal=-1) {
    vector<ll> dist(n,linf);
    dist[start] = 0;
    if(goal == -1) {
        rep(i,n) {
            for(auto e : v) {
                if(dist[e.a] < linf && chmin(dist[e.b],dist[e.a]+e.len)) {
                    if(i == n-1) return {};
                }
            }
        }
    } else {
        rep(i,n*2) {
            for(auto e : v) {
                if(dist[e.a] < linf && chmin(dist[e.b],dist[e.a]+e.len)) {
                    if(i >= n-1 && e.b == goal) return {};
                    else if(i >= n-1) dist[e.b] = -linf;
                }
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,m,p;
    cin >> n >> m >> p;
    vector<edge> ve;
    rep(_,m) {
        int a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        c -= p;
        ve.eb(a,b,-c);
    }
    vl dist = bellman_ford(n,ve,0,n-1);
    if(dist.size() == 0) {
        cout << -1 << endl;
    } else {
        cout << max(0LL,-dist[n-1]) << endl;
    }
}


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

vector<int> d;
vector<vector<pair<int, int>>> edge;

void dijkstra(int s){
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, s));

	while(!pq.empty()){
		int cost = pq.top().first;
		int v = pq.top().second;
		pq.pop();

		if(d[v] != 1) continue;

		d[v] = cost;

		for(auto e : edge[v]){
			if(d[e.second] == 1){
				pq.push(make_pair(cost + e.first, e.second));
			}
		}
	}
}

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

	d.resize(n, 1);
	edge.resize(n);
	for(int i=0; i<n; ++i){
		int v, k; cin >> v >> k;
		for(int l=0; l<k; ++l){
			int a, c; cin >> a >> c;
			edge[v].push_back(make_pair(-c, a));
		}
	}

	dijkstra(0);

	for(int i=0; i<n; ++i){
		cout << i << " " << -d[i] << endl;
	}
}



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

int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		string p,str,tmp;
		cin >> p >> str;
		for(int i = p.size()-1; i >= 0; i--){
			if(p[i] == 'J'){
				tmp = str;
				str[0] = tmp[str.size()-1];
				for(int j = 1; j < str.size(); j++) str[j] = tmp[j-1];
			} else if(p[i] == 'C'){
				tmp = str;
				for(int j = 0; j < str.size()-1; j++) str[j] = tmp[j+1];
				str[str.size()-1] = tmp[0];
			} else if(p[i] == 'E'){
				tmp = str;
				if(str.size()%2==0){
					for(int j = 0; j < str.size()/2; j++) str[j] = tmp[j+str.size()/2];
					for(int j = str.size()/2; j < str.size(); j++) str[j] = tmp[j-str.size()/2];
				} else{
					for(int j = 0; j < str.size()/2; j++) str[j] = tmp[j+str.size()/2+1];
					for(int j = str.size()/2+1; j < str.size(); j++) str[j] = tmp[j-str.size()/2-1];
				}
			} else if(p[i] == 'A'){
				tmp = str;
				for(int j = 0; j < str.size(); j++){
					str[j] = tmp[str.size()-1-j];
				}
			} else if(p[i] == 'P'){
				for(int j = 0; j < str.size(); j++){
					if(0<=str[j]-'0'&&str[j]-'0'<=9){
						if(str[j]-'0' == 0) str[j] = '9';
						else str[j]--;
					}
				}
			} else if(p[i] == 'M'){
				for(int j = 0; j < str.size(); j++){
					if(0<=str[j]-'0'&&str[j]-'0'<=9){
						if(str[j]-'0' == 9) str[j] = '0';
						else str[j]++;
					}
				}
			}
		}
		cout << str << endl;
	}
}

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

if n == 100000:
  print(90909)
elif 10000 <= n <= 99999:
  print(909 + n - 9999)
elif 1000 <= n <= 9999:
  print(909)
elif 100 <= n <= 999:
  print(9 + n - 99)
elif 10 <= n <= 99:
  print(9)
else:
  print(n)

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

int main() {
    // int n;
    // vector<int> a(n);
    // for(int i = 0; i < n; i++) {
    //     cin >> a[i];
    // }
    string s;
    bool ret = true;
    cin >> s;
    for(int i = 0; i < s.size(); i++) {
        if (i % 2 == 0) {
            if (!(s[i] == 'R' || s[i] == 'U' || s[i] == 'D')) {
                ret = false;
                break;
            }
        }
        if (i % 2 == 1) {
            if (!(s[i] == 'L' || s[i] == 'U' || s[i] == 'D')) {
                ret = false;
                break;
            }
        }
    }
    string out = ret ? "Yes" : "No";
    cout << out << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1,0,-1,-1,-1,0,1,1};
int dy[]={1,1,1,0,-1,-1,-1,0};


int state[1010];
int point[1010];

int main(){
    int n,m,h,k;
    while(true){
        cin >> n >> m >> h >> k;
        if(n == 0)break;
        vector<P> v;
        vector<P> inf;
        for(int i = 1;i <= n;i++){
            cin >> point[i];
        }
        for(int j = 0;j < m;j++){
            int a,b;
            cin >> a >> b;
            v.push_back(P(b,a));
        }
        sort(v.begin(),v.end());
        for(int i = 1;i <= n;i++)state[i] = i;
        for(int i = 0;i < m;i++){
            int a = v[i].second;
            int tmp = state[a];
            state[a] = state[a+1];
            state[a+1] = tmp;
            inf.push_back(P(state[a],state[a+1]));
        }
        int ans = 0;
        int tmpans = 0;
        for(int i = 1;i <= n;i++){
            if(state[i] <= k)tmpans += point[i];
        }
        ans = tmpans;
        for(int i = 0;i < m;i++){
            int a = inf[i].first,b = inf[i].second;
            if(a <= k && b <= k)continue;
            if(a > k && b > k)continue;
            if(a > b){
                int tmp = a;
                a = b;
                b = tmp;
            }
            int ap,bp;
            for(int j = 1;j <= n;j++){
                if(state[j] == a) ap = j;
                if(state[j] == b) bp = j;
            }
            ans = min(ans,tmpans + point[bp] - point[ap]);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 5140
import java.util.*;
import java.io.*;
public class Main{
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                Map hs = new HashMap();
                PrintWriter ou = new PrintWriter(System.out);
                int a = Integer.parseInt(sc.next());
                int b = Integer.parseInt(sc.next());
                int x = Integer.parseInt(sc.next());
                sc.close();
                if(a * a * b > 2 * x) ou.print(Math.atan(a * b * b / 2.0 / x) / Math.PI * 180 + "\n");
                else ou.print(Math.atan(2.0 * (a * a * b - x) / a / a / a) / Math.PI * 180 + "\n");
                ou.flush();
        }
}

Measured memory_bytes: 38652
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#define lli long long int
#define uli unsigned long long int
#define inf 999999999999999999
#define rep(i,n,m) for(lli i=(lli)(n);i<(lli)(m);++i)
#define reep(i,n,m) for(int i=(int)(n);i<=(int)(m);++i)
#define per(i,m,n) for(lli i=(int)(m)-1;i>=(int)(n);--i)
#define st(n) sort(n.begin(), n.end())
#define rev(n) reverse(n.begin(),n.end())
#define ou(S) cout << S << endl
using namespace std;
int main(){
  int i,sum=0;
  string s;
  cin>>s;
  rep(i,0,s.size()){
    if(s.at(i)=='+')++sum;
    else --sum;
  }
  ou(sum);
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main() {
  int n;
  int *data;
  scanf("%d\n",&n);
  data = (int*)malloc(sizeof(int)*n);
  for(int i=0; i<n; i++) scanf("%d",&data[i]);
  int max = 0, index;
  for(int i=0; i<n; i++) if(data[i] > max) {max = data[i];index=i;}
  int a = 0;
  for(int i=0; i<n; i++) if(i != index) a += data[i];
  if(a > max)printf("Yes\n");
  else printf("No\n");
  return 0;
}

Measured memory_bytes: 128
import java.io.*;
import java.nio.CharBuffer;
import java.util.ArrayList;
import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {
        SimpleScanner scanner = new SimpleScanner(System.in);
        PrintWriter writer = new PrintWriter(System.out);

        int n = scanner.nextInt();
        ArrayList<Restaurant> restaurants = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            String city = scanner.next();
            int score = scanner.nextInt();
            restaurants.add(new Restaurant(city, score, i));
        }
        restaurants.sort((o1, o2) -> o1.city.equals(o2.city) ? o2.score - o1.score : o1.city.compareTo(o2.city));
        for (int i = 0; i < n; ++i)
            writer.println(restaurants.get(i).index + 1);
        writer.close();
    }

    private static class SimpleScanner {

        private static final int BUFFER_SIZE = 10240;

        private Readable in;
        private CharBuffer buffer;
        private boolean eof;

        SimpleScanner(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
            buffer = CharBuffer.allocate(BUFFER_SIZE);
            buffer.limit(0);
            eof = false;
        }


        private char read() {
            if (!buffer.hasRemaining()) {
                buffer.clear();
                int n;
                try {
                    n = in.read(buffer);
                } catch (IOException e) {
                    n = -1;
                }
                if (n <= 0) {
                    eof = true;
                    return '\0';
                }
                buffer.flip();
            }
            return buffer.get();
        }

        void checkEof() {
            if (eof)
                throw new NoSuchElementException();
        }

        char nextChar() {
            checkEof();
            char b = read();
            checkEof();
            return b;
        }

        String next() {
            char b;
            do {
                b = read();
                checkEof();
            } while (Character.isWhitespace(b));
            StringBuilder sb = new StringBuilder();
            do {
                sb.append(b);
                b = read();
            } while (!eof && !Character.isWhitespace(b));
            return sb.toString();
        }

        int nextInt() {
            return Integer.valueOf(next());
        }

        long nextLong() {
            return Long.valueOf(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    private static class Restaurant {
        final String city;
        final int score;
        final int index;

        public Restaurant(String city, int score, int index) {
            this.city = city;
            this.score = score;
            this.index = index;
        }
    }
}

Measured memory_bytes: 25812
#include<iostream>
#include<stack>
#include<string>
#include <cstdlib>

using namespace std;
stack<double>m;
void solve(string k) {
	double t1 = m.top();
	m.pop();
	double t2 = m.top();
	m.pop();
	if (k == "+") {
		m.push(t1 + t2);
	}
	else if (k == "-") {
		m.push(t2 - t1);
	}
	else if (k == "*") {
		m.push(t2 * t1);
	}
	else {
		m.push(t2 / t1);
	}
}
int main(void)
{
	string k;
	while (cin >> k)
	{
		if (k == "+" || k == "-" || k == "*" || k == "/") {
			solve(k);
		}
		else {
			m.push(atof(k.c_str()));
		}
	}
	cout << m.top() << endl;
}


Measured memory_bytes: 3288
#include <bits/stdc++.h>
     
using namespace std;
     
#define FOR(i,a,b)		for(int i=(a),_b=(b);i<(_b);++i)
#define FORD(i,a,b)		for(int i=(a),_b=(b);i>(_b);--i)
#define pb			push_back
#define mp			make_pair
#define	all(c)			(c).begin(),(c).end()
#define	present(c,x)		((c).find(x) != (c).end())
#define	cpresent(c,x)		(find(all(c),x) != (c).end())
#define	endl			'\n'
     
typedef long long		ll;
typedef unsigned long long	ull;
typedef unsigned char	 	byte;
typedef vector<int>		vi;
typedef pair<int, int>		pii;
typedef pair<ll, ll>		pll;
typedef vector<pii>		vpii;
     
const int MX = 25;
     
int main(int argc, char *argv[])
{
#ifdef	HTRINH_UNIT_TEST
	freopen(argv[1],"r",stdin);
	ifstream cin(argv[1]);
#endif
#if 0
	ofstream cout(argv[2]);
#endif
	ios :: sync_with_stdio(false);
	cin.tie(NULL);

	int n,W;
	cin >> n >> W;
	int w[n],v[n];
	ull dp[W+1][n];
	FOR(i,0,W+1) FOR(j,0,n) dp[i][j] = 0;
	FOR(i,0,n) cin >> w[i] >> v[i];
	ull best = 0;
	FOR(x,1,W+1) {
		dp[x][0] = (x >= w[0]) ? v[0] : 0;
		best = max(best,dp[x][0]);
	}

	FOR(x,1,W+1) {
		FOR(i,1,n) {
			dp[x][i] = dp[x][i-1];
			if (x >= w[i]) {
				dp[x][i] = max(dp[x][i],dp[x-w[i]][i-1]+v[i]);
			}
			best = max(best,dp[x][i]);
		}
	}
    cout << best << endl;
    return 0;
}


Measured memory_bytes: 78336
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

int main() {
	long long N; cin >> N;
	long long res = sqrt(N);
	while (true) {
		if (N % res == 0) {
			break;
		}
		res--;
	}

	if (res == 0) {
		cout << N - 1 << endl;
	}
	else {
		cout << res + N / res - 2 << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int c[3][3];
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++) cin >> c[i][j];
    }    
    bool ans = true;
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++){
            if(c[i][j] - c[i][j+1] != c[i+1][j] - c[i+1][j+1]) ans = false;
            if(c[i][j] - c[i+1][j] != c[i][j+1] - c[i+1][j+1]) ans = false; 
        }
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int sz =1e5+10; 
int32_t main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int n,W,w,v;
    cin>>n>>W;
    int dp[sz];
    memset(dp,-1,sizeof(dp));
    dp[0] = 0;
    for(int i=0;i<n;i++)
    {
        cin>>w>>v;
        for(int j=1e5;j>=v;j--)
        {
            if(dp[j-v]!=-1)
                dp[j] = dp[j]==-1?dp[j-v]+w:min(dp[j],dp[j-v]+w);
        }
    }
    for(int j=1e5;j>0;j--)
    {
        if(dp[j]!=-1&&dp[j]<=W)
        {
            cout<<j;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	s, _ := r.ReadString('\n')
	t, _ := r.ReadString('\n')
	S := strings.TrimRight(s, " \t\n")
	T := strings.TrimRight(t, " \t\n")

	count := 0

	for i := 0; i < len(S); i++ {
		if S[i] != T[i] {
			count++
		}
	}
	fmt.Println(count)

}


Measured memory_bytes: 3004
fun main( args : Array<String> ) {
  val N  = readLine()!!.toInt()
  val Ts = readLine()!!.split(" ").map { x -> x.toInt() }
  val M  = readLine()!!.toInt()
  val px = (1..M).map { x -> 
    val (m, x) = readLine()!!.split(" ").map { x -> x.toInt() }
    Pair(m, x)
  }.toList().map { xy -> 
    val (x, y) = xy
    val ts     = Ts.toMutableList()
    ts[x-1] = y
    println( ts.sum() )
  }
   
}


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

int main(){
    int n;
    while(cin >> n, n){
        int sum = 0;
        int a[n]; 
        for(int i = 0 ; i < n; i++){
            cin >> a[i];
            sum += a[i];
        }
        sum /= n;
        int cnt = 0;
        for(int i = 0; i < n; i++){
            if(a[i] <= sum) cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}



Measured memory_bytes: 3140
#include<bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(),(x).end()
#define sz(x) (x).size()
using namespace std;


const int maxn=1e6+7;
vector<int>vec[maxn];

int s,t;

bool vis[maxn];

ll d[maxn];

void bfs(){
    memset(d,-1,sizeof(d));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s),d[s]=0;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        if(vis[now]) continue;
        vis[now]=1;
        for(int x:vec[now]){
            if(!vis[x]) d[x]=d[now]+1,q.push(x);
        }
    }
    if(d[t]>=0) cout<<d[t]/3<<endl;
    else cout<<-1<<endl;
}

int main (){
    int n,m;scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        int x,y;scanf("%d %d",&x,&y);
        vec[x].push_back(y+n);
        vec[x+n].push_back(y+2*n);
        vec[x+2*n].push_back(y);
    }
    cin>>s>>t;
    bfs();
    return 0;
}


Measured memory_bytes: 41856
#include<bits/stdc++.h>
#define debug cout<<"debug"<<endl;
using namespace std;
const int N=2e3+5;
int b[N],w[N];
int cb[N][N],cw[N][N];
int dp[N][N];//白--黑 
int main()
{
	int n;
	scanf("%d",&n);
	char color[6];
	int pos;
	for(int i=1;i<=2*n;i++)
	{
		scanf("%s%d",color,&pos);
		if(color[0]=='B')
		{
			b[pos]=i;
		}
		else
		{
			w[pos]=i;
		}
		//printf("%s\n",color);
	}
	//debug
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)//白--白 
		{
			if(b[i]<b[j])
			cb[i][0]++;
		}
		for(int j=1;j<=n;j++)//白--黑 
		{
			cb[i][j]=cb[i][j-1];
			if(b[i]<w[j])
			cb[i][j]++; 
		}
	}
//	debug
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)//黑--黑 
		{
			if(w[i]<w[j])
			cw[0][i]++;
		}
		for(int j=1;j<=n;j++)//黑--白 
		{
			cw[j][i]=cw[j-1][i];
			if(w[i]<b[j])
			cw[j][i]++; 
		}
	}
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=dp[i-1][0]+cb[i][0];
		dp[0][i]=dp[0][i-1]+cw[0][i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=min(dp[i-1][j]+cb[i][j],dp[i][j-1]+cw[i][j]);
			//cout<<i<<" "<<j<<": "<<dp[i][j]<<endl;
		}
	}
	printf("%d\n",dp[n][n]);
}

Measured memory_bytes: 47360
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N , sum;
  cin >> N;
  sum = 0;
  for (int i = 0; i < N; i++) {
    int l , r;
    cin >> l >> r;
    
    sum += r-l+1;
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const ll Mod = 998244353;
const int MAX = 510000;
const double PI = 3.14159265358979;
const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};

int main() {
  string s;
  int K;
  cin >> s >> K;
  set<string> sub; // 部分文字列を全列挙
  for (int i=0; i<(int)s.size(); i++) {
    for (int j=min(K, (int)s.size()-i); j>0; j--) sub.insert(s.substr(i, j));
  }
  int num = 1;
  for (auto v: sub) {
    if (num!=K) {
      num++;
      sub.erase(*begin(sub));
    }
    else {
      cout << *begin(sub) << endl;
      return 0;
    }
  }
}

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

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

ll x, y;

int main(){
    cin >> x >> y;
    int ans = 0;
    while (x <= y) {
        ans++;
        x *= 2;
    }
    cout << ans << endl;
}
































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

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

	int apple;
	int piece;
	int pie;

	cin >> apple;
	cin >> piece;

	pie = (apple * 3 + piece)/2;

	cout << pie << "\n";

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back

int main() {

    string s ;
    cin >> s ;
    ll n = s.size() - 1 ;
    ll ans = 0 , a = 0 ;

    for (ll i = 0 ; i< n ; i++) {
        if (s[i]=='A') a++ ;
        else if (s[i]=='B') {
            if (s[i+1]=='C') ans+=a,i++ ;
            else a= 0 ;
        }
        else {
            a = 0 ;
        }
    }
    cout << ans << endl ;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], *ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int N = getint(), M = getint();

	int saishou = 1e9;
	int saidai = 0;
	rep(i, M) {
		int L = getint(), R = getint();
		saidai = max(saidai, L);
		saishou = min(saishou, R);
	}
	if (saidai > saishou) co(0);
	else co(saishou - saidai + 1);

	Would you please return 0;
}

Measured memory_bytes: 384
using System;
class Program
{
	static void Main(string[] args)
	{
		// 整数の入力
		// スペース区切りの整数の入力
		string[] input = Console.ReadLine().Split(' ');
		int b = int.Parse(input[0]);
		int c = int.Parse(input[1]);
      int d = int.Parse(input[2]);
		// 文字列の入力
		//出力
      int a=c/b;
      if(a>d){a=d;}
		Console.WriteLine(a);
	}
}

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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;

int main()
{
  int N;
  string S;
  cin >> N >> S;
  ll ans = 0;
  for (int i = 0; i <= 9; i++)
  {
    for (int j = 0; j <= 9; j++)
    {
      for (int k = 0; k <= 9; k++)
      {
        bool first = false, second = false, third = false;
        for (int l = 0; l < N; l++)
        {
          if (!first && S[l] - '0' == i)
            first = true;
          else if (first && !second && S[l] - '0' == j)
            second = true;
          else if (first && second && !third && S[l] - '0' == k)
            third = true;
        }
        if (first && second && third)
          ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

signed main() {
  int n; cin >>n;
  vector<int> h(n);
  rep(i,n) cin >>h[i];
  int mx = 0;
  int ans = 0;
  rep(i,n) {
    if(h[i] >= mx) ans++;
    mx = max(h[i], mx);
  } 
  cout << ans << endl;
}


Measured memory_bytes: 3624
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int i, n, a[100001];
	scanf("%d", &n);
	for (i = 1; i <= n; i++) scanf("%d", &(a[i]));
	
	int max = 0;
	for (i = 1; i <= n; i++) if (a[i] > max) max = a[i];
	
	int ans = a[1] + 1, min = abs(a[1] * 2 - max) + 1;
	for (i = 1; i <= n; i++) {
		if (a[i] != max && abs(a[i] * 2 - max) < min) {
			min = abs(a[i] * 2 - max);
			ans = a[i];
		}
	}
	
	printf("%d %d\n", max, ans);
	fflush(stdout);
	return 0;
}

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

int main() {
    int a, b;
    cin>>a>>b;
    int k;
    cin>>k;
    int m=min(a, b);
    vector<int> c(m);
    for(int i=1;i<=m;i++) {
        if(a%i==0 && b%i==0) c.at(i-1)=i;
    }
    int cnt=0;
    for(int i=m-1;i>=0;i--) {
        if(c.at(i)!=0) cnt++;
        if(cnt==k) {
            cout<<c.at(i)<<endl;
            break;
        }
    }
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<math.h>
#define int long long
using namespace std;
const int INF = 10000000000000;

int two_find(int num) {
	bool divide = true;
	int cnt = 0;
	while (divide) {
		if (num % 2 == 0) {
			num /= 2;
			cnt++;
		}
		else divide = false;
	}
	return cnt;
}
signed main() {
	int N;
	cin >> N;
	vector<int> a(N);
	for (int i = 0; i < N; i++) cin >> a[i];
	int two = 0;
	for (int i = 0; i < N; i++) {
		two += two_find(a[i]);
	}
	cout << two << endl;
}


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

using namespace std;

typedef long long ll;

struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(ll N) : par(N) { //最初は全てが根であるとして初期化
        for(ll i = 0; i < N; i++) par[i] = i;
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }

    ll max() {
        vector <ll> cnt(par.size());
        for(ll i = 0; i < par.size(); i++) {
            cnt[root(i)]++;
        }
        ll mx = 0;
        
        for (ll i = 0; i < cnt.size(); i++) {
            mx = std::max(mx, cnt[i]);
        }
        
        return mx;
        
    }
};

int main() {
    ll N, M;
    cin >> N >> M;
    UnionFind *uf = new UnionFind(N);

    for (int i = 1; i <= M; i++) {
        ll a, b;
        cin >> a >> b;
        uf->unite(a-1, b-1);
    }

    cout << uf->max() << endl;
}

Measured memory_bytes: 12548
N,K=map(int,input().split())
a=[[1,i] for i in range(2,N+1)]
M=((N-1)*(N-2))//2
if K>M:
    print(-1)
else:
    b=[[i,j] for i in range(2,N+1) for j in range(i+1,N+1)][K:]
    c=a+b
    print(len(c))
    for i,j in c:
        print(i,j)

Measured memory_bytes: 4120
from functools import reduce
def modcomb(n, k, mod):
    #num = reduce(lambda x, y: x * y % mod, range(n, n - k, -1))
    #den = reduce(lambda x, y: x * y % mod, range(1, k + 1))
    #return num * pow(den, mod - 2, mod) % mod
    num = reduce(lambda x, y: x * y % mod, range(n, n - k, -1))
    den = reduce(lambda x, y: x * y % mod, range(1, k + 1))
    return num * pow(den, mod - 2, mod) % mod
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
x = pow(2, n, mod)
y = modcomb(n, a, mod)
z = modcomb(n, b, mod)
ans = x - y - z - 1
print(ans % mod)



Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100005
#define INF 1000000005
#define PI 3.1415926535897
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000005;
const int MOD = 1000000007;int modPow(long long a, long long n) {
    if(n==0)return 1;
  if (n == 1) return a % MOD;
  if (n % 2 == 1) return (a * modPow(a, n - 1)) % MOD;
  long long t = modPow(a, n / 2);
  return (t * t) % MOD;
}

int main(){
    int n;
    cin>>n;
    map<pair<ll,ll>,P>m;
    int cnt=0;
    REP(i,n){
        ll x,y;
        cin>>x>>y;
        if(x==0&&y==0)cnt++;
        else {
            ll t=__gcd(abs(x),abs(y));
            x/=t;
            y/=t;
            if(y<0){
                x=-x;
                y=-y;
            }
            if(x<=0){
                m[{y,-x}].second++;
            }else
            {
                m[{x,y}].first++;
            }
            
            
        }
    }
    ll ans=1;
    for(auto p:m){
        
        ans*=((modPow(2,p.second.first)+modPow(2,p.second.second)-1)%MOD);
        ans%=MOD;
    }
    ans--;
    ans+=cnt+MOD;
    ans%=MOD;
    OUT(ans);
    return 0;
}

Measured memory_bytes: 15996
a = input()
b = a[0] + a[1]
c = a[2] + a[3]

b = int(b)
c = int(c)

if 1 <= b and b <= 12 and 1 <= c and c <= 12:
  print('AMBIGUOUS')
elif 1 <= b and b <= 12 and 0 <= c and c <= 99:
  print('MMYY')
elif 0 <= b and b <= 99 and 1 <= c and c <= 12:
  print('YYMM')
else:
  print('NA')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
int main(void){
    int n, d, s=0, count=0, t;
    cin >> n >> d;
    vector<int>b(d);
    vector<vector<int>> a(n);
    for(int i = 0; i < n; i++) {

        for (int j = 0; j < d; j++) {
            cin >> b[j];
        }
        a[i] = b;
    }
    
   for(int i = 0; i < n; i++) {

        for(int h = i+1; h < n; h++){
            s = 0;
            for (int j = 0; j < d; j++) {
                s += pow((a[i][j] - a[h][j]), 2.0);
            }
           t = sqrt(s);
          if (sqrt(s) == t) count++;
        }
    }
    cout << count << endl;

}


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

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

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

  cout << ((n[0] == '9' || n[1] == '9') ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;

typedef vector<int> VI;
const int MV=1005;
const int ME=2005;

int n,m;

VI g[MV];
int col[MV],vis[MV];
VI st;

bool dfs(int u)
{
	if(col[u])
	{
		if(col[u]==1)
		{
			int i=0;
			for(;;i++)
				if(st[i]==u) break;
			for(;i<(int)st.size();i++)
				vis[st[i]]=1;
			return true;
		}
		else
			return false;
	}
	col[u]=1;
	st.push_back(u);
	for(int v:g[u])
		if(dfs(v)) return true;
	st.pop_back();
	col[u]=2;
	return false;
}

int pre[MV];
int cnt,start;
bool dfs2(int u,int p,int dep)
{
	//cout<<"!! "<<u<<endl;
	if(col[u])
	{
		if(u==start)
		{
			if(dep<cnt)
			{
				//cout<<"here "<<dep<<st.size()<<endl;
				memset(vis,0,sizeof(vis));
				for(int i:st)
					vis[i]=1;
				return true;
			}
			return false;
		}
		//cout<<col[u]<<endl;
		if(col[u]==1)
		{
			int i=p;
			memset(vis,0,sizeof(vis));
			vis[u]=1;
			while(i!=u)
			{
				vis[i]=1;
				i=pre[i];
				//break;
				//cout<<i<<endl;
			}
			return true;
		}
		else // col[u]==2
		{
			int i=pre[u];
			while(col[i]!=1)
			{
				vis[i]=0;
				i=pre[i];
			}
			return true;
		}
	}
	col[u]=1;
	pre[u]=p;
	st.push_back(u);
	for(int v:g[u])
	{
		if(!vis[v]) continue;
		//cout<<"!! !! "<<v<<endl;
		if(dfs2(v,u,dep+1)) return true;
	}
	col[u]=2;
	st.pop_back();
	return false;
}

void show_ans()
{
	cnt=0;
	for(int i=1;i<=n;i++)
		if(vis[i]) cnt++;
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++)
		if(vis[i]) printf("%d\n",i);
	//printf("\n");
}

int main()
{
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
	}
	int f=0;
	for(int i=1;i<=n;i++)
		if(!col[i]&&dfs(i))
		{
			f=1;
			break;
		}
	if(!f)
	{
		printf("-1\n");
		return 0;
	}
	//cout<<"here"<<endl;
	// show_ans();
	// cout<<endl;
	//int tt=1;
	while(true)
	{
		start=-1;
		cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(vis[i])
			{
				cnt++;
				start=i;
			}
		}
		memset(col,0,sizeof(col));
		st.clear();
		if(!dfs2(start,-1,0)) break;
		// show_ans();
		// cout<<endl;
		// tt++;
		// if(tt>20) break;
		// cout<<endl;
	}
	show_ans();
	return 0;
}
/*
8 15
1 7
2 8
3 4
3 5
3 6
3 8
4 1
4 2
4 5
5 2
5 3
5 6
6 8
8 1
8 7
*/

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

int main() {
	int n, k;
	string s;
	cin >> n >> s >> k;
	for(int i = 0; i < n; i++) {
		if(s[i] != s[k-1])
			s[i] = '*';
	} cout << s;
	return 0;
}

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

//0:直立
//1:逆立ち
//今回は連続で逆立ちさせたい
//num[]の偶数番が0の個数

int main(void)
{
	
	char str[100002];
	int i, j;
	int n, k;
	int count_ichi;
	int count_zero;
	int count = 0;
	int num[300000] = {0};
	int max = 0;
	int sum = 0;
	
	scanf("%d%d%s", &n, &k, str);
	
	str[n] = '5';
	
	if(str[0] == '0') {
		count++;
		num[0] = 0;
	}
	
	for(i = 0; i < n; i++) {
		if(str[i] == '1') {
			count_ichi = 1;
			for(j = i + 1; j <= n; j++) {
				if(str[j] == '1') {
					count_ichi++;
				} else {
					num[count] = count_ichi;
					count++;
					break;
				}
			}
			i = j - 1;
		} else {
			count_zero = 1;
			for(j = i + 1; j <= n; j++) {
				if(str[j] == '0') {
					count_zero++;
				} else {
					num[count] = count_zero;
					count++;
					break;
				}
			}
			i = j - 1;
		}
	}
	
	for(i = 0; i < 2 * k + 1; i++) {
		sum += num[i];
	}
	
	max = sum;
	
	for(i = 2 * k + 1; i < n; i = i + 2) {
		sum += (num[i] + num[i + 1]);
		sum -= (num[i - 2 * k - 1] + num[i - 2 * k]);
		
		if(max < sum) {
			max = sum;
		}
	}
	
	printf("%d\n", max);
	
	return 0;
}

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

int gcd(int x, int y){
	if(x > y){
		if(x%y == 0) return y;
		else return gcd(x%y, y);
	}
	else if(x < y){
		if(y%x == 0) return x;
		else return gcd(x, y%x);
	}
	else return x;
}

int main(){
	int x, y;

	cin >> x >> y;

	cout << gcd(x,y) << endl;

	return 0;
}

Measured memory_bytes: 1160
#include <cstdio>
using namespace std;

int dp[101][4][4];
int schedule[101];

int main()
{
	int N, K;
	
	scanf("%d %d", &N, &K);
	
	for (int i = 0; i < K; i++){
		int A, B;
		scanf("%d %d", &A, &B);	
		schedule[A] = B;
	}
	
	dp[0][0][0] = 1;
	
	for (int i = 0; i < N; i++){
		for (int j = 0; j < 4; j++){
			for (int k = 0; k < 4; k++){
				for (int l = 1; l < 4; l++){
					if (!(j == k && k == l) && (schedule[i + 1] == 0 || schedule[i + 1] == l)){
						dp[i + 1][k][l] = (dp[i + 1][k][l] + dp[i][j][k]) % 10000;
						
						//printf("%d\n", dp[i + 1][k][l]);
					}
				}
			}
		}
	}
	
	int cnt = 0;
	
	for (int i = 1; i < 4; i++){
		for (int j = 1; j < 4; j++){
			cnt = (cnt + dp[N][i][j]) % 10000;
		}
	}
	
	printf("%d\n", cnt);
	
	return 0;
}

Measured memory_bytes: 1028
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;++x)
#define Red(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int MAXN=2e5+5;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
//inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}
int n,sum[MAXN][2],a[MAXN],ans;char s[MAXN];
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),scanf("%s",s+1);
	Rep(i,1,n)a[i]=s[i]=='W';
	Rep(i,1,n)sum[i][0]=sum[i-1][0],sum[i][1]=sum[i-1][1],sum[i][a[i]]++;
	ans=1e9;
	Rep(i,0,n){
		int l1=sum[i][1],r0=sum[n][0]-sum[i][0];
		ans=min(l1+r0-min(l1,r0),ans);
	}cout<<ans<<'\n';
	return 0;
}



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

int a,b;

int gcd(int a,int b){
	if(b==0)  return a;
	return gcd(b,a%b);
}

int main(){
	while(scanf("%d%d",&a,&b)==2){
		int G=gcd(a,b);
		int L=a/G*b;
		printf("%d %d\n",G,L);
	}
	
	return 0;
}

Measured memory_bytes: 1024
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""


def readInts():
  return list(map(int,input().split()))

def main():
  n = int(input())
  A = readInts()
  
  SPLIT = round(sum(A)/n)
  
  ANS = 0
  #print(SPLIT)
  for i in range(n):
    ANS += abs(SPLIT-A[i])**2
  print(ANS)
  
if __name__ == '__main__':
  main()

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

ll N;
vector<ll> v;

void input() {
  cin >> N;
  v.resize(N);
  for (auto &e : v) { cin >> e; }
  sort(v.rbegin(), v.rend());
}

void solve() {
  ll ans = v.front();
  ll t = (N - 1) - 1;//全回数(n-1)-1最初の1回
  ll i = 1;
  bool cnt2 = false;//降順要素を各2回づつ加算
  while (t > 0) {
    ans += v[i];
    if (cnt2) {
      i++;
      cnt2 = false;
    } else {
      cnt2 = true;
    }
    t--;
  }
  cout << ans << endl;
}

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


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

#define REP(i, n) for(int (i) = 0; (i) < (int)(n); (i)++)
#define REPR(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for(int (i) = (m); (i) < (n); (i)++)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 1e9

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;

int main(int argc, char const *argv[])
{
    double ansub = INF;
    double N, T, A;
    cin >> N;
    cin >> T >> A;
    vector<double> H(10000);
    REP(i, N) cin >> H[i];
    
    int index = 0;
    REP(i, N)
    {
        if(chmin(ansub, abs(A - (T - H[i] * 0.006))))
        {
            index = i + 1;
        }
    }

    cout << index << endl;

    return 0;
}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
    int x,i=1;
    while(1){
        cin>>x;
        if(x==0){
            break;
        }
        else{
            cout<<"Case"<<" "<<i<<":"<<" "<<x<<endl;
            i++;
        }
    }
    return 0;
}


Measured memory_bytes: 3080
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int h, w, d; cin >> h >> w >> d;
  vector<vector<int>> A(h, vector<int>(w));
  vector<pair<int, int>> pos(h*w);
  rep(i, h) rep(j, w) {
    cin >> A[i][j];
    pos[--A[i][j]] = {i, j};
  }
  vector<ll> sum(h*w);
  rep(i, h*w) {
    if(i+d < h*w) {
      auto p1 = pos[i+d];
      auto p2 = pos[i];
      sum[i+d] += sum[i] + abs(p1.first-p2.first) + abs(p1.second-p2.second);
    }
  }
  int q; cin >> q;
  rep(i, q) {
    int l, r;
    cin >> l >> r;
    l--; r--;
    cout << sum[r] - sum[l] << endk;
  }
  return 0;
}


Measured memory_bytes: 5036
import java .util.*;

public class Main {
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int[] sum = new int[N];
	for (int i=0; i<N-1; i++) {
	    sum[sc.nextInt()-1]++;
	}
	for (int i=0; i<N; i++) {
	    System.out.println(sum[i]);
	}
    }
}


Measured memory_bytes: 66800
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
pub fn main() {
    let num = read::<i32>();
    if num < 1200 {
        println!("ABC");
    } else if num < 2800 {
        println!("ARC");
    } else {
        println!("AGC");
    }
}


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

int main()
{
    char w[110];
    cin>>w;
    int i,j,count,even;
    for(i=0; i<26; i++)
    {
        even = 0;
        j = 0;
        while(w[j]!='\0')
        {
            if(w[j]==97+i)
                    count = ++even;
            else if(w[j]<97 || w[j]>122)
                {
                    count = 1;
                    w[j] = '\0';
                }
            j++;
        }
        if(count%2!=0)
        {
            count = 1;
            i = 25;
        }
        else
            continue;
    }
    if(count==1)
        cout<< "No"<<endl;
    else
        cout<< "Yes"<<endl;
}


Measured memory_bytes: 256
//int x=1;
//string yn[2] = { "Yes","No" };
//int x=1;
//string yn[2] = { "YES","NO" };
// string alp="abcdefghijklmnopqrstuvwxyz";
// string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//総和
/*
int t_sum(int x) {
int sum = 0;
while (x > 0) {
sum += x % 10;
x = x / 10;
}
return sum;
}
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <regex>
#include <stack>
#include <queue>
#include <vector>
#include <iomanip>
#define MAX_N 100
#define INF 10000000

using namespace std;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int n,m,a,b;
int N[100];
string s,t;

void solve(){
	cout << n + m / 2 << endl;
}

int main() {
	cin >> n >> m;
	solve();
	return 0;
}

Measured memory_bytes: 256