akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>
int main()
{
	char a[12],b[12];
	scanf("%s %s",a,b);
  int na=strlen(a);
  int nb=strlen(b);
  int i,k=0;
  if(na+1==nb){
    for(i=0;i<na;i++){
      if(a[i]!=b[i]){
        k=1;
        break;
      }
    }
  }
  else{
    k=1;
  }
  if(k==1){
    printf("No");
  }
  else{
  printf("Yes");
  }
	return 0;
}

Measured memory_bytes: 2076
#include <iostream>

using namespace std;

void merge( int* arr, int l, int m, int r ){
	
	int i, j, k;
	int n1 = m - l + 1;
	int n2 = r - m;
	
	int L[n1], R[n2];
	
	for( i=0; i<n1; i++ ){
		L[i] = arr[l+i];
	}
	for( j=0; j<n2; j++ ){
		R[j] = arr[m+j+1];
	}
	i = 0;
	j = 0;
	k = l;
	while( i < n1 && j < n2 ){
		if( L[i] <= R[j] ){
			arr[k] = L[i];
			i++;
		}
		else{
			arr[k] = R[j];
			j++;
		}
		k++;
	}
	while( i < n1 ){
		arr[k] = L[i];
		k++;
		i++;
	}
	while( j < n2 ){
		arr[k] = R[j];
		k++;
		j++;
	}
}

void merge_sort( int* arr, int l, int r ){
	
	if( l < r ){
		int m = l + (r-l)/2;
		merge_sort( arr, l, m );
		merge_sort( arr, m+1, r );
		merge( arr, l, m, r );
	}
}

int main(){
	
	int N = 0;
	cin >> N;
	int L[N] = {0};
	for(int i=0; i<N; i++){
		cin >> L[i];
	}
	
	merge_sort( L, 0, N-1 );
	
	int c = 0;
	for( int i=0; i<N-2; i++ ){
		for( int j=i+1; j<N-1; j++ ){
			if( (L[i] + L[j]) > L[j+1] ){
				for( int k=j+1; k<N; k++ ){
					if( (L[i] + L[j]) > L[k] ){
						c++;
					}
					else{
						break;
					}
				}
			}
		}
	}
	cout << c << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
const int INFTY =2147483647;
int main(){
    string s;
    cin>>s;
    if(s[0]-s[1]!=0||s[1]-s[2]!=0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

int main() {
	int a,b,c;
	cin >> a >> b >> c;
	if(a == b && b == c)
            cout << 1 << endl;
	else if(a == b || b == c || c == a) 
            cout << 2 << endl;
	else 
            cout << 3 << endl;
	return 0;
}
 

Measured memory_bytes: 3620
#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
	int n, m;
	
	while (scanf("%d %d", &n, &m), n != 0 && m != 0){
		
		int p[1024];
		
		for (int i = 0; i < n; i++){
			scanf("%d", &p[i]);
		}
		
		sort(p, p+n);
		reverse(p, p+n);
		
		for (int i = 0; i < n; i++){
			if ((i + 1) % m == 0){
				p[i] = 0;
			}
		}
		
		int sum = 0;
		for (int i = 0; i < n; i++){
			sum += p[i];
		}
		
		printf("%d\n", sum);
	}
}

Measured memory_bytes: 1048
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;

// こっちの方が使いまわせて良い
const ll MOD = 1000000007;
const int SIZE = 200005;
ll inv[SIZE],fac[SIZE],finv[SIZE];
void make(){
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<SIZE;i++){
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		fac[i]=fac[i-1]*(ll) i%MOD;
		finv[i]=finv[i-1]*inv[i]%MOD;
	}
}
ll C (int a,int b) {
	if(a<b) return 0;
	return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD;
}

int main(){
  int H,W,A,B;
  cin >> H >> W >> A >> B;
  ll ans = 0;
  make();
  FOR(x,B+1,W+1){
    int y = H - A;
    int mx = x - 1, my = y - 1;
    ll tmp = C(mx + my, mx);
    mx = W - x, my = A - 1;
    tmp *= C(mx + my, mx);
    tmp %= MOD;
    ans += tmp;
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4992
#include <string>
#include <iostream>
using namespace std;
int N, Q, v[1000], w[1000], x; char s[1000][20];
int main() {
	while (scanf("%d %d", &N, &Q), N | Q) {
		for (int i = 0; i < N; i++) scanf("%s%d%d", s[i], &v[i], &w[i]);
		for (int i = 0; i < Q; i++) {
			scanf("%d", &x); int f = 0;
			for (int j = 0; j < N; j++) {
				if (w[j] - v[j] < x && x <= w[j]) {
					printf("%s %d\n", s[j], x - w[j] + v[j]); f = 1; break;
				}
			}
			if (!f) cout << "Unknown" << endl;
		}
	}
}

Measured memory_bytes: 3208
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype

template <class T>
int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount

const double EPS = 1e-8;
typedef long long ll;
typedef pair<int, int> pint;

struct E
{
	E(int dis, string to)
		: dis(dis), to(to){}
	int dis;
	string to;
};
struct P
{
	P(int calo, int visit, string pos)
		: calo(calo), visit(visit), pos(pos){}
	int calo, visit;
	string pos;
};
bool operator>(const P& a, const P& b)
{
	return a.calo > b.calo;
}
int main()
{
	int m, n, k, d;
	while (cin >> m >> n >> k >> d, m|n|k|d)
	{
		map<string, int> cake;
		for (int i = 1; i <= m; ++i)
			cin >> cake[string("C") + (char)('0' + i)];
		map<string, vector<E> > edge;
		for (int i = 0; i < d; ++i)
		{
			string a, b;
			int t;
			cin >> a >> b >> t;
			edge[a].push_back(E(t, b));
			edge[b].push_back(E(t, a));
		}
		map<string, map<int, int> > calo;
		queue<P> qq;
		priority_queue<P, vector<P>, greater<P> > q;
		calo["H"][0] = 0;
		q.push(P(0, 0, "H"));
		while (!q.empty())
		{
			P p = q.top(); q.pop();
			if (calo.count(p.pos) && calo[p.pos].count(p.calo)
				&& p.calo > calo[p.pos][p.visit])
				continue;

			foreach (it, edge[p.pos])
			{
				int next_calo = p.calo + it->dis * k;
				int next_visit = p.visit;
				if (it->to[0] == 'C')
				{
					if (p.visit & 1 << (it->to[1] - '1'))
						continue;
					else
					{
						next_calo -= cake[it->to];
						next_visit |= 1 << (it->to[1] - '1');
					}
				}

				if (!calo.count(it->to) || !calo[it->to].count(next_visit)
					|| next_calo < calo[it->to][next_visit])
				{
					calo[it->to][next_visit] = next_calo;
					q.push(P(next_calo, next_visit, it->to));
				}
			}
		}

		int res = 100000000;
		foreach (it, calo["D"])
			res = min(res, it->second);
		printf("%d\n", res);
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <fstream>
#include <iterator>
#include <random>
#include <chrono>

 
#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s
 
typedef long long ll;
 
using namespace std;

ll modd = 1000*1000*1000+7;

int main()   {

    ios_base::sync_with_stdio(false);

    cout.precision(17);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no
 
//    auto start = chrono::steady_clock::now();
  
//    readint(test_cases);
    int test_cases = 1;
    forr(t, 1, test_cases) {
        readint(a); readint(b); readint(c);
        readint(k);

        while ((k>0) && (b<=a)) {b*=2;k--;}
        while ((k>0) && (c<=b)) {c*=2;k--;}

        if ((a<b) && (b<c)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }

    }
 
//    auto end = chrono::steady_clock::now();
//    cout << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;

    return 0;
}

Measured memory_bytes: 3648
#include <map>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define met(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
typedef long long ll;

int main()
{
    ll num;
    cin>>num;
    ll ans=0;
    ll num1=num;
    while(num1)
    {
        ans+=num1%10;
        num1/=10;
    }
    if(num%ans==0)
        printf("Yes\n");
    else
        printf("No\n");
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N;
	in >> N;
	std::vector<LL>a(N);
	rep(i, N) in >> a[i];

	LL ans = 0;
	rep(i, N)
	{
		LL cnt = 0;
		for (int j = i; j < N; ++j)
		{
			if (a[i] == a[j]) ++cnt;
			else
			{
				ans += cnt / 2;
				i = j - 1;
				break;
			}
			if (j == N - 1)
			{
				ans += cnt / 2;
				i = j;
				break;
			}
		}
	}
	out << ans << std::endl;
}


Measured memory_bytes: 256
fn main() {
    proconio::input! {
        c: char,
    }
    let v = [
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
        's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
    ];
    let pos = v.iter().position(|x| *x == c).unwrap();
    let ans = v[pos + 1];
    println!("{}", ans);
}


Measured memory_bytes: 2088
#include<cmath>
#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;



int main() {
	int n, m;
	int a[100][100] = {};
	int b[100] = {};
	int c[100] = {};
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
			//cout << a[i][j] << endl;
		}
	}
	for (int z = 0; z < m; z++) {
		cin >> b[z];
		//cout << b[m] << endl;
	}
	for (int g = 0; g < n; g++) {
		for (int h = 0; h < m; h++) {
			c[g] += (a[g][h] * b[h]);
			//cout << b[g] << endl;
		}
		cout << c[g] << endl;
	}


	return 0;
}

Measured memory_bytes: 1208
#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>;

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



Measured memory_bytes: 3596
#include <iostream>
#include <cstdio>
#define N 100005
using namespace std;

typedef long long ll;
ll n, m, mx, a[N], b[N], st[N];
bool v[N][31], k[31];
void f(ll p) {
	ll i, j, s = 0;
	for (i =0; i < n; i++) {
		if (!v[i][p] && st[i] > p) s += b[i];
	}
	mx = max(mx, s);
}

int main()
{
	ll i, j, u;
	cin >> n >> m;
	for (i = 29; i >= 0; i--) {
		k[i] = m % 2;
		m /= 2;
	}
	for (i = 0; i < n; i++) {
		scanf ("%lld %lld", &a[i], &b[i]);
		u = a[i];
		st[i] = 31;
		for (j = 29; j >= 0; j--) {
			v[i][j] = u % 2;
			u /= 2;
			if (k[j] == 0 && v[i][j] == 1) st[i] = j;
		}
	}
	f(30);
	for (i = 0; i < 30; i++) {
		if (k[i]) f(i);
	}
	cout << mx << endl;
    return 0;
}


Measured memory_bytes: 5632
#!/usr/bin/perl

use strict;
use warnings;

my $S = <STDIN>;
chomp($S);

my $yes = 0;

my $l = length($S);
if ($l == 4) {
	my @mozi = ();
	my %count = ();
	for (my $i = 0; $i < $l; $i++) {
		my $c = substr($S, $i, 1);
		if (defined($count{$c})) {
			$count{$c}++;
		} else {
			push(@mozi, $c);
			$count{$c} = 1;
		}
	}
	if (@mozi == 2) {
		$yes = 1;
		for (my $i = 0; $i < @mozi; $i++) {
			if ($count{$mozi[$i]} != 2) { $yes = 0; }
		}
	}
}

printf("%s\n", $yes ? "Yes" : "No");


Measured memory_bytes: 640
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import math

if __name__ == "__main__":
    n = int(input())
    a = map(int, input().split())
    now = 0
    ans = 0
    for i, x in enumerate(a):
        if i + 1 == x:
            now += 1
        elif now:
            ans += max(1, math.ceil(now / 2))
            now = 0
    if now:
        ans += max(1, math.ceil(now / 2))
    print(ans)


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

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

int main() {
    int n;
    cin >> n;
    if(n < 10){
        cout << n << endl;
        return 0;
    }else if(n < 100){
        cout << 9 << endl;
        return 0;
    }else if(n < 1000){
        cout << n - 90 << endl;
        return 0;
    }else if(n < 10000){
        cout << 909 << endl;
        return 0;
    }else if(n < 100000){
        cout << n - 9090 << endl;
        return 0;
    }else{
        cout << 90909 << endl;
    }
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, M; cin >> N >> M;
  ll one = 1900 * M + (N - M) * 100;
  double p = 0;
  int t = 1; // t回目で成功する
  double sum = 0;
  while((1.0-p)>1e-9) {
    sum += pow(1.0 - 1.0 / pow(2, M) , t - 1) / pow(2, M) * one * t;
    p += pow(1.0 - 1.0 / pow(2, M) , t - 1) / pow(2, M);
    t++;
  }
  cout << ceil(sum) << endl;
  return 0;
}

Measured memory_bytes: 512
#include<cstdio>

int main(void){
	int p, buf, i;
	scanf("%d", &p); p=(p<40)?40:p;
	for(i=0; i<4; ++i){ scanf("%d", &buf); p+=(buf<40)?40:buf; }
	printf("%d\n", p/5);
	return(0);
}


Measured memory_bytes: 2712
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <time.h>
#include <cstdio>
using namespace std;

int A[4000] = {};
int main(){
	vector< pair<int,int> > v;
	for(int i = 0 ; i <= 1000 ; i++){
		for(int j = 0 ; j <= 1000 ; j++){
			A[i+j]++;
		}
	}
	int n;
	while(cin >> n){
		long long ans = 0;
		for(int i = 0 ; i <= n ; i++){
			ans += A[i]*A[n-i];
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1172
#include <stdio.h>

int main(void) {
  int x, y;

  while (1) {
  scanf("%d %d", &x, &y);
  
  if (x == 0 && y == 0)
    break;


  if (x <= y){
    printf("%d %d\n", x,y);
  }
  else printf("%d %d\n", y,x);
  }
  return 0;
}


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

int main(){
  int A,B,C,X;
  cin>>A>>B>>C>>X;
  int cnt=0;
  for(int i=0;i<=A;i++){
    for(int j=0;j<=B;j++){
      for(int k=0;k<=C;k++){
        if(500*i+100*j+50*k==X) cnt++;
      }
    }
  }
  cout<<cnt<<endl;
  return 0;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<bitset>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define re(i,x,y) for(int i=x;i<y;i++)

long long INF=1e9;
const long long mod=2019;
#define ll long long

int main(){
  string s;
  int k,n;
  map<string,int>mp;
  cin>>s>>k;
  n=s.size();
  for(int i=0;i<n;i++){
    for(int j=1;j<=5;j++){
      mp[s.substr(i,j)]=1;
    }
  }
  int kk=0;
  string ans;
  for(auto it=mp.begin();it!=mp.end();it++){
    ans=it->first;
    kk++;
    if(kk==k)break;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); 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 FORS(i, m, n) for (int i = m; i <= n; i++)
#define BIT(n) (1LL << (n))
#define INF 2e9
#define MOD (1000000007)
#define EPS 1e-9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long long int lli;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<double> x(N);
    vector<string> u(N);
    REP(i, N)
    {
        cin >> x[i] >> u[i];
    }
    double total = 0;
    REP(i, N)
    {
        total += u[i] == "BTC" ? x[i] * 380000 : x[i];
    }
    cout << total << "\n";
}

Measured memory_bytes: 256
def solve(N, S):
    ans = 0
    R, G, B = 0, 0, 0
    for i in range(N):
        if S[i] == "R":
            R += 1
        elif S[i] == "G":
            G += 1
        else:
            B += 1
    # print(R, G, B, R*G*B)
    ans = R * G * B

    dif = 1
    while dif <= N//2+1:
        idx = 0
        while idx + dif + dif < N:
            if S[idx] != S[idx + dif] and S[idx+dif] != S[idx+2*dif] and S[idx+2*dif] != S[idx]:
                ans -= 1
            idx += 1
        dif += 1
    print(ans)
if __name__ == '__main__':
    # N = 4000
    # S = 'RGBR' * 1000
    N = int(input())
    S = input()

    solve(N, S)


Measured memory_bytes: 73164
#include<stdio.h>
 int main(void)
 {
     int r,g,b;
     int R;

     scanf("%d%d%d",&r,&g,&b);

     R=100*r+10*g+b;

     if(R%4==0) printf("YES\n");
     else printf("NO\n");

     return 0;
 }




Measured memory_bytes: 128
#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 d, n;
    cin >> d >> n;
    int num = 1;
    rep(i,d) num *= 100;
    int ans = 0;
    rep(i,n) ans += num;
    if(n == 100) cout << ans + num << endl;
    else cout << ans << endl;
}

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

using namespace std;

int main() {
	int w, h, x, y; cin >> w >> h >> x >> y;
	double area = (( double) w * ( double) h) / 2;
	int flag = 0;
	if (w * y == h * x || w * y == -h * x + w * h || w == 2 * x || h == 2 * y) {
		if (w == 2 * x && h == 2 * y) flag = 1;
	}
	printf("%.8f %d\n", area, flag);

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, k, n) for(int i = (k); i < (n); i++)
#define FORe(i, k, n) for(int i = (k); i <= (n); i++)
#define FORr(i, k, n) for(int i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(int i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using ll = long long;

const int INF = 1001001001;
const int mod = 1000000007;

class mint{
  public:
  ll x;
  mint(ll x = 0):x((x % mod + mod) % mod){};
  mint pow(ll y) const {
    mint res(1);
    mint a(x);
    while(y>0){
      if(y&1) res *= a;
      a *= a;
      y >>= 1;
    }
    return res;
  }
  mint inv() const{ return pow(mod-2); }
  mint& operator+= (const mint a) noexcept {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-= (const mint a) noexcept {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*= (const mint a) noexcept {
    (x *= a.x) %= mod;
    return *this;
  }
  mint& operator/= (const mint a) noexcept {
    return (*this) *= a.inv();
  }
  mint operator+ (const mint a) const noexcept {
    mint res(*this);
    return res += a;
  }
  mint operator- (const mint a) const noexcept {
    mint res(*this);
    return res -= a;
  }
  mint operator* (const mint a) const noexcept {
    mint res(*this);
    return res *= a;
  }
  mint operator/ (const mint a) const noexcept{
    mint res(*this);
    return res /= a;
  }
};

class comb{
  public:
  vector<mint> fact, ifact;
  comb(int n): fact(n+1), ifact(n+1){
    fact[0] = 1;
    for(int i = 1; i <= n; i++) fact[i] = fact[i-1] * i;
    ifact[n] = fact[n].inv();
    for(int i = n; i >= 1; i--) ifact[i-1] = ifact[i] * i;
  }
  mint operator()(int n, int k) const noexcept{
    if(k < 0 || n < k) return 0;
    return fact[n] * ifact[k] * ifact[n-k];
  }
};

mint dp[105][5][5][5];
enum{
  X,
  A,
  C,
  G,
  T
};

int main(void){
  int n;
  cin >> n;
  dp[0][0][0][0] = 1;
  REP(i, n) REP(a, 5) REP(b, 5) REP(c, 5){
    FOR(d, 1, 5){
      // AGC GAC ACG
      if(b == A && c == G && d == C) continue;
      if(b == G && c == A && d == C) continue;
      if(b == A && c == C && d == G) continue;
      // A*GC AG*C
      if(a == A && c == G && d == C) continue;
      if(a == A && b == G && d == C) continue;
      dp[i+1][b][c][d] += dp[i][a][b][c];
    }
  }
  mint ans;
  REP(a, 5) REP(b, 5) REP(c, 5) ans += dp[n][a][b][c];
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 384
# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# author:   noname
# url:      https://github.com/pettan0818
# license:  mit license
# created: 木 10/12 18:57:45 2017

# usage
#
"""
import math


def calc_distance(student_post, checkpoint_post):
    return int(math.fabs(student_post[0] - checkpoint_post[0]) + math.fabs(student_post[1] - checkpoint_post[1]))


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    first = input()
    first = first.split(" ")
    data = [int(line) for line in first]

    student_num = data[0]
    checkpoint_num = data[1]

    student_pos_data = [[int(i) for i in input().split(" ")] for i in range(student_num)]
    checkpoint_data = [[int(i) for i in input().split(" ")] for i in range(checkpoint_num)]

    for each_student in student_pos_data:
        dis_list = [calc_distance(each_student, i) for i in checkpoint_data]
        print(dis_list.index(min(dis_list)) + 1)


Measured memory_bytes: 7048
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, m, c;
  cin >> n >> m >> c;
  vector<int> b(m);
   for (int i = 0; i < m; i++) {
     cin >> b.at(i);
   }
  vector<vector<int>> data(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> data.at(i).at(j);
    }
  }
    int kauto = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        kauto += data.at(i).at(j) * b.at(j);
        if (j == m - 1) {
          if (kauto + c > 0) {
            count++;
          }
            kauto = 0;
          
        }
      }
    }
  cout << count << endl;
}

Measured memory_bytes: 3600
#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 SZ(i) int(i.size())
#ifdef tmd
#define IOS()
#define debug(...) fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(...)
#endif

const int MAXN = 500005;
const ll MOD = 1000000007;

int n;
/*********************GoodLuck***********************/
int main () {
    IOS();

    cin >> n;
    REP1 (i, 9) {
        REP1 (j, 9) {
            if (i*j == n) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const char atcg[4] = {'A', 'T', 'C', 'G'};

ll dp[101][5][5][5];

int main() {
    int n;
    cin >> n;
    
    dp[0][0][0][0] = 1;

    for(int i=0;i<n;++i) {
        for(int j1=0;j1<5;++j1) {
            for(int j2=0;j2<5;++j2) {
                for(int j3=0;j3<5;++j3) {
                    if(!dp[i][j1][j2][j3]) continue;
                    for(int j4=1;j4<5;++j4) {
                        if(j4 == 3 && ((j3 == 4 && (j1 == 1 || j2 == 1)) || (j2 == 4 && (j1 == 1 || j3 == 1))) || (j2 == 1 && j3 == 3 && j4 == 4)) {
                            continue;
                        }
                        dp[i+1][j2][j3][j4] += dp[i][j1][j2][j3];
                        dp[i+1][j2][j3][j4] %= MOD;
                    }
                }
            } 
        }
    }

    ll ans = 0LL;
    for(int j1=1;j1<5;++j1) {
        for(int j2=1;j2<5;++j2) {
            for(int j3=1;j3<5;++j3) {
                ans += dp[n][j1][j2][j3];
                ans %= MOD;
            }
        }
    }

    cout << ans << endl;
}


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

int main() {
  int n;
  cin >> n;
  int ans = 0;
  int ant = 101234;
  int atual;
  n--;
  while (n--) {
    cin >> atual;
    ans += min(ant, atual);
    ant = atual;
  }
  ans += min(ant, 101234);
  printf("%d\n", ans);
  return 0;}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
const int MAX_N = 60;
struct Info
{
    P left, right;
};
string Rfield[MAX_N];
string Lfield[MAX_N];
bool used[MAX_N][MAX_N][MAX_N][MAX_N];
int h, w, lsy, lsx, rsy, rsx;
bool OutOfRange(int y, int x, string field[])
{
    if(y >= h || x >= w || x < 0 || y < 0 || field[y][x] == '#') return true;
    else return false;
}
bool bfs()
{
    memset(used, false, sizeof(used));
    queue<Info> que;
    que.push({P(lsy, lsx), P(rsy, rsx)});
    while(!que.empty())
    {
        Info p = que.front();
        que.pop();
        if(used[p.left.first][p.left.second][p.right.first][p.right.second]) continue;
        used[p.left.first][p.left.second][p.right.first][p.right.second] = true;
        if(Lfield[p.left.first][p.left.second] == '%' && Rfield[p.right.first][p.right.second] == '%') return true;
        if(Lfield[p.left.first][p.left.second] == '%' || Rfield[p.right.first][p.right.second] == '%') continue;
        for(int i = 0; i < 4; i++)
        {
            int ly = p.left.first;
            int lx = p.left.second;
            int ry = p.right.first;
            int rx = p.right.second;
            if(!OutOfRange(ly + dy[i], lx + dx[i], Lfield)) ly += dy[i], lx += dx[i];
            if(!OutOfRange(ry + dy[i], rx - dx[i], Rfield)) ry += dy[i], rx -= dx[i];
            P np = {ly, lx}, nq = {ry, rx};
            if(!used[ly][lx][ry][rx]) que.push({np, nq});
        }
    }
    return false;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> w >> h, w | h)
    {
        for(int i = 0; i < h; i++)
        {
            cin >> Lfield[i] >> Rfield[i];
            for(int j = 0; j < w; j++)
            {
                if(Lfield[i][j] == 'L') lsy = i, lsx = j;
                if(Rfield[i][j] == 'R') rsy = i, rsx = j;
            }
        }
        cout << (bfs() ? "Yes" : "No") << endl;
    }
    return 0;
}




Measured memory_bytes: 17280
#include <iostream>
#include <complex>
#include <cmath>
#include <cstdio>
using namespace std;
typedef complex<double> xy_t;
xy_t P[110];

double cross_product(xy_t a , xy_t b){
	return (conj(a)*b).imag();
}

int main(){
	int i,n;
	double x,y,area;
	scanf("%d\n",&n);
	for(i=0;i<n;i++){
		scanf("%lf %lf\n",&x,&y);
		P[i]= xy_t(x,y);
	}//読み込み

	double areasum = 0.0;
	for(i=2;i<n;i++){
		area = cross_product(P[i]-P[0],P[i-1]-P[0])/2;
		areasum += area;
	}

	areasum = fabs(areasum);
	printf("%.1f\n",areasum);;
	return 0;	

}

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

using namespace std;

#define int long long
#define MOD 1000000007

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}

//typedef long long ll;
#define TENNINE 1000000005
#define TENFIVE 100005
//#define int long long

int n;
vector<int> p;

signed main()
{

    cin >> n;
    p.resize(n);
    rep(i, n)
    {
        cin >> p[i];
    }
    vector<int> temp;
    temp.resize(n);
    temp = p;
    sort(all(temp));

    int cnt = 0;

    rep(i, n)
    {
        if (p[i] != temp[i])
        {
            cnt++;
        }
    }

    if ((cnt == 0) || (cnt == 2))
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
vector<string> split(string s, char p){vector<string>v;stringstream m(s);string b;while(getline(m,b,p))v.push_back(b);return v;}
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; }
struct nya{ nya(){ cin.tie(0); ios::sync_with_stdio(false); } }nyan;

int main(){
    ll N; cin >> N;
    ll ans = 0;
    if (N%2 == 0) {
        ans = (N/2-1) * N + (N/2);
    } else {
        ans = (N/2) * N;
    }
    cout << ans << "\n";
}


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

int main(){
  string s;
  cin >> s;
  int n=s.size();
  for(int i=0; i<n; i++){
    if(i==3){
      cout << s[i] << " ";
      continue;
    }
    cout << s[i];
  }
  cout << endl;
}



Measured memory_bytes: 3600
#include <stdio.h>

int main() {
  int n, m, ans = 0;
  
  scanf("%d%d",&n, &m);
  
  long h[n + 1];
  int a[m + 1], b[m + 1], c[n + 1];
  
  for(int i = 1; i <= n; i++) {
    c[i] = 0;
  }
  
  for(int i = 1; i <= n; i++) {
    scanf("%ld",&h[i]);
  }
  for(int i = 1; i <= m; i++) {
    scanf("%d%d",&a[i], &b[i]);
  }
  
  for(int i = 1; i <= m; i++) {
    if(h[a[i]] > h[b[i]]) {
		c[b[i]] = 1;
	}
    if(h[a[i]] < h[b[i]]) {
		c[a[i]] = 1;
	}
    if(h[a[i]] == h[b[i]]) {
		c[b[i]] = 1;
		c[a[i]] = 1;
	}
  }
  
  for(int i = 1; i <= n; i++) {
    if(c[i] == 0) {
		ans += 1;
	}
  }
  printf("%d",ans);
}


Measured memory_bytes: 3660
import java.util.*;
import java.lang.*;

public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        while (true) {
            int n = sc.nextInt();
            if (n == 0) break;
            
            double[] s = new double[n];
            double m = 0;
            double var = 0;
            double sd = 0;
        
            for (int i = 0; i < n; i++){
                s[i] = sc.nextInt();
                m += s[i];
            }
            m /= n;
            
            for (int i = 0; i < n; i++) {
                var += Math.pow(s[i] - m, 2);
            }
            var /= n;
            
            sd = Math.sqrt(var);
            
            System.out.println(sd);
        }
    }
}


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

int main() {
    int a[3],b=0,c=0;
    for(int i=0;i<3;i++){
     cin >> a[i];
     if(a[i]==5) b++;
     if(a[i]==7) c++;
    }
  if(b==2 && c==1) cout << "YES" << endl;
  else cout << "NO" << endl;

}

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

string s,t;
int flags[55];

int main() {
    cin >> s >> t;
    int sizes = s.size();
    int sizet = t.size();
    if (sizes < sizet) {
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    for (int i = 0; i <= sizes - sizet; i++) {
        int flag = 1;
        for (int j = 0; j < sizet; j++) {
            if (s[i+j] != t[j] && s[i+j] != '?') flag = 0;
        }
        flags[i] = flag;
    }
    int flag = 1;
    for (int i = sizes - sizet; i >= 0; i--) {
        if (flags[i] && flag) {
            flag = 0;
            for (int j = 0; j < sizet; j++) s[i+j] = t[j];
            for (int j = 0; j < sizes; j++) if (s[j] == '?') s[j] = 'a';
        }
    }
    if (flag) {
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    cout << s << endl;
    return 0;
}

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    return arr

fact = factorization(N)
s = 0
for p, e in fact:
    s += int(pow(e * 2 + 0.25, 0.5) - 0.5)
print(s)

Measured memory_bytes: 9468
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)n; i++)
#define PI 3.14159265358979323846
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define pll pair<long long, long long>
#define cld complex<long double>
using namespace std;
using ll = long long;
using ld = long double;

// ----本問について----
// 問題：A Point in a Triangle
// 問題文URL：https://onlinejudge.u-aizu.ac.jp/problems/0012
// 所要時間：
// 学んだこと：
// ------------------

// ----ここから本問のソースコード----

// グローバル変数（入力）
complex<ld> c[3], cp;

void input() {
  rep(i, 3) {
    ld x, y;
    cin >> x >> y;
    c[i] = complex<ld>(x, y);
  }
  ld xp, yp;
  cin >> xp >> yp;
  cp = complex<ld>(xp, yp);
}

ld cross_product(complex<ld> a, complex<ld> b) { return (conj(a) * b).imag(); }

void solve() {
  rep(i, 3) { c[i] -= cp;}
  ld a[3];
  rep(i, 3) { a[i] = cross_product(c[i % 3], c[(i + 1) % 3]);}
  if ((a[0] > 0 && a[1] > 0 && a[2] > 0) ||
      (a[0] < 0 && a[1] < 0 && a[2] < 0)) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

int main() {
  while (true) {
    input();
    if (!cin) { break; }
    solve();
  }
  return 0;
}



Measured memory_bytes: 3184
#include<stdio.h>
int main(void)
{
long n,a[10000],i,max=-1000001,min=1000001,Sam=0;
	scanf("%ld",&n);
	for(i=0;i<n;i++){
		scanf("%ld",&a[i]);
		if(a[i]>max){
			max=a[i];
		}
		if(a[i]<min){
			min=a[i];
		}
		Sam+=a[i];
	}
	printf("%ld %ld %ld\n",min,max,Sam);
	return 0;
}

Measured memory_bytes: 676
N, M, C = map(int, input().split(' '))
B = []
for b in input().split(' '):
  B.append(int(b))
A = []
for n in range(N):
  A_n = []
  for a in input().split(' '):
    A_n.append(int(a))
  A.append(A_n)
 
# search answer
ans = 0
for A_i in A:
  eq = 0
  for m in range(M):
    eq += A_i[m]*B[m]
  eq += C
  if eq>0:ans+=1
print(ans)

Measured memory_bytes: 3064
#平方根を求める
def sqrt(n):
    a = n/2
    while True:
        b = (a+n/a)/2
        if a == b:return b
        else:a,b = b,a


#べき乗数かどうか判断する関数
def pow_judge(n):
    if n == 1 or n == 2:return True
    i = int(sqrt(n))
    if i*i == n:
        return True
    else:
        return False

ls = set()
for i in range(1,32):
    for j in range(2,11):
        if i**j > 1000:break
        ls.add(i ** j)
x = int(input())
for i in range(x,-1,-1):
    if i in ls:
        print(i)
        break

Measured memory_bytes: 3064
A=[[],[],[]]
b=[]
A[0]=[int(x) for x in input().split()]
A[1]=[int(x) for x in input().split()]
A[2]=[int(x) for x in input().split()]
N =int(input().split()[0])
for i in range(N):
  b.append(int(input()))

for i in range(N):
  for j in range(3):
    for k in range(3):
      if A[j][k]==b[i]:
        A[j][k]=0
num=(A[0][0]+A[0][1]+A[0][2])*(A[1][0]+A[1][1]+A[1][2])*(A[2][0]+A[2][1]+A[2][2])*(A[0][0]+A[1][0]+A[2][0])*(A[0][1]+A[1][1]+A[2][1])*(A[0][2]+A[1][2]+A[2][2])*(A[0][0]+A[1][1]+A[2][2])*(A[0][2]+A[1][1]+A[2][0])

if num==0:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 9300
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  int A = 0;
  int B = 0;
  int C = 0;
  int D = 0;
  for (int i = 0; i < N; i++) {
    string S;
    cin >> S;
    if (S=="AC") {
      A++;
 }
    else if (S=="WA"){
      B++;
}
    else if (S=="TLE"){
      C++;
}
    else if (S=="RE"){
      D++;
}
}
 
  cout << "AC x "<< A << endl;
  cout << "WA x " << B << endl;
  cout << "TLE x " << C << endl;
  cout <<"RE x " << D << endl;
}

Measured memory_bytes: 3632
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  vector<string> vec(H);
  
  for(int i = 0; i <= W + 1; i++){
    cout << "#";
  }
  
  cout << endl;
  
  for(int i = 0; i < H; i++){
    cin >> vec[i];
    cout << "#" << vec[i] << "#" << endl;
  }
  
  for(int i = 0; i <= W + 1; i++){
    cout << "#";
  }
  
  return 0;
}

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

int main()
{
    int a, b, k;
    cin >> a >> b >> k;
    int minmax = min(b,a+k);
    for(int i=a;i<minmax;i++){
        cout << i << endl;
    }
    if(minmax <= b){
        for(int j=max(b-k+1,minmax);j<=b;j++){
            cout << j << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
/*
 * main.c
 *
 *  Created on: 2019/07/07
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
	int N = 0, A = 0, B = 0, ans = 0;
	scanf("%d %d %d", &N, &A, &B);
	if((A*N) < B) {
		ans = (A*N);
	} else {
		ans = B;
	}

    printf("%d\n",ans );
    return 0;
}


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

int main() {
  int n;
  string s,sf,sb,ans;
  sf = ""; sb = "";
  ans = "No";
  cin >> n >> s;
  if(n%2 == 1){
    cout << ans << endl;
    return 0;
  }
  sf = s.substr(0,n/2);
  sb = s.substr(n/2,n-1);
  if(sf == sb){
    ans = "Yes";
  }

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


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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    int dp[n + 1][m + 1];
    memset(dp, 0, sizeof dp);
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            if(i == 0 || j == 0) dp[i][j] = 0;
            else if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    int ind = dp[n][m];
    char ans[ind + 1];
    ans[ind] = ' ';
    int i = n, j = m;
    while(i > 0 && j > 0) {
        if(s[i - 1] == t[j - 1]) {
            ans[ind - 1] = s[i - 1];
            i--;
            j--;
            ind--;
        } else if(dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    for(int i = 0; i < dp[n][m]; i++) {
        cout << ans[i];
    }
    return 0;
}


Measured memory_bytes: 35456
#include <bits/stdc++.h>
#define INF 1000000007
using namespace std;

vector<int> g[100010];
int d[100010],r[100010],l[100010],n,k;
bool ans;

void solve(int v,int p)
{
	l[v]=-INF-1;r[v]=INF+1;
	if(d[v]!=-1){
		l[v]=d[v];
		r[v]=d[v];
	}
	for(int i=0;i<g[v].size();i++){
		int nx=g[v][i];
		if(nx!=p){
			solve(nx,v);
			if(l[nx]<-INF/2) continue;
			if(l[v]<-INF/2){
				l[v]=l[nx]-1;
				r[v]=r[nx]+1;
			}
			else{
				if(abs(l[nx])%2==abs(l[v])%2){
					ans=true;
					return;
				}
				l[v]=max(l[v],l[nx]-1);
				r[v]=min(r[v],r[nx]+1);
			}
		}
	}
	if(l[v]>r[v]){
		ans=true;
	}
}

void make(int v,int p)
{
	if(v==1&&d[v]==-1) d[v]=l[v];
	for(int i=0;i<g[v].size();i++){
		int nx=g[v][i];
		if(nx!=p){
			if(d[nx]==-1){
				if(l[nx]<=d[v]-1&&d[v]-1<=r[nx]) d[nx]=d[v]-1;
				else d[nx]=d[v]+1;
			}
			make(nx,v);
		}
	}
}

int main()
{
	memset(d,-1,sizeof(d));
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	cin>>k;
	for(int i=1;i<=k;i++){
		int v,p;
		cin>>v>>p;
		d[v]=p;
	}
	solve(1,-1);
	if(ans){
		cout<<"No"<<endl;
		return 0;
	}
	else{
		make(1,-1);
		cout<<"Yes"<<endl;
		for(int i=1;i<=n;i++) cout<<d[i]<<endl;
		return 0;
	}
}

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

bool S[100005];
ll W[100005];

int main() {
    ll N, M;
    cin >> N >> M;
    memset(S, 0, sizeof(S));
    memset(W, 0, sizeof(W));
    REP(i, M) {
        ll p;
        string s;
        cin >> p >> s;
        p--;
        if (s == "AC")
            S[p] = true;
        else if (!S[p])
            W[p]++;
    }

    ll ac = 0, wa = 0;
    REP(i, N) {
        if (S[i]) {
            ac++;
            wa += W[i];
        }
    }

    cout << ac << " " << wa << endl;

    return 0;
}

Measured memory_bytes: 1152
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
using namespace std;
typedef long long int llint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;

bool check(int a, int b) {
	return a > b;
}

int main() {
	int a, b, k;
	cin >> a >> b >> k;
	int cnt;
	while (a != 0 && b != 0) {
		if (a < b) {
			b %= a;
		}
		else {
			a %= b;
		}
	}
	cnt = max(a, b);
	int tmp = 0;
	int ans;
	rep(i, cnt) {
		if (cnt%(cnt-i) == 0)tmp++;
		if (tmp == k) {
			ans = (cnt-i);
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
N=int(input())
a=list(input().split())
a=[int(S) for S in a]
mini=min(a)
count=0
#print(a)
for i in range(0,N-1):
    if a[i+1]>a[i]:
        count+=a[i+1]-a[i]
        #print(a[i+1],a[i])
#print(count)
count+=a[0]
print(count)


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[] a = new int[10000];
				for(int i = 0 ; i<10000 ; i++){
					a[i]=scan.nextInt();
					if(a[i]==0) break;
					}
				
		for(int i = 0 ; i<10000 ; i++){
			if(a[i]==0) break;
		System.out.println("Case "+(i+1)+": "+a[i]);
		}
	}


}

Measured memory_bytes: 43076
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

ll counter[100001];
ll n, m, p[100000], a, b, c;

int main() {
  scanf("%lld%lld", &n, &m);
  for (ll i = 0; i < m; i++) scanf("%lld", &p[i]), p[i]--;
  for (ll i = 0; i < m - 1; i++) {
    if (p[i] < p[i+1]) {
      counter[p[i]]++;
      counter[p[i+1]]--;
    } else {
      counter[p[i+1]]++;
      counter[p[i]]--;
    }
  }
  ll temp = 0, ans = 0;
  for (ll i = 0; i < n; i++) {
    scanf("%lld%lld%lld", &a, &b, &c);
    temp += counter[i];
    if (temp == 0) continue;
    ans += min(a * temp, c + temp * b);
  }
  printf("%lld\n", ans);
}



Measured memory_bytes: 4248
#include <bits/stdc++.h>
#include <ext/numeric>
/**
    PROGRESS IS PROGRESS
    NO MATTER HOW SMALL
*/
using namespace std;
using namespace __gnu_cxx;

#define all(v)   v.begin(), v.end()
#define sz(x)    (int) x.size()
#define Unique(x) x.erase(unique(all(x)), x.end())
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define START cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define isOdd(n)    (n&1)
#define LLMAX LLONG_MAX
#define LLMIN LLONG_MIN
#define IMN INT_MIN
#define IMX INT_MAX
#define pow(n, m) power((ll)n, (ll)m)
#define numOfDigits(n)  ((n)? (ll)(log10(n))+1 : 1)
#define mem(x, val)    memset(x, val, sizeof(x)) //be careful
#define MOD 1000000007


typedef long long ll;
typedef long double ld;
typedef double dd;
typedef pair<int, int> pii;
typedef vector<ll> vi;


int main()
{
    START
    //freopen("test cases\\in.txt", "r", stdin) ;
    //freopen("test cases\\out.txt", "w", stdout) ;
     string s1, s2; cin>>s1>>s2;
    int n = s1.size(), m = s2.size();
    int dp[n+1][m+1];
    for(int i =0; i<=n; i++){
        for(int j = 0; j<=m; j++){
            if(!i || !j) dp[i][j] = 0;

            else if(s1[i-1]==s2[j-1]) dp[i][j] = 1 + dp[i-1][j-1];

            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    //cout<<dp[n][m]<<endl;
    int i = n, j = m;
    string ans = "";
    while(dp[i][j]>0){
        if(dp[i][j]==max(dp[i-1][j], dp[i][j-1])){
            if(dp[i-1][j] >= dp[i][j-1])i--;
            else j--;
        }
        else ans.pb(s1[i-1]), i--, j--;
    }
    reverse(all(ans));
    cout<<ans;
	return 0;
}


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

int main() {
  int N, X, a, ans = 0, cnt, i;
  cin >> N >> X;
  vector< int > L(N);
  for ( i = 0; i < N; i++ ) {
    cin >> a;
    ans += a;
    // cout << a << " " << ans << " " << i << endl;
    if ( ans > X ) {
      break;
    }
  }
  cout << i + 1 << endl;

  return 0;
}


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

#define int long long
#define inf 1000000007LL

#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n) - 1LL; i >= 0; i--)
#define trep(i, n) for(int i = 0; i <= (n); i++)
#define rep1(i, n) for(int i = 1LL; i <= (n); i++)
#define mfor(i, s, t) for(int i = (s); i < (t); i++)
#define tfor(i, s, t) for(int i = (s); i <= (t); i++)
/*
class Dinic {
public:
  vector<vector<pair<int, int>>> v;
  vector<int> e;

  vector<int> k;
  vector<int> j;

  void init(int n) {
    v = vector<vector<pair<int, int>>>(n);
    e = vector<int>();
    k = vector<int>(n);
    j = vector<int>(n);
  }
  void add_edge(int a, int b, int atob, int btoa = 0) {
    v[a].push_back(make_pair(b, e.size()));
    e.push_back(atob);
    v[b].push_back(make_pair(a, e.size()));
    e.push_back(btoa);
  }
  void dyk(int s) {
    for(auto& i : k) {
      i = inf;
    }
    queue<pair<int, int>> pq;
    pq.push(make_pair(0, s));
    while(!pq.empty()) {
      int w = pq.front().first;
      int b = pq.front().second;
      pq.pop();
      if(k[b] > w) {
        k[b] = w;
        for(auto i : v[b]) {
          if(e[i.second] > 0) {
            pq.push(make_pair(w + 1LL, i.first));
          }
        }
      }
    }
  }
  int dfs(int s, int t, int p, int c) {
    if(p == t) {
      return c;
    }
    int all = 0;
    while(c > all && j[p] < v[p].size()) {
      if(k[v[p][j[p]].first] == k[p] + 1LL) {
        int r = dfs(s, t, v[p][j[p]].first, min(c - all, e[v[p][j[p]].second]));
        e[v[p][j[p]].second] -= r;
        e[v[p][j[p]].second ^ 1LL] += r;
        if(r < c - all) {
          j[p]++;
        }
        all += r;
      }
      else {
        j[p]++;
      }
    }
    return all;
  }
  int solve(int s, int t) {
    int all = 0;
    while(1LL) {
      dyk(s);
      for(auto& i : j) {
        i = 0;
      }
      int r = dfs(s, t, s, inf);
      if(r == 0) {
        return all;
      }
      all += r;
    }
  }
};
*/

bool dp[19191];

signed main() {
  int n;
  cin >> n;
  rep(i, 19191) {
    dp[i] = false;
  }
  dp[0] = true;
  rep(i, n) {
    int w;
    cin >> w;
    rrep(j, 19191 - w) {
      if(dp[j]) {
        dp[j + w] = true;
      }
    }
  }
  int ans = 0;
  rep(i, 19191) {
    if(i % 10 != 0 && dp[i]) {
      ans = i;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256