akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define P pair<int, int>
#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define GI(name) \
  int(name);     \
  scanf("%d", &(name))
#define GI2(name1, name2) \
  int(name1), (name2);    \
  scanf("%d %d", &(name1), &(name2))
#define GI3(name1, name2, name3) \
  int(name1), (name2), (name3);  \
  scanf("%d %d %d", &(name1), &(name2), &(name3))
#define GVI(name, size)    \
  vector<int>(name)(size); \
  FOR(i, (size)) scanf("%d", &(name)[i])
#define GS(name) \
  string(name);  \
  cin >> (name);
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  FOR(i, v.size() - 1) { ret += to_string(v[i]) + ","; }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

int main() {
  GI2(A, B);
  print((A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0) ? "Possible"
                                                       : "Impossible");
  return 0;
}

Measured memory_bytes: 256
//codeforces
#include <algorithm>
#include <vector>
#include <string>
#include <ctype.h>
#include <set>
#include <map>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<time.h>
#include<string>
#include<stack>
#include<cmath>
#include<iostream>
#include<cstring>
#include<complex>
#include<bitset>
#include <climits>
#include<tr1/unordered_set>
#include<tr1/unordered_map>


#define FOR(i,j,k) for(int i=j;i<k;i++)
#define FORD(i,j,k) for(int i=j;i>=k;i--)
#define ll long long
//Make sure no overflow problems
//#define int long long
#define pii  pair<int, int>
#define vi vector<int >
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define VAR(i,n) __typeof(n) i = (n)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();i++)
#define FORDEACH(i,c) for( VAR(i,(c).rbegin()),i!=(c).rend();i++)
#define REP(i,n) FOR(i,0,n)
#define ld long double
const int INF = 1e9+7;
const long long INFLL = (ll)INF * (ll)INF;
const ld EPS = 10e-9;

using namespace std;

class TrieNode{
    public:
    bool isword;
    char c;
    map<char,TrieNode*> m;
    string word;
    public:
    TrieNode(){}
    TrieNode(char ch){
        c=ch;
        isword=false;
    }
};

void insert(TrieNode* root,string word){
    TrieNode* temp=root;
    for(char c:word){
        if(temp->m.find(c)==temp->m.end())
            temp->m[c]=new TrieNode(c);
        temp=temp->m[c];
    }
    temp->isword=true;
    temp->word=word;
}

#pragma GCC optimize ("Ofast")
static auto _ = [] { std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); std::cerr.tie(0); return 0; } ();

int main() {
    int n;
    cin>>n;
    vector<int> v(n),dp(n,INT_MAX);
    for(int i=0;i<n;i++)
        cin>>v[i];
    dp[0]=0;

    for(int i=0;i<n;i++){
        if(i+1<n)
            dp[i+1]=min(dp[i+1],dp[i]+abs(v[i]-v[i+1]));
        if(i+2<n)
            dp[i+2]=min(dp[i+2],dp[i]+abs(v[i]-v[i+2]));
    }

    cout<<dp[n-1];
    return 0;
}


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


using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int oo = 1e9 + 7;
const int mod = 1e9 + 7;

ll modulo(ll a, ll m){
    return (a + m)%m;
}

int main (){
    ll n, k, x, ans = 0;
    cin >> n >> k;

    vector<ll> ps(n+1);
    ps[0] = 0;

    for (int i=0; i<n; i++) cin >> x , ps[i+1] = ps[i]+x;

    map<int, int> hist;
    hist[0]++;
    for (int i=1; i<n+1; i++){
        if(i >= k ) hist[modulo(ps[i-k] - (i-k), k)]--;
        ans += hist[modulo(ps[i] - i, k)];
        hist[modulo(ps[i] - i, k)]++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11136
/*
 *  stay hungry, stay foolish, stay home.
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define ml cout<<"\n"
#define tc(w) ll w;cin>>w;while(w--)

#define pii pair<ll,ll>
#define vi  vector<ll>
#define vii vector<pii>
#define mi  map<ll,ll>
#define all(a)  (a).begin(),(a).end()

#define pb push_back
#define in insert
#define ff first
#define ss second
#define mod 1000000007

#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;
int main(){
	ios_base::sync_with_stdio(false);
     	cin.tie(NULL);
    	cout.tie(NULL);
    	ll n,k;cin>>n>>k;
    	ll ar[n+5];
    	rep(i,0,n){
    		cin>>ar[i];
    	}
    	ll dp[n+5]={0};
    	dp[0]=0;
    	
    	rep(i,1,n){
			dp[i] = INT_MAX;    		
    		for(ll j=i-1 ; j>=0 && (i-j)<=k ;--j){
    			dp[i] = min(dp[i] , abs(ar[i]-ar[j]) + dp[j]);
    		}
    		//cout<<dp[i]<<" ";
    	}

    	cout<<dp[n-1]<<endl;

	return 0;
		
}


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

int main(){
  string s; cin >> s;
  if(s=="AAA" || s=="BBB") cout << "No" << endl;
  else cout << "Yes" << endl;
return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
  int N, K;
  cin >> N >> K;
  vector<int> a(26,0);
  for(int i = 0; i < N; i++){
    string s;
    cin >> s;
    a[s[0]-'A']++;
  }
  int ans = 0;
  while(1){
    sort(a.begin(),a.end(),greater<int>());
    int n = 0;
    for(int i = 0; i < 26; i++){
      if(a[i] > 0){
        a[i]--;
        n++;
      }
      if(n >= K) break;
    }
    if(n >= K) ans++;
    else break;
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int K, X;
    cin >> K >> X;
    cout << (K * 500 >= X ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;

int main(void){
    ll N, M, a, co=0;
    cin>>N>>M;
    rep(i, M){
        cin>>a;
        co+=a;
    }
    if(co>N) cout<<-1<<endl;
    else cout<<N-co<<endl;
    return 0;
}

Measured memory_bytes: 3640
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<complex>
#include<set>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define fr(i,c) for(__typeof (c.begin()) i=c.begin(); i!=c.end(); i++)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define mp make_pair
#define dbg(x) cerr<<#x<<" = "<<x<<endl
using namespace std;

typedef vector<int> vi;
typedef long long ll;

const int inf=(int)1e9;
const double EPS=1e-9, INF=1e12;

const int mod = (int)1e9 + 7;
inline ll modpow(ll n, ll m, ll mod){
	ll res = 1;
	for(; m; m /= 2){
		if(m & 1) res = res * n % mod;
		n = n * n % mod;
	}
	return res;
}
ll fact[300010];
inline ll C(ll n, ll k){
	if(n < 0 || k > n) return 0;
	return (ll)fact[n] * modpow(fact[k], mod - 2, mod) % mod
		* modpow(fact[n-k], mod - 2, mod) % mod; 
}
ll calc(ll x, ll y){
	ll res = C(x + y, y);
	res = (res + mod - C(x + y, x - 1)) % mod;
	return res;
}
int main(){
	fact[0] = 1;
	rep(i, 300000) fact[i+1] = fact[i] * (i+1) % mod;

  int n, m, k;
  cin >> n >> m >> k;
  ll res = 0;
  rep(i, k + 1){
  	ll tmp = C(n + m + 2*k, m + 2*i) * calc(k - i, n + k - i) % mod * calc(i, m + i) % mod;
  	res = (res + tmp) % mod;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3180
n, h = map(int, input().split())
a, b = [], []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai), b.append(bi)
a.sort(), b.sort()

ans, amax = 0, a[-1]
for bi in b[::-1]:
    if bi <= amax or h<=0:
        break
    h -= bi
    ans += 1
print(ans + h // amax + (h % amax > 0) if h > 0 else ans)


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

typedef long long ll;

ll f(ll n){
	if(n%2==0) return n/2;
	else return 3*n +1;
}

ll a(ll i, ll s){
	if(i==1) return s;
	else return f(a(i-1,s));
}
 
int main(int argc, char const *argv[])
{
	ll s;
	cin >> s;
	vector<ll> list;
	list.assign(2*31,0);

	ll ans;
	for(ll m=1; m<=1000000; m++){
		if(list[a(m,s)]==0) list[a(m,s)]=1;
		else{
			ans = m;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

bool isPrime(int x);

int main() {
	int n;
	int x;
	int count = 0;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> x;

		if(isPrime(x))
			count++;	
	}

	cout << count << endl;
}

bool isPrime(int x) {
	if (x == 2)
		return true;
	else if (x < 2 || x % 2 == 0)
		return false;
	else {
		int j = 3;

		while (j <= sqrt(x)) {
			if (x % j == 0)
				return false;
			j = j + 2;		
		}	

		return true;
	}
}



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

int main() {
	int n, k; cin >> n >> k;
	if (n == 1) {
		char c; cin >> c;
		if (k % 2 == 0) cout << c << endl;
		else cout << (c == 'A' ? 'B' : 'A') << endl;
		return 0;
	}
	deque<int> q;
	for (int i = 0; i < n; ++i) {
		char c; cin >> c;
		q.push_back(c == 'A' ? 0 : 1);
	}
	int inv = 0, diff = 0;
	for (int i = 0; i + 1 < n; ++i) if (q[i] != q[i + 1]) ++diff;
	while (k > 0 && !(diff == n - 1 && (n % 2 == 1 || (q[0] ^ inv) == 1))) {
		int x = q.front() ^ inv;
		if (x == 0) {
			if (q[0] != q[1]) --diff;
			q.front() = 1 ^ inv;
			if (q[0] != q[1]) ++diff;
		} else {
			if (q[0] != q[1]) --diff;
			q.pop_front();
			inv ^= 1;
			if (inv != q.back()) ++diff;
			q.push_back(inv);
		}
		--k;
	}
	for (int i = 0; i < n; ++i) q[i] ^= inv;
	inv = 0;
	if (q[0] == 0) {
		if (k % 2 == 1) q[0] ^= 1;
	}
	//cout << k << endl;
	for (int i = 0; i < n; ++i) cout << ((q[i] ^ inv) == 0 ? 'A' : 'B');
	return 0;
}


Measured memory_bytes: 1280
#include<iostream>

using namespace std;

void tolower(string &a){
    for(int i = 0; i < a.length(); ++i){
        if(isupper(a[i])) a[i] += 32;
    }
}

string s, p;
int main(){
    int count = 0;
    cin >> p;
    tolower(p);
    while(true){
        cin >> s;
        if(s == "END_OF_TEXT") break;
        if(s.length() != p.length()) continue;
        tolower(s);
        int pos = 0;
        while(true){
            pos = s.find(p, pos);
            if(pos == -1) break;
            pos += p.length();
            ++count;
        }
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3208
n, a, b = map(int, input().split())
V = list(map(int, input().split()))
V.sort(reverse=True)

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
x = 0
y = 0
for i in range(n):
    if i <= a-1:
        ans += V[i]
        if V[i] == V[a-1]:
            x += 1
            y += 1
    else:
        if V[i] == V[a-1]:
            x += 1

if V[0] != V[a-1]:
    cnt = combinations_count(x, y)
    print(ans/a)
    print(cnt)
else:
    cnt = 0
    for i in range(a, b+1):
        if i <= x:
            cnt += combinations_count(x, i)
    print(ans/a)
    print(cnt)

Measured memory_bytes: 3064
import sys
input = lambda : sys.stdin.readline().rstrip()

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = []
for _ in range(m):
    bc.append(list(map(int, input().split())))
bc = sorted(bc, reverse=True, key=lambda x: x[1])
cnt = n
for b, c in bc:
    if cnt <= b:
        for i in range(cnt):
            a.append(c)
        break
    else:
        for i in range(b):
            a.append(c)
        cnt -= b
a = sorted(a, reverse=True)
print(sum(a[:n]))



Measured memory_bytes: 36804
n, m, k = map(int, input().split())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

Acum = [0]*n
Bcum = [0]*m
Acum[0] = A[0]
Bcum[0] = B[0]

for i in range(1,n):
  Acum[i] = Acum[i-1] + A[i]  
for i in range(1,m):
  Bcum[i] = Bcum[i-1] + B[i]

mx = 0

import bisect
for i in range(n+1):
  cnt = 0
  if i==0:
    rest = k
  else:
    rest = k - Acum[i-1]
    cnt = i
    if rest<0:continue
  
  idx = bisect.bisect_right(Bcum, rest)
  cnt += idx

  if cnt>mx:
    mx = cnt
    
print(mx)
#print(bisect.bisect_right([0,1], 0))

Measured memory_bytes: 47544
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll n, m;
    cin>>n>>m;
    ll x;
    string s;
    map<ll,ll>mp1, mp2;
    ll c = 0, p = 0;
    for(ll i=0; i<m; i++)
    {
        cin>>x;
        cin>>s;
        if(mp2[x] == 0 && s == "WA") mp1[x]++;
        if(mp2[x] == 0 && s == "AC")
        {
            mp2[x] = 1;
            p += mp1[x];
            c++;
        }
    }
    cout<<c<<" "<<p<<endl;
    return 0;
}


Measured memory_bytes: 16092
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int m;
const int maxn=2e5+7;
ll a[maxn],b[maxn];
int main()
{
	scanf("%d",&m);ll ans=0;ll sum=0;ll c=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&a[i],&b[i]);
		sum+=a[i]*b[i];c+=b[i];
	}
	cout<<(c-1)+((sum-1)/9)<<endl;
 } 

Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define endl '\n'

using namespace std;
typedef long long int ll;

string s;
int n, q;
char command[200000][2];

bool gotoleft(int i){
    int pointer = i;
    char nowchar = s[pointer];
    for(int i=0; i<q; i++){
        if(command[i][0] == nowchar){
            if(command[i][1] == 'L'){
                pointer --;
                if(pointer < 0){
                    return true;
                }
                nowchar = s[pointer];
            }else{
                pointer ++;
                if(pointer >= n){
                    return false;
                }
                nowchar = s[pointer];
            }
        }
    }

    return false;
}

bool gotoright(int i){
    int pointer = i;
    char nowchar = s[pointer];
    for(int i=0; i<q; i++){
        if(command[i][0] == nowchar){
            if(command[i][1] == 'L'){
                pointer --;
                if(pointer < 0){
                    return false;
                }
                nowchar = s[pointer];
            }else{
                pointer ++;
                if(pointer >= n){
                    return true;
                }
                nowchar = s[pointer];
            }
        }
    }

    return false;
}

int main(){

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

    cin >> n >> q;
    
    cin >> s;
    
    for(int i=0; i<q; i++){
        cin >> command[i][0] >> command[i][1];
    }

    if(n <= 3){
        int res_count = 0;
        for(int i=0; i<n; i++){
            if(gotoleft(i) || gotoright(i)){
                res_count++;
            }
        }

        cout << n - res_count << endl;
        return 0;
    }
    int left = 0; 
    int right = n-1;
    int leftans;
    while(true){
        bool res = gotoleft((right+left)/2);
        if(res==true){
            left = (right+left)/2;
        }else{
            right = (right+left)/2;
        }

        if(right-left==1){
            leftans = right;
            break;
        }
    }


    left = 0;
    right = n-1;
    int rightans;
    while(true){
        bool res = gotoright((right+left)/2);
        if(res==true){
            right = (right+left)/2;
        }else{
            left = (right+left)/2;
        }

        if(right-left==1){
            rightans = left;
            break;
        }
    }


    if(n-1-rightans+leftans> n){
        cout << 0 << endl;
    }else{
        cout << n - (n-1-rightans) - (leftans-0) << endl;
    }

    return 0;
}

Measured memory_bytes: 976
#include <iostream>
#include <cmath>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)

int main(){
	int N,K;
	cin >> N >> K;
	double ans = 0;
	REP(i,N){
		int tmp = i+1;
		double time = 1.0/N;
		while(tmp < K){
			tmp *=2;
			time/=2;
		}
		ans += time;
		//cout << pow(2,- time) << endl;
	}
	
	cout.precision(12);	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
/*

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    prayer
*/

// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

//nCr mod m
#define MOD 998244353ll
#define M 100000
// a^b mod MOD
ll powmod(ll a,ll b,ll m=MOD){
	ll out=1;
	ll p=a%m;
	while(b){
		if(b&1)out=out*p%m;
		p=p*p%m;
		b>>=1;
	}
	return out;
}
int dp[310][100000][2][2];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

    int n;
    cin>>n;
    vi in(n);
    rep(i,n)cin>>in[i];
    int sum=0;
    rep(i,n)sum+=in[i];
    rep(i,310)rep(j,100000)rep(k,2)rep(l,2)
        dp[i][j][k][l]=0;
    dp[0][0][0][0]=1;
    rep(i,n)rep(j,sum+1)rep(k,2)rep(l,2){
        (dp[i+1][j+in[i]][k][l]+=dp[i][j][k][l])%=MOD;
        (dp[i+1][j][k|1][l]+=dp[i][j][k][l])%=MOD;
        (dp[i+1][j][k][l|1]+=dp[i][j][k][l])%=MOD;
    }
    int out=powmod(3,n)-3*powmod(2,n)+3+3*MOD;
    out%=MOD;
    rep(i,sum+1)if(2*i>=sum)(out+=3*MOD-3*dp[n][i][1][1])%=MOD;
    cout<<out<<endl;
}


Measured memory_bytes: 969088
import scala.io.StdIn.{readLine,readInt}

object Main extends App {
    val n = readInt
    for(i <- 1 to n) {
      val Array(a,b,c) = readLine.split(" ").map(_.toInt).sorted
      if(a*a+b*b==c*c)
        println("YES")
      else
        println("NO")
    }
}

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

int main() {
  int n;
  cin >> n;
  vector<int> edge(n - 1, 0);
  vector<int> vertex(n + 1, 0);
  vector<tuple<int, int, int>> arr;
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    arr.emplace_back(a, b, i);
  }
  sort(arr.begin(), arr.end());
  int prev_vertex = 0;
  int color = 0;
  int colors = 0;
  for (auto elem : arr) {
    int a = get<0>(elem);
    int b = get<1>(elem);
    int i = get<2>(elem);
    if (a != prev_vertex) {
      color = 0;
      prev_vertex = a;
    }
    color++;
    if (color == vertex[a]) {
      color++;
    }
    edge[i] = color;
    vertex[b] = edge[i];
    if (color > colors) {
      colors = color;
    }
  }
  cout << colors << endl;
  for (int i = 0; i < n - 1; ++i) {
    cout << edge[i] << endl;
  }
}


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

int main()
{
	int N, D, answer = 0;
	cin >> N >> D;
	vector<vector<int>> X(N, vector<int>(D));
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < D; j++)
		{
			cin >> X.at(i).at(j);
		}
	}

	for(int i = 0; i < N - 1; i++)
	{
		for(int j = i + 1; j < N; j++)
		{
			int   temp = 0;
			int   intScrt;
			float floatScrt;

			for(int k = 0; k < D; k++)
			{
				temp += pow(X.at(i).at(k) - X.at(j).at(k), 2);
			}

			intScrt   = sqrt(temp);
			floatScrt = sqrt(temp);

			if(intScrt == floatScrt)
			{
				answer++;
			}
		}
	}

	cout << answer << endl;

	return 0;
}

Measured memory_bytes: 256
n, d = gets.split.map(&:to_i)

xs = []
n.times do
  xs << gets.split.map(&:to_f)
end

ans = 0
(0..n-2).each do |i|
  ((i+1)..n-1).each do |j|
    dis = 0
    (0..d-1).each do |dd|
      dis += (xs[i][dd] - xs[j][dd]) ** 2
    end
    val = Math.sqrt(dis)
    if val == val.to_i
      ans += 1
    end
  end
end
puts ans

Measured memory_bytes: 1788
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;
using static System.Console;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        solve();
    }
    static Scanner cin;

    static int N;
    static int[] X;
    static void input()
    {
        cin = new Scanner();
        N = cin.nextInt();
        X = cin.ArrayInt(N);
    }
    static void solve()
    {
        input();
        int[] copyX = (int[])X.Clone();
        Array.Sort(copyX);
        int l = copyX[N / 2 - 1];
        int r = copyX[N / 2];
        for(int i = 0; i < N; i++)
        {
            if (X[i] < r)
                WriteLine(r);
            else
                WriteLine(l);
        }


    }
    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }
        
        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }

        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for(int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for(int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }

        public double[] ArrayDounble(int N, int add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }
}

Measured memory_bytes: 34656
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <fstream>

using namespace std;

#define ll long long
#define INF 2000000000
#define LINF 9000000000000000000
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define dum(x) cout<<#x<<'='<<x<<endl
#define dum2(x,y) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<'\n'<<endl
#define dum3(x,y,z) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<'\n'<<endl
#define darr(arr,n) rep(i,(n-arr)){cout<<*(arr+i)<<' ';}cout<<endl
#define ddarr(arr,a,b) rep(i,a){rep(j,b){cout<<*(arr+i*b+j)<<' ';}cout<<endl;}

//ifstream in("Text.txt");cin.rdbuf(in.rdbuf());


int main() {
    int A, B;
    cin >> A >> B;


    cout <<(A<=8&&B<=8 ? "Yay!" : ":(" )<< endl;

}

Measured memory_bytes: 256
//# pragma GCC optimize ("O2")
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<climits>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
#include<iomanip>
#include<sstream>
#define out(i,a,now) for(int i=a.be[now],to=a.v[i];i;i=a.ne[i],to=a.v[i])
#define fo(i,a,b) for(i=a;i<=b;i++)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
#define mp(a,b) make_pair(a,b)
#define qk(x) memset(x,0,sizeof(x))
#define RG register
#define gs(x) (tr[tr[x].f].son[1]==x)
#define lb(x) (x&(-x))
#define mid ((l+r)>>1)
#ifdef Mogician
#endif
using namespace std;
typedef long long LL;
typedef double DB;
template <class T> void cmax(T &a,T b)
{
    a=max(a,b);
}
template <class T> void cmin(T &a,T b)
{
    a=min(a,b);
}
template <class T> void swp(T &a,T &b)
{
	T temp=a; a=b; b=temp;
}
int main()
{
#ifdef Mogician
	freopen("D.in","r",stdin);
#endif
	LL t;
	scanf("%lld",&t);
	while (t--)
	{
		LL a,b;
		scanf("%lld%lld",&a,&b);
		LL mul=a*b-1;
		LL k=sqrt(mul);
		if (k*k>mul) k--;
		LL ans=k*2;
		if (a!=b) ans--;
		if (k*(k+1)>mul) ans--;
		printf("%lld\n",ans);
	}
}

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

int main(){
  using ll = long long int ;
  ll n,k,s ;
  cin >> n >> k >> s ;
  if(s==1000000000){
    for(int i=0;i<n;i++){
      if(i<k) cout << s << " " ;
      else cout << 999999999 << " " ;
    }
  }else{
    for(int i=0;i<n;i++){
      if(i<k) cout << s << " " ;
      else cout << s+1 << " " ;
    }
  }
}

Measured memory_bytes: 1280
import sys
sys.setrecursionlimit(10**5)
def GCM(a, b):
  if a < b:
    a += b
    b = a-b
    a -= b
  if a % b == 0:
    return b
  else:
    return GCM(b, a%b)

N = int(input())
A = list(map(int, input().split()))
l2r =[]
r2l = []
g = A[0]
for a in A:
  g = GCM(g, a)
  l2r.append(g)
g = A[-1]
for a in reversed(A):
  g = GCM(g, a)
  r2l.append(g)
r2l = list(reversed(r2l))
ans = r2l[1]
for i in range(1, N-1):
  ans = max(ans, GCM(l2r[i-1], r2l[i+1]))
ans = max(ans, l2r[N-2])
print(ans)

Measured memory_bytes: 14052
N = int(input())
S = input()

right = 0
left = 0
for i in S:
    if i == '(':
        left += 1
    else:
        if left > 0:
            left -= 1
        else:
            right += 1

ans = ''
for i in range(right):
    ans += '('
ans += S
for i in range(left):
    ans += ')'

print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <string>

using namespace std;

void solve();

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

void solve() {
    int h1,h2;
    cin >> h1 >> h2;
    int k1,k2;
    cin >> k1 >> k2;
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    int ans1 = h1 * a + h2 * b + c * (h1 / 10) + d * (h2 / 20);
    int ans2 = k1 * a + k2 * b + c * (k1 / 10) + d * (k2 / 20);
    if(ans1 > ans2) cout << "hiroshi" << endl;
    else if(ans1 < ans2) cout << "kenjiro" << endl;
    else cout << "even" << endl;
}

Measured memory_bytes: 3172
def solve(m, k):
    if k >= 2**m:
        return -1
    if (m == 1) and (k == 0):
        return "0 0 1 1"
    if (m == 1) and (k == 1):
        return -1
    b = [x for x in range(2**m) if x != k]
    c = b[::-1]
    a = b + [k] + c + [k]
    return " ".join(map(str, a))

m, k = map(int, input().split())
print(solve(m, k))

Measured memory_bytes: 29456
n, m = list(map(int, input().split()))

MOD = pow(10, 9) + 7

dp = [0] * (n+1)

dp[0] = 1

broken = [False] * (n+1)
for i in range(m):
    broken[int(input())] = True

c = 1

for i in range(1, n+1):
    if broken[i]:
        dp[i] = 0
    else:
        if i == 1:
            dp[i] = dp[i-1] % MOD
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD

print(dp[-1] % MOD) 


Measured memory_bytes: 13304
#include <bits/stdc++.h>
using namespace std;
long long ans=-1e18;
int N;
int m[333333];
long long v[333333], w[333333],s1,s2;
priority_queue<int>pq1,pq2;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>N;
    for(int i=0;i<3*N;i++){
        cin>>m[i];
        if(i<N)pq1.push(-m[i]),s1+=m[i];
        if(i>=2*N)pq2.push(m[i]),s2+=m[i];
    }
    for(int i=N;i<=2*N;i++){
        v[i]=s1;
        s1+=m[i];
        pq1.push(-m[i]);
        s1+=pq1.top();
        pq1.pop();
    }
    for(int i=2*N-1;i>=N-1;i--){
        w[i]=s2;
        s2+=m[i];
        pq2.push(m[i]);
        s2-=pq2.top();
        pq2.pop();
    }
    for(int i=N;i<=2*N;i++){
        ans=max(ans,v[i]-w[i-1]);
    }
    cout<<ans;
 
    return 0;
}

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

int main(){
  int N,K;
  long long res;
  cin >> N >> K;
  res = K;
  for(int i=2;i<=N;i++)
    res *= (K-1);
  cout << res << endl;
  
  return 0;
  
}

Measured memory_bytes: 3596
N, M = map(int, input().split())

A = []
B = []
buff = [0 for i in range(N+1)]
buff2 = [0 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.append(b)
        # buff[b] = 1
        buff[b] = 1
    if b == N:
        B.append(a)
        buff2[a] = 1

for i in range(N+1):
    if buff[i] == 1 and buff2[i] == 1:
        print('POSSIBLE')
        exit()



# print(buff)
# print(buff2)

# seikai1 = []
# for i in range(N+1):
#     if buff[i] == 1:
#         seikai1.append(i)

# for i in range(N+1):
#     if buff2[i] == 1:
#         if i in seikai1:
#             print('POSSIBLE')
#             exit()
# for i in range(len(buff)):
#     for j in range(len(buff2)):
#         if buff[i] == 1 and buff2[j] == 1:
#             print('POSSIBLE')
#             exit()

print('IMPOSSIBLE')



Measured memory_bytes: 62412
#include <iostream>
#include <string>
#include <queue>

struct Card{
    std::string mark;
    int value;
    void out(bool isN){
        std::cout << mark << value;
        if(isN){
            std::cout << std::endl;
        }else{
            std::cout << " ";
        }
    }
};

void bubbleSort(Card A[],int N){
    bool flag = true;
    std::string tmpm;
    int tmp;
    while(flag){
        flag = false;
        for(int i=N-1;i>0;i--){
            if(A[i].value<A[i-1].value){
                tmp = A[i].value;
                tmpm = A[i].mark;
                A[i].value = A[i-1].value;
                A[i].mark = A[i-1].mark;
                A[i-1].value = tmp;
                A[i-1].mark = tmpm;
                flag = true;
            }
        }
    }
}

void selectionSort(Card A[], int N){
    int min;
    std::string tmpm;
    int tmp;
    for(int i=0;i<N;i++){
        min = i;
        for(int j=i;j<N;j++){
            if(A[min].value>A[j].value){
                min = j;
            }
        }
        if(i!=min){
            tmp = A[i].value;
            tmpm = A[i].mark;
            A[i].value = A[min].value;
            A[i].mark = A[min].mark;
            A[min].value = tmp;
            A[min].mark = tmpm;
        }
    }
}

int main(){
    int n;
    bool isStable = true;
    std::string judge;
    std::cin >> n;
    std::queue<std::string> qb[10];
    std::queue<std::string> qs[10];
    Card A[n];
    std::string tmp;
    for(int i=0;i<n;i++){
        std::cin >> tmp;
        A[i].mark = tmp[0];
        A[i].value = tmp[1]-48;
        qb[A[i].value].push(A[i].mark);
        qs[A[i].value].push(A[i].mark);
    }
    Card bubble[n];
    Card selection[n];
    for(int i=0;i<n;i++){
        bubble[i].value = A[i].value;
        bubble[i].mark = A[i].mark;
    }
    for(int i=0;i<n;i++){
        selection[i].value = A[i].value;
        selection[i].mark = A[i].mark;
    }
    bubbleSort(bubble,n);
    for(int i=0;i<n;i++){
        bubble[i].out(i==n-1);
        judge = qb[bubble[i].value].front();
        qb[bubble[i].value].pop();
        if(judge!=bubble[i].mark){
            isStable = false;
            break;
        }
    }
    if(isStable){
        std::cout << "Stable\n";
    }else{
        std::cout << "Not stable\n";
    }
    isStable = true;
    selectionSort(selection,n);
    for(int i=0;i<n;i++){
        selection[i].out(i==n-1);
        judge = qs[selection[i].value].front();
        qs[selection[i].value].pop();
        if(judge!=selection[i].mark){
            isStable = false;
        }
    }
    if(isStable){
        std::cout << "Stable\n";
    }else{
        std::cout << "Not stable\n";
    }
    return 0;
}


Measured memory_bytes: 3200
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
#define rep(i,n) for(int i=0; i<((int)n); i++)
#define REP(i,n) for(int i=0; i<=((int)n); i++)
#define srep(i,a,n) for(int i=a; i<((int)n); i++)
#define SREP(i,a,n) for(int i=a; i<=((int)n); i++)
#define rrep(i,n) for(int i=n-1; i>=0; i--)
#define RREP(i,n) for(int i=n; i>=0; i--)
#define INF 1000000000
const int mod = INF+7;

int main(){
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> A(Q);
  rep(i,Q){
    cin >> A[i];
    A[i]--;
  }

  vector<int> count(N);
  rep(i,Q){
    count[A[i]]++;
  }

  vector<int> point(N);
  rep(j,N){
    point[j]=K-(Q-count[j]);
    if(point[j]>0){
      printf("Yes\n");
    }
    else{
      printf("No\n");
    }
  }

}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int K;
    cin >> K;
    string S;
    cin >> S;
    int size = S.size();
    if (K >= size) {
        cout << S << endl;
    } else {
        string sub = S.substr(0, K);
        cout << sub << "..." << endl;
    }

    return 0;
}

Measured memory_bytes: 3632
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve(args);
    }

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();

        long a = scanner.nextLong();
        long b = scanner.nextLong();
        long c = scanner.nextLong();
        long d = scanner.nextLong();

        long cntCup = b/c;
        long cntCdown = (a-1)/c;
        long cntC = cntCup - cntCdown;

        long cntDup = b/d;
        long cntDdown = (a-1)/d;
        long cntD = cntDup - cntDdown;

        long e = lcm(c,d);
        long cntEup = b/e;
        long cntEdown = (a-1)/e;
        long cntE = cntEup - cntEdown;

        long cnt = b - a + 1 - cntC - cntD + cntE;
        System.out.println(cnt);

    }

    private static long gcd(long m, long n) {
        if(m < n) return gcd(n, m);
        if(n == 0) return m;
        return gcd(n, m % n);
    }

    private static long lcm(long m, long n) {
        return m * n / gcd(m, n);
    }

    private class MyScanner {
        String[] s;
        int i;
        BufferedReader br;
        String reg = " ";
        MyScanner () {
            s = new String[0];
            i = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public String next() {
            try {
                if (i < s.length) return s[i++];
                String line = br.readLine();
                while (line.equals("")) {line = br.readLine();}
                s = line.split(reg, 0);
                i = 0;return s[i++];
            } catch (Exception e) {e.printStackTrace();}
            return null;
        }
        public int nextInt() {
            try {return Integer.parseInt(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public double nextDouble() {
            try {return Double.parseDouble(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public long nextLong()  {
            try {return Long.parseLong(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
    }
}

Measured memory_bytes: 23252
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
template<typename V> constexpr typename V::value_type sum(const V &v) { return accumulate(all(v), 0); }
void solve();
main { solve(); return 0; }
// clang-format on

void solve() {
  vi v(5);
  rep(i, 5) cin >> v[i];
  sort(rall(v));
  printf("%d %d %d %d %d\n", v[0], v[1], v[2], v[3], v[4]);
}

Measured memory_bytes: 3168
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		final int height = sc.nextInt();
		final int width = sc.nextInt();
		
		String SHARP = "#";
		// create header
		System.out.println(createHeaderFooter(width, SHARP));
		
		// 
		String line = sc.nextLine();
		for( int i = 0; i < height ; i++ ){
			line = sc.nextLine();
			System.out.println(SHARP + line + SHARP);
		}
		
		System.out.println(createHeaderFooter(width, SHARP));
		
	}

	private static String createHeaderFooter(final int width, String SHARP) {
		StringBuilder sb = new StringBuilder();
		for( int i = 0; i <= width + 1 ; i++ ){
			sb.append(SHARP);
		}
		return sb.toString();
	}

}


Measured memory_bytes: 21332
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>

using namespace std;

typedef long long i64;
typedef i64 int_t;
typedef vector<int_t> vi;
typedef vector<vi> vvi;

typedef pair<int_t, int_t> pi;

#define tr(c, i) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#define REP(s, e, i) for(i=(s); i < (e); ++i)

i64 ds(i64 d) {
  i64 ans = 0;
  while(d != 0) {
    ans += d % 10;
    d /= 10;
  }
  return ans;
}

int main(int argc, char *argv[]) {
  i64 N, i;
  cin >> N;

  i64 ans = N;
  REP(1, N, i) {
    i64 j = N - i;

    ans = min(ans, ds(i) + ds(j));
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
int N;
  int cnt=0;
  int elm=0;
  cin >> N;
vector<int> d(N);
  for (int i=0;i<N;i++){
    int tmp;
  cin >> tmp;d[i]=tmp;
  }
  sort(d.begin(),d.end());
  for (int i=0;i<N;i++){
  if (d[i] > elm){
    cnt++;
    elm=d[i];
  }     
  }
  cout << cnt;
}
  

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int n, s[10], k, display;
  scanf("%d\n", &n);
  for (int i = 0; i < n; i++) {
    s[i] = getchar();
  }
  scanf("%d", &k);
  display = s[k - 1];
  for (int i = 0; i < n; i++) {
    if (s[i] == display) {
      putchar(s[i]);
    } else {
      putchar('*');
    }
  }
  puts("");
  return 0;
}


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

using namespace std;

#define LL long long
#define ULL unsigned LL
#define LD long double
#define debug(x) cerr << #x << " " << x << endl;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	reverse(s.begin(), s.end());
	int n = s.size();
	int ob = 0;
	unordered_map<int, LL> M;
	M[ob] = 1;
	int pot = 1;
	LL w = 0;
	for(int i=0; i<n; i++) {
		int y = s[i] - 48;
		ob+=(pot * y);
		ob%=2019;
		pot*=10;
		pot%=2019;
		M[ob]++;
		//cout<<ob<<"\n"<<pot<<"\n===\n";
	}
	for(int i=0; i<2019; i++) {
		w+=(M[i]*(M[i]-1)/2);
	}
	cout<<w;
}


Measured memory_bytes: 3784
#include<bits/stdc++.h>
using namespace std;
int ans[1000200];
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1; i*i<=n; ++i) {
		for(int j=1; j*j<=n; ++j) {
			for(int k=1; k*k<=n; ++k) {
				int t;
				t=i*i+j*j+k*k+i*j+i*k+j*k;
				ans[t]++;
			}
		}
	}
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
}

Measured memory_bytes: 3864
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int main(void){
    char s[1005],t[1005];
    int dif;
    int maxdif=999999;
    scanf("%s",s);
    scanf("%s",t);

    for(int i=0;strlen(s)-strlen(t)+1>i;i++){
        dif=0;
        for(int j=0;t[j]!='\0';j++){
            if(s[j+i]!=t[j]){dif++;}
        }
        if(dif==0){printf("0\n");return 0;}
        else if(maxdif>=dif){maxdif=dif;}
    }
    printf("%d\n",maxdif);
}


Measured memory_bytes: 1724
from collections import defaultdict
N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
now = 0
counter = defaultdict(int)
counter[now] += 1
roop = []
if 2*N >= K:
    # 普通にシミュレーション
    now = 0
    for i in range(K):
        now = A[now]
    print(now+1)
    exit()

for i in range(1, K+1):  # 1回目のテレポート
    now = A[now]
    counter[now] += 1  # その街に訪れたという証拠
    # ここからループが始まる
    if counter[now] == 2:  # 二度目の訪問なら
        roop.append(now)  # 始まりの土地

    if counter[now] == 3:
        tmp = i-1
        now = roop[-1]
        break


# print((K-tmp) % len(roop))  # 残りのループ回数
print(roop[(K-tmp) % len(roop)-1]+1)


Measured memory_bytes: 33924
<?php
 fscanf(STDIN, "%d",$N);
$list = fscanf(STDIN, str_repeat("%d", $N));


$s = 0;
$e = 0;
$ans = 0;
$sum = $xor = $list[$s];
while($e<$N){

    if($s === $N){
        break;
    }
    $xor = $sum;
    while($sum===$xor){
        $e++;
        if($e === $N){
            break;
        }
        $sum += $list[$e];
        $xor ^=$list[$e];
    }
    if($e-$s >1){
        $ans += (($e-$s-1) * ($e-$s)) >> 1;
    }else{
        $s++;
        if($s === $N){
            break;
        }
        $sum = $xor = $list[$s];
        continue;
    }
    if($e === $N){
        break;
    }
    while($sum!==$xor){
        $sum -= $list[$e];
        $sum -= $list[$s];
        $xor = $sum;
        $sum += $list[$e];
        $xor ^= $list[$e];
        $s++;
    }
    if($e !== $s + 1){
        $ans -= (($e-$s) * ($e-$s-1)) >> 1;
    }
    if($s === $N){
        break;
    }

}
echo $ans + $N;

Measured memory_bytes: 14836