akhauriyash/Code-Regression huggingface dataset:
unittest
{
	assert( [ "3 2", "1 7 2", "7 8 1", "8 12 1" ].parse.expand.solve == 2 );
	assert( [ "3 4", "1 3 2", "3 4 4", "1 4 3" ].parse.expand.solve == 3 );
	assert( [ "9 4", "56 60 4", "33 37 2", "89 90 3", "32 43 1", "67 68 3", "49 51 3", "31 32 3", "70 71 1", "11 12 3" ].parse.expand.solve == 2 );
	
	assert( [ "1 2", "1 7 2" ].parse.expand.solve == 1 );							// 追加ケース
	assert( [ "3 2", "12 16 2", "7 8 1", "8 12 1" ].parse.expand.solve == 2 );		// 追加ケース
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nc = input.front.split.to!( long[] );
	auto stcs = new long[ 3 ][ nc[ 0 ] ];
	foreach( ref stc; stcs )
	{
		input.popFront;
		stc = input.front.split.to!( long[] );
	}
	return tuple( stcs );
}

auto solve( long[ 3 ][] stcs )
{
	// 番組の開始と終了をプロット
	auto ds = new long[ 10L ^^ 5 + 1 ];
	auto tm = 0L;
	stcs.multiSort!( ( a, b ) => a[ 2 ] < b[ 2 ], ( a, b ) => a[ 0 ] < b[ 0 ] );
	while( !stcs.empty )
	{
		auto s = stcs.front[ 0 ];
		auto t = stcs.front[ 1 ];
		auto c = stcs.front[ 2 ];
		stcs.popFront;
		
		// 同じチャンネルの連続する番組は一つにまとめる
		while( !stcs.empty && c == stcs.front[ 2 ] && t == stcs.front[ 0 ] )
		{
			t = stcs.front[ 1 ];
			stcs.popFront;
		}
		
		ds[ s - 1 ]++;
		ds[ t ]--;
		tm = max( tm, t );
	}
	ds.length = tm + 1;
	
	// 同時に放送される番組の最大数（＝必要な録画機の最大数）を集計
	auto ans = 0L;
	auto dt = 0L;
	foreach( d; ds )
	{
		dt += d;
		ans = max( ans, dt );
	}
	return ans;
}


Measured memory_bytes: 5244
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
template<typename T> 
ostream& operator<<(ostream &os, const vector<T> &v) { 
    os << '{'; 
    for (const auto &x : v) os << gap << x;
        return os << '}'; 
}
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) {
        return os << '(' << p.first << gap << p.second << ')';
}

template <class T>
void read(T &x) {
    char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        ;
    for (x = 0; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + (c & 15);
}
#define ll long long 
#define lll __int128_t
#define pb push_back
#define mp make_pair
typedef pair < int,int> ii;
typedef vector<ii> vii;
typedef vector<ll>vl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll hashPrime = 1610612741;
ll Arr[500005];
ll lastpos[500005];
ll bit[500005];
void update(ll n,ll pos,ll val){
    for (; pos <= n;pos+=lastone(pos)){
        bit[pos] += val;
    }
}
ll query(ll pos){
    ll ans = 0;
    while(pos>0){
        ans += bit[pos];
        pos -= (lastone(pos));
    }
    return ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll i, j, n, m, k, l;
    cin >> n >> m;
    for (i = 1; i <= n;i++)
        cin >> Arr[i];
    memset(lastpos, -1, sizeof(lastpos));
    vector<pair<pair<ll, ll>, ll>> Q;
    map<pair<ll, ll>, ll> mp1;
    vector<ll> res(m + 1);
    for (i = 1; i <= m;i++){
        ll u, v;
        cin >> u >> v;
        //u--, v--;
        Q.pb({{v, u}, i});
        ///mp1[{v, u}] = i;
    }
    sort(Q.begin(), Q.end());
    ll ini = 0;
    for (i = 1; i <= n;i++){
        if(lastpos[Arr[i]]!=-1){
            update(n, lastpos[Arr[i]], -1);
        }
        update(n, i, 1);
        lastpos[Arr[i]] = i;
        while(ini<m){
            if(Q[ini].first.first!=i)
                break;
            ll temp1 = query(Q[ini].first.first);
            ll temp2 = query(Q[ini].first.second-1);
            res[Q[ini].second] = temp1 - temp2;
            /// cout << Q[ini].second << " " << Q[ini].first << " " << temp1 << " " << temp2 << "\n";
            ini++;
        }
    }
    for (i = 1; i <= m;i++)
        cout << res[i] << "\n";
    return 0;
}

Measured memory_bytes: 31224
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int x=sc.nextInt();
        int y=sc.nextInt();
        int z;
        for(;;){
            if(y==0){
                System.out.println(x);
                break; 
            }else{
                z=x;
                x=y;
                y=z%y;
        }   
    }
        sc.close();
    }
}


Measured memory_bytes: 26392
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS

readInt = fst . fromJust . BS.readInteger
readIntList = map readInt . BS.words

getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  [h, n] <- getIntList
  a <- getIntList
  putStrLn $ solve h a

solve h a = if sum a >= h then "Yes" else "No"

Measured memory_bytes: 2172
def func(x):
  for i in range(3):
    if len([x[i][j] for j in [0,1,2] if x[i][j]])==3:
      return True
    elif len([x[j][i] for j in [0,1,2] if x[j][i]])==3:
      return True
  if len([x[i][i] for i in [0,1,2] if x[i][i]])==3:
    return True
  elif len([x[i][j] for i,j in zip([0,1,2],[2,1,0]) if x[i][j]])==3:
    return True
  else:
    False
    
x = [[False]*3 for i in range(3)]
A = []
for _ in range(3): A += list(map(int, input().split()))
N = int(input())
for i in range(N):
  b = int(input())
  if b in A:
    i = A.index(b)
    j,k = i%3, i//3
    x[k][j] = True
  if func(x):
    print("Yes")
    break
else:
  print("No")

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

int main(){
  string s,t;
  cin >> s >> t;
  sort(s.begin(),s.end());
  sort(t.begin(),t.end());
  reverse(t.begin(),t.end());
  if(s<t)cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

#define MOD 1000000007

long long f(long long a)
{
	if(a==1) return 1;
	return a*f(a-1)%MOD;
}

int main()
{
	long long n,m;
	cin >> n >> m;
	long long ans=0;
	if(abs(n-m)>1)ans=0;
	else if(abs(n-m)==1)
	{
		ans=f(n)*f(m)%MOD;
	}
	else
	{
		ans=f(n)*f(m)*2%MOD;
	}
	cout << ans << endl;
}

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

int c[33], s[444][33];
int sc(int i, int t, const vector<int> &v) {
    int j = i - 1, k = i + 1;
    while(j >= 0 && v[j] != t)
        j--;
    while(k < v.size() && v[k] != t)
        k++;
    return s[i][t] + c[t] * (i - j) * (k - i);
}
int main() {
    int d;
    cin >> d;
    for(int i = 0; i < 26; i++)
        cin >> c[i];
    for(int i = 0; i < d; i++)
        for(int j = 0; j < 26; j++)
            cin >> s[i][j];
    vector<int> ss, tt;
    int M = -1e9;
    for(int a = 10; a < 16; a++) {
        for(int b = 0; b < 4; b++) {
            for(int z = 5; z < 16; z++) {
                int r = 0, l[33] = {};
                ss.clear();
                for(int i = 0; i < d; i++) {
                    auto m = 0.;
                    int t = 0;
                    for(int j = 0; j < 26; j++) {
                        double p = s[i][j];
                        p += c[j] * (i + 1 - l[j]) * .4 * a;
                        for(int k = 1; k < z; k++)
                            if(i + k < d)
                                p -= s[i + k][j] * (z - k) * .05 / z * b;
                        if(p > m)
                            m = p, t = j;
                    }
                    ss.push_back(t);
                    r -= c[t] * (i + 1 - l[t]) * (i - l[t]) / 2;
                    l[t] = i + 1;
                    r += s[i][t];
                }
                for(int j = 0; j < 26; j++)
                    r -= c[j] * (d + 1 - l[j]) * (d - l[j]) / 2;
                if(r > M)
                    M = r, tt.swap(ss);
            }
        }
    }
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<> rc(0, 25), r0(0, d - 1), r2(1, 6);
    uniform_real_distribution<> ru(0, 1);
    int cnt = 0;
    auto ti = clock();
    for(;;) {
        auto T = (clock() - ti) / 1.9 / CLOCKS_PER_SEC;
        if(T > 1)
            break;
        auto U = pow(2e3, 1 - T) * pow(6e2, T);
        for(int cn = 0; cn < 100; cn++, cnt++) {
            if(rc(mt) < 13) {
                int x0 = r0(mt), xc = rc(mt);
                int di = sc(x0, xc, tt) - sc(x0, tt[x0], tt);
                if(ru(mt) <= exp(di / U))
                    tt[x0] = xc, M += di;
                continue;
            }
            int x2 = r2(mt);
            uniform_int_distribution<> r1(0, d - 1 - x2);
            int x1 = r1(mt);
            x2 += x1;
            if(tt[x1] == tt[x2])
                continue;
            int di = -sc(x1, tt[x1], tt) - sc(x2, tt[x2], tt);
            swap(tt[x1], tt[x2]);
            di += sc(x1, tt[x1], tt) + sc(x2, tt[x2], tt);
            if(ru(mt) > exp(di / U))
                swap(tt[x1], tt[x2]);
            else
                M += di;
        }
    }
    for(int i : tt)
        cout << i + 1 << '\n';
    cerr << M << endl;
    cerr << cnt << endl;
    return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  double a, b, h, m;
  cin >> a >> b >> h >> m;
  
  complex<double> c1, c2;
  c1 = polar(a, (h * 30 + 0.5 * m) * M_PI / 180);
  c2 = polar(b, m * 6 * M_PI/ 180);
  
  cout << fixed << setprecision(10) << abs(c1 - c2) << '\n';
}

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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vvll = vector<vll>;
using vst = vector<st>;
using vchar = vector<char>;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
ll mod = 1000000007;

bool travel(ll dt, ll dx, ll dy){
  if(dt >= dx + dy)if((dt - dx - dy) % 2 == 0) return true;
  return false;
}

int main(){
  vll a(3);
  vin(a);
  sort(all(a));
  ll p = (a[2] - a[1]) / 2;
  ll q = (a[2] - a[0]) / 2;
  ll s = (a[2] - a[1]) % 2;
  ll t = (a[2] - a[0]) % 2;
  if(s + t == 0) cout << p + q << endl;
  else if(s + t == 1) cout << p + q + 2 << endl;
  else cout << p + q + 1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

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

  ll A,B,M;
  cin>>A>>B>>M;
  vector<ll> a(A),b(B);
  rep(i,A) cin>>a[i];
  rep(i,B) cin>>b[i];
  vector<ll> X(M),Y(M),C(M);
  rep(i,M) cin>>X[i]>>Y[i]>>C[i];

  ll mia=a[0];
  rep(i,A) chmin(mia,a[i]);
  ll mib=b[0];
  rep(i,B) chmin(mib,b[i]);

  ll ans=mia+mib;
  rep(i,M){
    X[i]--;Y[i]--;
    chmin(ans,a[X[i]]+b[Y[i]]-C[i]);
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vl;
typedef vector<int> vi;
#define PB push_back
#define MP make_pair
#define ln "\n"
#define forn(i,e) for(ll i=0; i<e; i++)
#define forsn(i,s,e) for(ll i=s; i<e; i++)
#define rforn(i,e) for(ll i=e; i>=0; i--)
#define rforsn(i,s,e) for(ll i=e; i>=s; i--)
#define vasort(v) sort(v.begin(), v.end())
#define vdsort(v) sort(v.begin(), v.end(),greater<int>())
#define F first
#define S second

#define out1(x1) cout << x1 << ln
#define out2(x1,x2) cout << x1 << " " << x2 << ln
#define out3(x1,x2,x3) cout << x1 << " " << x2 << " " << x3 << ln
#define out4(x1,x2,x3,x4) cout << x1 << " " << x2 << " " << x3 << " " << x4 << ln
#define out5(x1,x2,x3,x4,x5) cout << x1 << " " << x2 << " " << x3 << " " << x4 << " " << x5 << ln
#define out6(x1,x2,x3,x4,x5,x6) cout << x1 << " " << x2 << " " << x3 << " " << x4 << " " << x5 << " " << x6 << ln

#define in1(x1) cin >> x1
#define in2(x1,x2) cin >> x1 >> x2
#define in3(x1,x2,x3) cin >> x1 >> x2 >> x3
#define in4(x1,x2,x3,x4) cin >> x1 >> x2 >> x3 >> x4
#define in5(x1,x2,x3,x4,x5) cin >> x1 >> x2 >> x3 >> x4 >> x5
#define in6(x1,x2,x3,x4,x5,x6) cin >> x1 >> x2 >> x3 >> x4 >> x5 >> x6

#define arrin(a,n) forn(i,n) cin >> a[i];
#define arrout(a,n) forn(i,n) {cout << a[i] << " ";} cout << ln;

#define zoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
vl adj[100001];
vl d(100001,0);
vector<bool> visited(100001,false);
void dfs(ll s) {
    if (visited[s]) return;
    visited[s] = true;
// process node s
    for (auto u: adj[s]) {
        dfs(u);
        d[s]=max(d[s],d[u]+1);
    }
}

int main() {
    ll n,m;
    in2(n,m);
    ll u,v;
    forn(i,m){
        in2(u,v);
        adj[u].PB(v);
    }
    for(ll i=1;i<=n;i++) {
        if (!visited[i]) dfs(i);
    }
    ll a=0;
    for(ll i=1;i<=n;i++){
        a=max(a,d[i]);
    }
    out1(a);
    return 0;
}

Measured memory_bytes: 8576
Sa = input()
Sb = input()
Sc = input()
judge = Sa[0]
for _ in range(302):

    if judge == 'a':
        if len(Sa) == 0:
            print('A')
            exit()
        judge = Sa[0]
        Sa = Sa[1:]
        # print(Sa)
        # print(len(Sa))
    elif judge == 'b':
        if len(Sb) == 0:
            print('B')
            exit()
        judge = Sb[0]
        Sb = Sb[1:]
        # print(Sb)
        # print(len(Sb))
    elif judge == 'c':
        if len(Sc) == 0:
            print('C')
            exit()
        judge = Sc[0]
        Sc = Sc[1:]
        # print(Sc)
        # print(len(Sc))

    # if len(Sa) == 0:
    #     print('A')
    #     exit()
    # elif len(Sb) == 0:
    #     print('B')
    #     exit()
    # elif len(Sc) == 0:
    #     print('C')
    #     exit()


Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void file(){
#ifndef ONLINE_JUDGE
	freopen("a_input.txt", "r", stdin);
	freopen("a_output.txt", "w", stdout);
#endif
}
void fast()
{
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
}
int dx[] = { 0, 0, -1, 1, 1, 1, -1, -1 };
int dy[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
int main(){
	//file();
	fast();
	int n;
	cin >> n;
	string s;
	switch (n)
	{
	case 25:s = "Christmas"; break;
	case 24:s = "Christmas Eve"; break;
	case 23:s = "Christmas Eve Eve"; break;
	case 22:s = "Christmas Eve Eve Eve"; break;
	//default:break;
	}
	cout << s << endl;
}

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

const int N = 1010;
int cntb[N][N], cntw[N][N];
int preb[N][N], prew[N][N];

int Sumb(int a, int b, int c, int d ) {
  if ( a > c || b > d ) return 0;
  int num = 0;
  num += preb[c][d];
  if ( a > 0 && b > 0 ) num += preb[a-1][b-1];
  if ( a > 0 ) num -= preb[a-1][d];
  if ( b > 0 ) num -= preb[c][b-1];
  return num;
}
int Sumw(int a, int b, int c, int d ) {
  if ( a > c || b > d ) return 0;
  int num = 0;
  num += prew[c][d];
  if ( a > 0 && b > 0 ) num += prew[a-1][b-1];
  if ( a > 0 ) num -= prew[a-1][d];
  if ( b > 0 ) num -= prew[c][b-1];
  return num;
}
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    int x, y, shift;
    char c;
    scanf("%d %d %c", &x, &y, &c);
    shift = x / k + y / k;
    x %= k;
    y %= k;
    if ( ( c == 'B' && shift % 2 == 0 ) || ( c == 'W' && shift % 2 == 1 ) ) cntb[x][y]++;
    else cntw[x][y]++;
  }
  preb[0][0] = cntb[0][0];
  prew[0][0] = cntw[0][0];
  for (int i = 1; i < k; i++) {
    preb[0][i] = cntb[0][i] + preb[0][i-1];
    preb[i][0] = cntb[i][0] + preb[i-1][0];
    prew[0][i] = cntw[0][i] + prew[0][i-1];
    prew[i][0] = cntw[i][0] + prew[i-1][0];
  }
  for (int i = 1; i < k; i++) {
    for (int j = 1; j < k; j++) {
      preb[i][j] = cntb[i][j] + preb[i-1][j] + preb[i][j-1] - preb[i-1][j-1];
      prew[i][j] = cntw[i][j] + prew[i-1][j] + prew[i][j-1] - prew[i-1][j-1];
    }
  }
  // for (int i = 0; i < k; i++) {
  //   for (int j = 0; j < k; j++) {
  //     cout << cnt[i][j] << ' ';
  //   }
  //   cout << "\n";
  // }
  int ans = 0;
  for (int i = 1; i <= k; i++) {
    for (int j = 1; j <= k; j++) {
      // black is (i,j)
      int num = 0;
      num += Sumb(i,j,k-1,k-1); // []
      num += Sumb(0,0,i-1,j-1);
      num += Sumw(i,0,k-1,j-1);
      num += Sumw(0,j,i-1,k-1);
      ans = max( ans, num );
      num = 0;
      num += Sumw(i,j,k-1,k-1); // []
      num += Sumw(0,0,i-1,j-1);
      num += Sumb(i,0,k-1,j-1);
      num += Sumb(0,j,i-1,k-1);
      ans = max( ans, num );
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 16128
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"sort"
	"strconv"
)

func main() {
	sc := NewScanner(os.Stdin)
	X := sc.NextInt()
	Y := sc.NextInt()
	Z := sc.NextInt()
	K := sc.NextInt()
	A := make([]int, X)
	B := make([]int, Y)
	C := make([]int, Z)
	for i := 0; i < X; i++ {
		A[i] = sc.NextInt()
	}
	for i := 0; i < Y; i++ {
		B[i] = sc.NextInt()
	}
	for i := 0; i < Z; i++ {
		C[i] = sc.NextInt()
	}
	AB := make([]int, X*Y)
	for i := 0; i < X; i++ {
		for j := 0; j < Y; j++ {
			AB[Y*i+j] = A[i] + B[j]
		}
	}
	sort.Ints(AB)

	all := make([]int, len(C)*min(K, len(AB)))
	for i := 0; i < min(K, len(AB)); i++ {
		for j := 0; j < len(C); j++ {
			all = append(all, AB[len(AB)-1-i]+C[j])
		}
	}

	sort.Ints(all)
	for i := 0; i < K; i++ {
		fmt.Println(all[len(all)-1-i])
	}

}

func vmin(v []int) int {
	mn := math.MaxInt32
	for i := 0; i < len(v); i++ {
		mn = min(mn, v[i])
	}
	return mn
}

func lcm(x, y int) int {
	x, y = max(x, y), min(x, y)
	if y == 0 {
		return x
	}
	return lcm(y, x%y)
}

func max64(x, y int64) int64 {
	if x > y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// scanner
type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner(r io.Reader) *Scanner {
	rdr := bufio.NewReaderSize(r, 1024)
	return &Scanner{r: rdr}
}

func (s *Scanner) ReadLine() {
	s.buf = make([]byte, 0)
	for {
		line, isp, err := s.r.ReadLine()
		if err != nil {
			os.Exit(1)
		}
		s.buf = append(s.buf, line...)
		if !isp {
			break
		}
	}
}

func (s *Scanner) NextInt64() int64 {
	i, err := strconv.ParseInt(s.Next(), 10, 64)
	if err != nil {
		os.Exit(1)
	}
	return i
}

func (s *Scanner) NextInt() int {
	i, err := strconv.Atoi(s.Next())
	if err != nil {
		os.Exit(1)
	}
	return i
}

func (s *Scanner) NextFloat64() float64 {
	i, err := strconv.ParseFloat(s.Next(), 64)
	if err != nil {
		os.Exit(1)
	}
	return i
}

func (s *Scanner) Next() string {
	s.Pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	next := string(s.buf[start:s.p])
	s.p++
	return next
}

func (s *Scanner) Pre() {
	if s.p >= len(s.buf) {
		s.ReadLine()
		s.p = 0
	}
}


Measured memory_bytes: 185216
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include<algorithm>
#include<sstream>
#include<iomanip>
#include<deque>
#include<list>


using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const ll MOD_CONST = 1000000007;
const ll BIG_NUM = 1000000000000000000;
const int BIG_INT = 1000000000;


struct  UnionFind
{
	vector<int> par;
	vector<int> s;

	UnionFind(int n) :par(n) ,s(n){
		for (int i = 0; i < n;i++) {
			par[i] = i;
			s[i] = 1;
		}
	};

	int root(int x) {
		if (par[x] == x) {
			return x;
		}
		par[x] = root(par[x]);
		return par[x];
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) {
			return;;
		}

		par[rx] = ry;
		s[ry] += s[rx];
	}

	bool same(int x, int y) {
		return root(x) == root(y);
	}
	
	int size(int x) {
		return s[root(x)];
	}
};

int main() {
	int n, m, k;
	cin >> n >> m >> k;

	UnionFind uf = UnionFind(n);

	vector<set<int>> adj(n);
	for (int i = 0; i < m;i++) {
		int a, b;
		
		cin >> a >> b;
		a--;
		b--;
		uf.unite(a, b);
		adj[a].insert(b);
		adj[b].insert(a);
	}

	
	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		if (uf.same(a, b)) {
			adj[a].insert(b);
			adj[b].insert(a);
		}
	}

	for (int i = 0; i < n; i++) {
		
		cout << (uf.size(i) - adj[i].size()-1) << " ";
	}

}



Measured memory_bytes: 25856
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1e18;
//const ll mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    map<ll, ll> mp;
    ll sum = 0;
    for(int i = 0; i < N; i++) {
        ll a;
        cin >> a;
        sum += a;
        mp[a]++;
    }
    ll Q;
    cin >> Q;
    while(Q--) {
        ll b, c;
        cin >> b >> c;
        sum -= b * mp[b];
        sum += c * mp[b];
        mp[c] += mp[b];
        mp[b] = 0;
        cout << sum << endl;
    }
    return 0;
}


Measured memory_bytes: 9524
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

sys.setrecursionlimit(10**6)
def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]

def nck(n, k, mod):
    bunbo = bunshi = 1
    for i in range(k):
        bunshi = (bunshi * (n-i)) % mod
        bunbo = (bunbo * (i+1)) % mod
    return (bunshi * pow(bunbo, mod-2, mod)) % mod

N = z()
s = []
M,A,R,C,H = 0, 0, 0, 0, 0
for i in range(N):
    tmp = S()
    if (tmp[0] == 'M'):
        M+=1
    elif (tmp[0] == 'A'):
        A+=1
    elif (tmp[0] == 'R'):
        R+=1
    elif (tmp[0] == 'C'):
        C+=1
    elif (tmp[0] == 'H'):
        H+=1
ans = M*A*R + M*A*C + M*A*H + M*R*C + M*R*H \
     + M*C*H + A*R*C + A*C*H + R*C*H+ A*R*H
print(ans)

Measured memory_bytes: 27124
/**
 *    author:  FromDihPout
 *    created: 2020-06-19
**/

#include <bits/stdc++.h>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    int n = (int) s.length();
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long num = 0;
        for (int j = i; j < n; j++) {
            num *= 10;
            num += s[j] - '0';
            long long plus_spots = max(i - 1, 0) + max(n - j - 2, 0);
            ans += num * pow(2, plus_spots);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4048
def solve(h):
    if len(h) == 0:
        return 0
    if len(h) == 1:
        return h[0]
    if len(h) == 2:
        return max(h)

    mn = min(h)
    x = -1
    for i in range(len(h)):
        if h[i] == mn:
            x = i
        h[i] -= mn
    return mn + solve(h[:x]) + solve(h[x + 1:])

n = int(input())
h = [int(i) for i in input().split(' ')]

print(solve(h))


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}


int32 ceild(int32 a, int32 b){
	return (a+b-1)/b;
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int32 N, K;
	cin >> N >> K;
	vector<int32> A(N);
	REP(i, N) cin >> A[i];
	int32 in = -1;
	REP(i, N) if(A[i] == 1) in = i;
	int32 res = 0;
	if(N == K){
		cout << 1 << endl;
		return 0;
	}
	int32 in2 = ceild(in, K-1)*(K-1);
	cout << ceild(in, K-1)+ceild(N-in2-1, K-1) << endl;
}

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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vll = vector<ll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	for (auto &u : v) os << u << el;
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}

int main() {
	int K, Q; cin >> K >> Q;
	vll D(K); cin >> D;	
	
	while (Q--) {
		vll dm(K);
		ll n, x, m;
		cin >> n >> x >> m; x %= m;
		//全て含む所
		ll num = 0;
		ll sum = 0;

		//一部
		ll numk = 0;
		ll sumk = 0;

		//0 はこわい dm[i] = 0になるようなものが何個あるのか数える
		for (int i = 0; i < K; i++) {
			dm[i] = D[i] % m;
			if (dm[i] == 0) num++;
			sum += dm[i];
		}
		ll loop = (n-1) / K;
		ll rema = (n-1) % K;
		for (int i = 0; i < rema; i++) {
			if (dm[i] == 0) numk++;
			sumk += dm[i];
		}

		sum = sum * loop + sumk;
		num = num * loop + numk;

		//cout << sum << " " << num << " " << endl;
		//何回下がったかの計算が出来る
		cout << (n-1) - (sum + x) / m - num << endl;
	}
	return (0);
}


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

int main(){

    int N;
    cin >> N;
    int h[N];
    for(int i = 0; i < N; i++){
        cin >> h[i];
    }

    int cost[N];
    cost[0] = 0;
    cost[1] = abs(h[1] - h[0]);

    for(int i = 2; i<N; i++){
        cost[i] = min(cost[i-1] + abs(h[i] - h[i-1]),
                      cost[i-2] + abs(h[i] - h[i-2]));
    }

    cout << cost[N-1] << endl;
}

Measured memory_bytes: 1024
using System;
using System.Linq;

namespace AtCoder0711
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            int ans = 0;

            for(var i = 0; i < N; i++)
            {
                if((i+1) %2 == 1 && a[i]%2==1) { ans++; }
            }

            Console.WriteLine(ans);
        }
    }
}


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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n, a, b;
  cin >> n >> a >> b;
  int cnt = 0;
  reps(i, 1, n+1) {
    int sum = 0;
    int x = i;
    while(x > 0) {
      sum += x%10;
      x /= 10;
    }
    if(a <= sum && sum <= b) cnt += i;
  }
  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 256
import math
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        ans += math.sqrt(sum((X[i][k]-X[j][k])**2 for k in range(D))).is_integer()
print(ans)

Measured memory_bytes: 3060
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		long a = Long.parseLong(sc.next());
		long sum = 100;
		long count = 0;
		while(a > sum) {
			sum *= 1.01;
			count++;
		}
		System.out.print(count);
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
}

Measured memory_bytes: 32292
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scanner = new Scanner(System.in);
		int h = scanner.nextInt();
		int w = scanner.nextInt();
		char[][] ary = new char[h][w];
		boolean flg = false;
		for(int n = 0; n < h; n++) {
			String tmp = scanner.next();
			for(int r = 0; r < w; r++) {
				ary[n][r] = tmp.charAt(r); 
			}
		}
		
		for(int s = 0; s < h; s++) {
			for(int t = 0; t < w; t++) {
				if(ary[s][t] == '#') {
					if(s != 0) {
						if(ary[s-1][t] == '#') continue;
					}
					if(t != 0) {
						if(ary[s][t-1] == '#') continue;
					}
					if(s != h-1) {
						if(ary[s+1][t] == '#') continue;
					}
					if(t != w-1) {
						if(ary[s][t+1] == '#') continue;
					}
				 
					flg = true;
				}
			}
			if(flg) break;
		}
		if(!flg) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<char> s(n);
    for(int i=0;i<n;i++){
        cin >> s.at(i);
    }
    sort(s.begin(),s.end());

    cout << (s.at(n-1)!='Y'?"Three":"Four") << endl;

}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n, m, a[2000], b[2000], c[2000];
LL d[1000];
LL const INF = 8000000000000001LL;

int main() {
	cin >> n >> m;
	inc(i, m) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--; b[i]--;
	}
	
	inc(i, n) { d[i] = -INF; }
	d[0] = 0;
	
	bool inf = false;
	inc(q, n * 2) {
		bool cont = false;
		inf = false;
		inc(i, m) {
			bool flag = setmax(d[ b[i] ], d[ a[i] ] + c[i]);
			cont |= flag;
			if(flag && q >= n && b[i] == n - 1) { inf = true; }
		}
		if(! cont) { break; }
	}
	
	if(inf) { cout << "inf" << endl; }
	else { cout << d[n - 1] << endl; }
	
	return 0;
}


Measured memory_bytes: 256
from fractions import gcd
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])

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

    return arr

a,b = map(int,input().split())
c = gcd(a,b)
d = factorization(c)
print(len(d)+1-(c==1))

Measured memory_bytes: 5048
use std::io;

fn main() {
    let words = read_vec::<String>();
    let mut num   = read_vec::<i32>();

    if words[0] == read::<String>() {
        num[0] = num[0] - 1;
    } else {
        num[1] = num[1] - 1;
    }
    println!("{} {}", num[0], num[1]);
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut line = String::new();
    io::stdin().read_line(&mut line)
        .ok()
        .expect("Faild to read Vec");
    line.trim().split_whitespace()
        .map(|i| i.parse().ok().unwrap()).collect()
}

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


Measured memory_bytes: 4352
#include <iostream>
#include <utility>
#include <algorithm>

using namespace std;

int main(void) {
  long long int a, b, c;
  cin >> a >> b >> c;
  
  if(a % 2 != 0 && b % 2 != 0 && c % 2 != 0) {
    long long int m = max(max(a, b), c);
    if(m == a) {
      cout << b * c << endl;
    }
    else if(m == b) {
      cout << a * c << endl;
    }
    else {
      cout << a * b << endl;
    }
  }
  else {
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define gt(n) scanf("%d", &n)
#define gtll(n) scanf("%ld", &n)
#define out(n) printf("%d", n)
#define outll(n) printf("%ld", n)
#define loop(n) for(int i=0; i<n; i++)
#define MAXX 1001
#define mem(x, y) memset(x, y, sizeof(x))
#define loop1(n) for(int i=1; i<=n; i++)
#define ll long long
#define pb push_back
#define pi acos(-1)
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
//(only in c)char[33];itoa(n,buffer,base);printf("%s",buffer);
#define dec_to_bin(n) std::string binary = std::bitset<64>(n).to_string();
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
int main()
{
fast;
int n;
cin>>n;
int val[n+7],cost[n+7];
int mx=0;
for(int i=0;i<n;i++){
cin>>val[i];
}
for(int i=0;i<n;i++){
cin>>cost[i];
}
for(int i=0;i<n;i++){
if(val[i]>cost[i]){
        mx+=val[i]-cost[i];
}
}
cout<<mx<<endl;
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
struct edge {int /*from,*/to,cost;};
typedef long long ll;
typedef pair<int,int> P;
typedef pair<pair<int,int>,int> PP;
typedef vector<int> VI;
typedef vector<long long int> VL;
typedef vector<edge> VE;
//static const int INF = 2147483647;
//static const long long INF = 9223372000000000000;
//static const long long INF = 9223372000000000000/2;
//static const long long INF = 9223372000000000000/2145;
//static const int INF = 1000010000;
//static const int NIL = -1;
//static const int MOD = 1000000007;
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define np next_permutation
#define pq priority_queue
#define int ll

signed main(){
    int n;
    VL a;
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        int tmp;
        scanf("%lld",&tmp);
        a.pb(tmp);
    }
    sort(all(a));

    VL b;
    for(int i=0;i+1<n;i++){
        int cur=a[i],nxt=a[i+1];
        if(cur==nxt){
            b.pb(cur);
            i++;
        }
    }

    if(b.size()<2){
        printf("0\n");
        return 0;
    }

    sort(all(b));
    reverse(all(b));
    printf("%lld\n",b[0]*b[1]);
    return 0;
}

Measured memory_bytes: 1908
#include <cstdio>  
using namespace std;  
int main() { 	
	int a,b,c; 	
	scanf("%d %d %d", &a, &b, &c); 	
	if(a<=c && b<=c){
		printf("%d", a+b);
	}
	else if(b<=a && c<=a){
		printf("%d", b+c);
	}
	else if(c<=b && a<=b){
		printf("%d", a+c);
	}
	
} 

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

int main() {
  int64_t x, k, d, n;
  cin >> x >> k >> d;
  x = abs(x);
  n = k - x/d;
  if(n <= 0) {
    x -= d*k;
  }
  else {
    x %= d;
    if(n%2==1)
      x = d-x;
  }
  cout << x << endl;
}

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

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

    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        String S = scan.next();

        char[] data = S.toCharArray();
        int len = data.length;
        if (!is_kaibun(S, 0, len)) {
            System.out.println("No");
            return;
        }
        if (!is_kaibun(S, 0, (len-1)/2)) {
            System.out.println("No");
            return;
        }
        if (!is_kaibun(S, (len+1)/2, len)) {
            System.out.println("No");
            return;
        }
        System.out.println("Yes");
    }

    private boolean is_kaibun(String S, int start, int end) {
        String org = S.substring(start, end);
        StringBuilder sb = new StringBuilder(org);
        String tran = sb.reverse().toString();
        return org.equals(tran);
    }
}


Measured memory_bytes: 21972
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    get!($($t),*)
        ).collect::<Vec<_>>()
    };
    ($t:ty |) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty | $n:expr) => {
        (0..$n).map(|_| get!($t |)).collect::<Vec<_>>()
    };
}
macro_rules! tern {
    ($condition: expr, $_true: expr, $_false: expr) => {
        if $condition {
            $_true
        } else {
            $_false
        }
    };
}

fn main() {
    let (A, B) = get!(u64, u64);
    if (A + B) % 2 == 0 {
        println!("{}", (A+B)/2);
    } else {
        println!("IMPOSSIBLE");
    }
}


Measured memory_bytes: 4352
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, sum[110], x, mx, mn;
int main(){
	scanf("%d", &n); memset(sum, 0, sizeof(sum));
	for(int i=1; i<=n; i++){scanf("%d", &x); sum[x]++;}
	for(int i=1; i<=n-1; i++)if(sum[i])mx=i;
	if(sum[mx]==1){printf("Impossible"); return 0;}
	if(mx==1){if(n==2)printf("Possible"); else printf("Impossible"); return 0;}
	mn=(mx+1)/2;
	for(int i=mn+1; i<=mx; i++){
		if(sum[i]<=1){printf("Impossible"); return 0;}
		sum[i]-=2;
	}
	if(mx&1)sum[mn]-=2; else sum[mn]--;
	if(sum[mn]<0){printf("Impossible"); return 0;}
	mn++; for(int i=1; i<=mn-1; i++)if(sum[i]){printf("Impossible"); return 0;}
	printf("Possible");
	return 0;
}

Measured memory_bytes: 128
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
A=LI()
MEMO = [[0]*(N+1) for i in range(N+1)]
turn = -1 if N%2 == 0 else 1
for i in range(N): MEMO[i][i+1] = turn*A[i] 

for wid in range(2, N+1):
    turn *= -1
    for i in range(N-wid+1):
        xy1 = MEMO[i+1][i+wid] + turn*A[i]
        xy2 = MEMO[i][i+wid-1] + turn*A[i+wid-1]
        MEMO[i][i+wid] = xy1 if turn*xy1 > turn*xy2 else xy2

print(MEMO[0][N])


Measured memory_bytes: 112604
N = int(input())
Alist = [0] + list(map(int,input().split()))
Sum = 0
for i in range(1,len(Alist)):
    Sum += abs(Alist[i] - Alist[i-1])
Sum += abs(Alist[-1])
Answer= []
for i in range(1,len(Alist)-1):
    Ans = Sum
    Ans = Ans - abs(Alist[i]-Alist[i-1]) - abs(Alist[i] - Alist[i+1]) + abs(Alist[i+1] - Alist[i-1])
    Answer.append(Ans)
Ans = Sum
Ans = Ans - abs(Alist[-1]) - abs(Alist[-1]-Alist[-2]) + abs(Alist[-2])
Answer.append(Ans)
for a in Answer:
    print(a)

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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

int main()
{
    int n; cin >> n;
    vector<int> s(n);
    rep(i,n) cin >> s[i];

    int q; cin >> q;
    vector<int> t(q);
    rep(i,q) cin >> t[i];

    sort(s.begin(), s.end());

    ll ans = 0;
    rep(i,q){
        if(lower_bound(s.begin(), s.end(), t[i]) != upper_bound(s.begin(), s.end(), t[i])){
            ans++;
        }
    }
    cout << ans << endl;
}


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


int main() 
{
	int N,ans=0;
	cin >> N;
	vector<int> aVec(N+1);
	for (int i = 0; i < N; i++)
	{
		cin >> aVec.at(i);
	}

	sort(aVec.begin(), aVec.end(),greater<int>());
	for (int i = 0; i < N; i = i+2)
	{
		ans += aVec.at(i) - aVec.at(i + 1);
	}
	cout << ans << endl;

}

Measured memory_bytes: 256
import sys
import os

def file_input():
    f = open('../Beginner_Contest_165/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    K=int(input())
    A,B=map(int, input().split())

    ok=0
    if K == 1:
        print('OK')
    elif B-A > K:
        print('OK')
    else:
        for i in range(A,B+1):
            if i%K==0:
                print('OK')
                ok=1
                break
        if ok==0:
            print('NG')

if __name__ == '__main__':
    main()


Measured memory_bytes: 9196
void main()
{
    long[] tmp = rdRow;
    long h = tmp[0], w = tmp[1];
    dchar[][] a = h.rdCol!(dchar[]);

    if (a[0][0] == '.')
    {
        "Impossible".writeln;
        return;
    }

    long y, x;
    a[0][0] = '.';
    while (y != h - 1 || x != w - 1)
    {
        bool down, right;
        if (y < h - 1) down = a[y+1][x] == '#';
        if (x < w - 1) right = a[y][x+1] == '#';

        if (!(down ^ right))
        {
            "Impossible".writeln;
            return;
        }

        if (down) ++y;
        if (right) ++x;
        a[y][x] = '.';
    }

    bool ok = true;
    foreach (i; 0 .. h)
    {
        foreach (j; 0 .. w)
        {
            if (a[i][j] == '#') ok = false;
        }
    }

    writeln(ok ? "Possible" : "Impossible");
}

T rdElem(T = long)()
{
    //import std.stdio : readln;
    //import std.string : chomp;
    //import std.conv : to;

    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;

dchar[] rdDchar()
{
    //import std.conv : to;

    return rdStr.to!(dchar[]);
}

T[] rdRow(T = long)()
{
    //import std.stdio : readln;
    //import std.array : split;
    //import std.conv : to;

    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    //import std.range : iota;
    //import std.algorithm : map;
    //import std.array : array;

    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    //import std.range : iota;
    //import std.algorithm : map;
    //import std.array : array;

    return iota(col).map!(x => rdRow!T).array;
}

void wrMat(T = long)(T[][] mat)
{
    //import std.stdio : write, writeln;

    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int cnt = 0;
    for (int i = 0; i < N; i++) {
      if (i + 1 != sc.nextInt()) {
        cnt++;
      }
    }
    if (cnt == 0 || cnt == 2) {
      System.out.println("YES");
    } else {
      System.out.println("NO");
    }
  }
}


Measured memory_bytes: 23892
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    A, B, C = map(int, readline().split())

    print(min(B // A, C))

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9100
import sys
input = sys.stdin.readline
N = int(input())

coin = [6**n for n in range(10) if 6**n <= N]
coin += [9**n for n in range(10) if 9**n <= N]

dp = [0] * (N+1)

for i in range(1,N+1):
    temp = []
    for c in coin:
        if i - c >= 0:
            temp.append(dp[i-c] + 1)
    dp[i] = min(temp)
print(dp[-1])

Measured memory_bytes: 3828
N,T=gets.split.map &:to_i
minc=1001
f=0
N.times{|i|
  c,t=gets.split.map &:to_i
  if t<=T then
    minc=[c,minc].min
    f=1
  end
}
puts (f==0)? "TLE": "#{minc}"

Measured memory_bytes: 1788