akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.text.*;
public class Main {
	public static void main(String args[]){
		Scanner in=new Scanner(System.in);
		for(int t=1,T=in.nextInt();t<=T;t++){
			//x^2+y^2 -2xi*x -2yi*y +xi^2+yi^2 =r^2
			//G[] =>  -2xi   -2yi    xi^2+yi^2
			double g[][]=new double[5][5];
			double x=0,y=0;
			for(int i=1;i<=3;i++){
				x=in.nextDouble();
				y=in.nextDouble();
				g[i][1]=-2*x;
				g[i][2]=-2*y;
				g[i][3]=x*x+y*y;
			}
			for(int i=2;i<=3;i++)
				for(int j=1;j<=3;j++)
					g[i][j]-=g[1][j];
			double a1=g[2][1],b1=g[2][2],c1=g[2][3];
			double a2=g[3][1],b2=g[3][2],c2=g[3][3];
			double x0=(b1*c2-b2*c1)/(b2*a1-b1*a2);
			double y0=(a1*c2-a2*c1)/(a2*b1-a1*b2);
			double r=Math.sqrt((x-x0)*(x-x0)+(y-y0)*(y-y0));
			DecimalFormat df=new DecimalFormat("0.000");
			System.out.println(df.format(x0)+" "+df.format(y0)+" "+df.format(r));
		}
		in.close();
	}
}

Measured memory_bytes: 28404
n=int(input())
s=input()
a=s.count('R')*s.count('G')*s.count('B')
for i in range(n-2):
  for j in range(i+1,i+1+(n-i-1)//2):
    k=j+j-i
    if s[i]!=s[j]!=s[k]!=s[i]:
      a=a-1
print(a)

Measured memory_bytes: 9192
#include<stdio.h>
#include<unordered_map>
#include<iostream>
using namespace std;

int main()
{
    long long int a=0;
    long long int b=0;
    long long int c=0;
    cin>>a;
    cin>>b;
    cin>>c;
    unordered_map<int,int> d;
    d.insert(pair<int,int>(a,1));
    d.insert(pair<int,int>(b,1));
    d.insert(pair<int,int>(c,1));
    cout<<d.size();
    return 0;
}

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

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define f first
#define s second


typedef long long ll;

const ll INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

const ll MAX = 3e5+10;

ll n, memo[19][MAX];
int v[MAX], w[MAX], vans[MAX];

vector<vector<pair<ll,ll>>> vq(MAX);

vector<vector<int>> erase(20);

int log(int x) {
    return 32 - __builtin_clz(x) - 1;
}

ll dp(int x, int L) {
	int pos = log(x);
	if(L < 0) return -LINF;
	if(!x) return 0;
	ll& p = memo[pos][L];
	erase[pos].push_back(L);
	if(p != -1) return p;

	return p = max(v[x]+dp(x/2, L-w[x]), dp(x/2, L));
}

void dfs(int x) {
	int pos = log(x);
	for(auto u : erase[pos]) memo[pos][u] = -1;
	erase[pos].clear();

	for(auto u : vq[x])
		vans[u.s] = dp(x,u.f);

	if(2*x <= n) dfs(2*x);
	if(2*x+1 <= n) dfs(2*x+1);
}

int main(){ _

	cin >> n;
	for(ll i=1; i<=n; i++) cin >> v[i] >> w[i];	

	ll q; cin >> q;
	for(ll i=0; i<q; i++) {
		ll vi, L; cin >> vi >> L;

		vq[vi].push_back({L,i});
	}

	memset(memo,-1,sizeof memo);
	dfs(1);

	for(ll i=0; i<q; i++) cout << vans[i] << endl;	

	return 0;
}


Measured memory_bytes: 73848
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef pair<double,double> PD;
typedef pair<int,P> ed;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;

ll pow(ll a,ll b) {
  ll res = 1;
  while(b > 0) {
    if(b&1) {
      res = (res*a);
    }
    a = (a*a);
    b >>= 1;
  }
  return res;
}
  
int main() {
  int N,K;
  cin >> N >> K;
  ll ans = K;
  ans *= pow(K-1,N-1);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
#ABC144 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
from itertools import product
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def f_x(x):
    s = 0
    for A,F in zip(a,f):
        s += max(0,A - x//F)
    if s <= k:
        return True
    return False


n,k = LI()
a = LI()
f = LI()
a.sort()
f.sort(reverse = True)
ok = 0
for A,F in zip(a,f):
    ok = max(ok,A*F)
ng = -1
while ok - ng > 1:
    mid = (ok + ng)//2
    if f_x(mid):
        ok = mid
    else:
        ng = mid
print(ok)

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




int main() {

            int n ; cin >> n ;
            int Arr [n+5];
             int cnt = 0 ;
             for ( int i = 1 ; i  <=  n ; i ++ ){
                    cin >> Arr[i];
             }

             for ( int i = 1 ; i <= n ; i+=2){
                 if ( Arr[i] % 2 ==1)
                     cnt ++;
             }
             cout << cnt << endl;

        return 0;
    }

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

int main(){
  int n;
  cin >> n;
  vector<int> x(10000);
  x.at(0) = n;
  for(int i=1; i<10000; i++){
    if(n%2 == 0){
      n /= 2;
    }else{
      n = 3*n+1;
    }
    for(int j=0; j<i; j++){
      if(n == x.at(j)){
        cout << i+1 << endl;
        return 0;
      }
    }
    x.at(i) = n;
  }
  return 0;
}


Measured memory_bytes: 256
W, H = map(int, input().split())

side = [{"cost":int(input()), "di":0}for i in range(W)] + [{"cost":int(input()), "di":1}for i in range(H)]
side = sorted(side, key=lambda x:x["cost"])
ans = 0
ty = [H+1,W+1]
for s in side:
    cost, di = s["cost"], s["di"]
    ans += ty[di] * cost
    ty[(di+1)%2] -= 1
print(ans)

Measured memory_bytes: 76008
#3 <= a <= 10000
def findthree(a):
    a = str(a)
    l = len(a)
    for i in range(l):
        if a[i]=="3":
            return True

a = int(input())
res = ""
for i in range(a):
    j = i + 1    
    if j%3==0 or findthree(j):
        res += " " + str(j)
print(res)


Measured memory_bytes: 5636
#include <bits/stdc++.h>
#define loop2(i, s, n, a) for (int i = int(s); i < int(n); i += a)
#define loop(i, s, n) loop2(i, s, n, 1)
#define rep(i, n) loop(i, 0, n)

#define pb push_back
#define all(in) in.begin(),in.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
    ll n, d, a; cin >> n >> d >> a;
    vector<pair<ll,ll>> data(n);
    rep(i,n){
        ll aa, bb; cin >> aa >> bb;
        data[i] = make_pair(aa,bb);
    }
    sort(all(data));
    vector<ll> x(n), h(n);
    rep(i,n){
        x[i] = data[i].first;
        h[i] = data[i].second;
    }

    ll ans = 0;
    vector<ll> attack(n+1,0);
    rep(i,n){
        if(h[i]-attack[i] <= 0){
            attack[i+1] += attack[i];
            continue;
        }
        ll count = (h[i]-attack[i]+a-1)/a;
        ans += count;
        ll k = upper_bound(all(x),x[i]+2*d)-x.begin();
        attack[i] += a*count;
        attack[k] -= a*count;
        attack[i+1] += attack[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 11180
#include <iostream>
#include <string>
#include <stdio.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cfloat>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <iomanip>

using namespace std;

#define ll long long
#define rep(i, n) for (long double i = 0; i < n; i++)
// #define req(j, n) for (ll j = 1; j < (n+1); j++)
// #define rer(k, n) for (ll k = 1; k < (n+1); k++)


int main()
{
    ll a;
    float b;
    ll ans;
    cin >> a >> b;
    int c;
    c = floor(100 * b + 0.1);
    ans = a*c/100;
    cout << ans << endl;
}


Measured memory_bytes: 3716
#include<stdio.h>
#include <stdlib.h>
int desc(const void *a, const void *b) {
  return *(int *)b - *(int *)a;
}

int main()
{
  int N,p=0,max=101;
  scanf("%d", &N);
  int a[N];
  for(int i=0;i<N;i++) a[i]=0;
  for(int i=0;i<N;i++) scanf("%d", &a[i]);
  qsort(a, sizeof(a) / sizeof(*a), sizeof(*a), desc);
  for(int i=0;i<N;i++){
    if(max>a[i]){
     max=a[i];
     p++;
    }    
  }
  printf("%d\n", p);
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;

const ll INF = 1LL<<60;

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

int main(){
  int n;
  cin >> n;
  vector<ll> dp(n+1,INF);
  dp[0] = 0;
  for(int i=1; i<=n; i++){
    for(int j=1; j<=i; j*=6)
      chmin(dp[i],dp[i-j]+1);
    for(int j=9; j<=i; j*=9)
      chmin(dp[i],dp[i-j]+1);
  }
  cout << dp[n] << endl;
  return 0;
}

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

using namespace std;

using ll = long long;

int main(){
    ll n, ans = INT_MAX;
    cin >> n;
    for(ll i = 0; i < n; ++i){
        ll tmp; cin >> tmp;
        if(tmp % 2 != 0){
            cout << 0;
            return 0;
        }else{
            ll ct = 0;
            while(tmp % 2 != 1){
                ct++;
                tmp /= 2;
            }
            ans = min(ans, ct);
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define INF 1000000000
int main(){
cin.tie(0);
ios::sync_with_stdio(false);

	int N,x,co=0;
	cin>>N>>x;
	vector<int>a(N);
	
	REP(i,N)cin>>a[i];
	std::sort(a.begin(),a.end());
	REP(i,N){
		if(x<a[i]){
			cout<<co<<endl;
			return 0;
		}
		else{
			co++;
			x-=a[i];
			//cout<<a[i]<<x<<endl;
		}
	}
	//cout<<x<<co<<endl;
	if(x>0)co--;
	cout<<co<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  string s,t;
  cin >> s >> t;
  int n = s.size();
  s += s;
  rep(i,n){
    bool ok = [&]{
      rep(j,n) if(s[i+j]!=t[j]) return false;
      return true;
    }();
    if(ok){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}


Measured memory_bytes: 256
/**
  @file b.cpp
  @title B - Kleene Inversion
  @url https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b
**/

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

typedef long long LL;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, N) for (int i = 0; i < (N); ++i)

int main() {
  LL mod = 1e9 + 7;

  LL N;
  LL K;
  cin >> N >> K;
  vector<LL> A(N, 0);
  REP(i, N) {
    cin >> A[i];
  }

  LL ans = 0;
  for (LL i = 0; i < N; i++) {
    for (LL j = i + 1; j < N; j++) {
      if (A[i] > A[j]) ans++;
    }
  }

  ans = (ans * K) % mod;

  auto reps = [](LL K) {
    if (K > 1) {
      return (K - 1) * K / 2;
    } else {
      return 0LL;
    }
  };

  for (LL i = 0; i < N; i++, ans %= mod) {
    for (LL j = 0; j < N; j++, ans %= mod) {
      if (A[i] > A[j]) {
        ans += reps(K);
      }
    }
  }

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


Measured memory_bytes: 256
N = int(input())
DP = [[0,0,0] for _ in range(N+1)] 
Data = []
Data.append([0,0,0])
for _ in range(N):
    Data.append(list(map(int,input().split())))

DP[1][0] = Data[1][0]
DP[1][1] = Data[1][1]
DP[1][2] = Data[1][2]

for i in range(2,N+1):
    DP[i][0] = max(DP[i-1][1],DP[i-1][2])+Data[i][0]
    DP[i][1] = max(DP[i-1][2],DP[i-1][0])+Data[i][1]
    DP[i][2] = max(DP[i-1][0],DP[i-1][1])+Data[i][2]

ans = max(DP[N][0],DP[N][1],DP[N][2])
print(ans)

Measured memory_bytes: 74192
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
using namespace std;

int main() {
    int N;
    int M;
    int X;

    cin >> N >> M >> X;
    vector <int> c(N);
    vector< vector <int> > power(N, vector<int>(M));

    for (int i = 0; i < N; ++i) {
        cin >> c[i];
        for (int j = 0; j < M; ++j) {
            cin >> power[i][j];
        }
    }

    int allTry = 1<<N;
    const int INF = 1000000000;
    int ans = INF;

    for (int s = 1; s < allTry; ++s) {
        vector <int> level(M);
        int cost = 0;

        for (int i = 0; i < N; ++i) {
            if (s & (1<<i)) {
                cost += c[i];
                for (int j = 0; j < M; ++j) {
                    level[j] += power[i][j];
                }
            }
        }

        bool pass = true;

        for (int i = 0; i < M; ++i) {
            if (level[i] < X) {
                pass = false;
                break;
            }
        }

        if (pass) {
            ans = min(ans, cost);
        }
    }

    cout << (ans == INF ? -1 : ans) << endl;


    return 0;
}

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


using namespace std;
using ll = long long;
using ull = unsigned long long;

float sumOfAP(float a, float d, float n) 
{ 
    float sum = (n / 2) * (2 * a + (n - 1) * d); 
    return sum; 
} 

void solve(){
    int n,m;
    cin>>n>>m;

    int ans1 = sumOfAP(1,1,n-1);
    int ans2 = sumOfAP(1,1,m-1);
    cout<<ans1+ans2<<"\n";
    
}
 
int main(){
     
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt","r",stdin);
    //     freopen("output.txt","w",stdout);
    // #endif
 
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    // int t;
    // cin>>t;
 
    // while(t--)
        solve();
 
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <utility>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int n, ans=0;
bool used[100] = {0};
pair<int, int> x[100],y[100];

int main() {
	cin >> n;
	for(int i = 0; i < n; i++) {
        cin >> x[i].first >> x[i].second;
    }
	for(int i = 0; i < n; i++) { 
        cin >> y[i].first >> y[i].second;
    } 

	sort(x, x+n);
	sort(y, y+n);

	for(int i = n-1; i >= 0; i--) {
		int k = 999;
		int c = -1;
		for(int j = 0; j < n; j++) {
			if(x[i].first < y[j].first && x[i].second < y[j].second && y[j].second < k  && !used[j]) {
				c = j;
				k = y[j].second;
			}
		}
        
		if(c != -1) {
			used[c] = 1;
			ans++;	
		}
	}

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

Measured memory_bytes: 256
{-# LANGUAGE OverloadedLists     #-}
{-# LANGUAGE OverloadedStrings   #-}
{-# LANGUAGE ScopedTypeVariables #-}

import           Control.Monad
import           Data.IORef
import           Data.Maybe
import qualified Data.Text     as T
import qualified Data.Text.IO  as T
import           GHC.Base
import           System.IO

import qualified Data.Array    as A
import qualified Data.IntMap   as I
import qualified Data.Map      as M
import qualified Data.Set      as S
import qualified Data.Vector   as V

main :: IO ()
main = grouping2

grouping2 :: IO ()
grouping2 = do
  n :: Int <- readLn
  print $ n `div `3


Measured memory_bytes: 508
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define for_tests(t, tt) int t; scanf("%d", &t); for(int tt = 1; tt <= t; tt++)
#ifndef ONLINE_JUDGE
#define debug(args...) fprintf(stderr,args)
#else
#define debug(args...)
#endif //ONLINE_JUDGE
template<typename T> inline T abs(T t) { return t < 0? -t : t; }
const ll modn = 1000000007;
inline ll mod(ll x) { return x % modn; }
#define IOS() ios::sync_with_stdio(0),cin.tie(0)

const int MAXN = 212345;

int n, m, k;
int s[MAXN];
int sz[MAXN], p[MAXN];

int raiz(int i){
    if(p[i] == i) return i;
    return p[i] = raiz(p[i]);
}

void join(int i, int j){
    i = raiz(i);
    j = raiz(j);
    if(i == j) return;
    if(sz[i] < sz[j]) swap(i, j);
    p[j] = i;
    sz[i] += sz[j];
}

int main (){
	scanf("%d%d", &n, &m);
    for(int a=0;a<n;a++){
        p[a] = a;
        sz[a] = 1;
    }
    int mx = 1;
	for(int a=0;a<m;a++){
        int i, j;
        scanf("%d%d", &i, &j);
        i--;j--;
        join(i, j);
        mx = max(mx, sz[raiz(i)]);
	}
    printf("%d\n", mx);
}



Measured memory_bytes: 5300
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdio>

#define rep(i, n) for(int i = 0;i < (int)(n); i++)
#define pb push_back
typedef long long ll;

using namespace std;


int main() {
    string s;
    cin >> s;
    if(s.size() == 3){
        char s0 = s[0];
        char s2 = s[2];
        s[2] = s0;
        s[0] = s2;
    }
    cout << s << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define MOD 1000000007
// Use cout.flush() for interactive problems.
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
ll n, k;
ll a[105];
ll dp[105][100005];
ll compute(ll i, ll cur)
{
    if(i==n)
    {
        if(cur==0) return 1;
        else return 0;
    }
    if(dp[i][cur]!=-1) return dp[i][cur];
    ll ans = 0;
    ll j;
    FOR0(j, k+1)
    {
        ans += compute(i+1, j);
        ans %= MOD;
        if(j - a[i] - 1 >=0) 
            ans -= compute(i+1, j-a[i]-1);
        ans += MOD;
        ans %= MOD;   
        dp[i][j] = ans;
    }
    return dp[i][cur];
}
int main()
{
    she_told_me_dont_worry
    cin>>n>>k;
    int i;
    FOR0(i, n) cin>>a[i];
    memset(dp, -1, sizeof dp);
    cout<<compute(0, k);
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 82304
#include <iostream>
#include <string>
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
using namespace std;
typedef long long ll;

int main() {
	string s; cin >> s;
	if (stoi(s.substr(0, 4)) <= 2018 ||
		stoi(s.substr(0, 4)) == 2019 && stoi(s.substr(5, 2)) < 4 ||
		stoi(s.substr(0, 4)) == 2019 && stoi(s.substr(5, 2)) == 4 && stoi(s.substr(8, 2)) <= 30) {
		cout << "Heisei" << endl;
	}
	else {
		cout << "TBD" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>  
#include<cstdio>
#include<stdio.h>
#include<cstring>
#include<cstdio>
#include<climits>   
#include<cmath> 
#include<vector>  
#include <bitset>  
#include<algorithm>    
#include <queue>  
#include<map> 
#define inf 9999999; 
using namespace std;


int k,n,i;

int sum;
int a[55];
int main()
{
	sum=0;
	cin>>n>>k;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(i=n;i>n-k;i--)
	{
		sum+=a[i];
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
  int a,b,c;
  int five,seven;
  five=0;
  seven=0;
  scanf("%d %d %d",&a,&b,&c);
  if(a==5) five++;
  if(a==7) seven++;
  if(b==5) five++;
  if(b==7) seven++;
  if(c==5) five++;
  if(c==7) seven++;
  if(five==2 && seven==1) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }
  return 0;
}
    

Measured memory_bytes: 128
#define _GLIBCXX_DEBUG //test only

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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
int main()
{
  ll n;
  cin >> n;
  ll a,b,c;
  bool fin = false;
  for(a=1;a<=3500;a++)
  {
    for(b=1;b<=3500;b++)
    {
      ll l = a*b*4;
      ll r1 = n*b;
      ll r2 = n*a;
      ll r3 = n*a*b;
      ll ks = l-r1-r2;
      if(ks == 0) continue;
      if(ks < 0)
      {
        ks *= -1;
        r3 *= -1;
      }
      if(r3 <= 0) continue;
      c = r3/ks;
      if(c > 3500) continue;
      if(c*ks == r3)
      {
        printf("%lld %lld %lld", a,b,c);
        fin = true;
      }
      if(fin) break;
    }
    if(fin) break;
  }
}

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

using namespace std;

int main()
{
	int n, m;

	cin >> n >> m;

	vector<vector<int> > s(m);
	vector<int> k(m);
	vector<int> p(m);

	for(int i = 0; i < m; ++i)
	{
		cin >> k[i];

		s[i] = vector<int>(k[i]);

		for(int j = 0; j < k[i]; ++j)
		{
			cin >> s[i][j];
			--s[i][j];
		}
	}

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

	int ans = 0;
	for(int i = 0; i < (1 << n); ++i)
	{
		int onLightCnt = 0;

		for(int j = 0; j < m; ++j)
		{
			int onSwitchCnt = 0;

			for(int l = 0; l < k[j]; ++l)
			{
				if((i >> s[j][l]) & 1)
				{
					++onSwitchCnt;
				}
			}

			if(onSwitchCnt % 2 == p[j])
			{
				++onLightCnt;
			}
		}

		if(onLightCnt == m)
		{
			++ans;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
// #define FNAME "template"

#define NDEBUG

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

typedef long long inte;
const int maxn = 100005;

#ifndef NDEBUG
#    define dprint(x) (cerr << (#x) << " = "<< (x) << endl)
#else
#    define dprint(x) (NULL)
#endif

template<typename T>
inline void readFig(T& x)
{
#   ifdef FTREAD
        static int c = 0;
        int op = 1;
        x = 0;
        while (!isdigit(c)) {
            if (c == '-')
                op = -1;
            c = getchar();
        }
        while (isdigit(c)) {
            x *= 10;
            x += c - '0';
            c = getchar();
        }
        x *= op;
#   else
        cin >> x;
#   endif
}

int N, M;
struct Edge {
    int u, v, w;
} edges[maxn * 2];
inline bool operator < (const Edge &a, const Edge &b)
{
    return a.w < b.w;
}

int par[maxn];
int getPar(int x)
{
    static int st[maxn];
    int stop = 0;
    while (par[x] != x) {
        x = par[x];
        st[stop++] = x;
    }
    while (stop--)
        par[st[stop]] = x;
    return x;
}
inline inte genMST()
{
    for (int i = 1; i <= N; ++i)
        par[i] = i;
    int cnt = 0;
    inte ans = 0;
    for (int i = 1; i <= M; ++i) {
        int u = getPar(edges[i].u), v = getPar(edges[i].v);
        if (u != v) {
            par[u] = v;
            ++cnt;
            ans += edges[i].w;
            dprint(ans);
        }
    }
    //assert(cnt == N - 1);
    return ans;
}

struct City {
    int x, y, id;
} cities[maxn];

inline bool compx(const City &a, const City &b)
{
    return a.x < b.x;
}
inline bool compy(const City &a, const City &b)
{
    return a.y < b.y;
}
inline int getdis(const City &a, const City &b)
{
    return min(abs(a.x - b.x), abs(a.y - b.y));
}

inline void solve()
{
    readFig(N);
    for (int i = 1; i <= N; ++i) {
        readFig(cities[i].x); readFig(cities[i].y);
        cities[i].id = i;
    }
    sort(cities + 1, cities + N + 1, compx);
    for (int i = 1; i < N; ++i) {
        edges[++M].u = cities[i].id;
        edges[M].v = cities[i + 1].id;
        edges[M].w = getdis(cities[i], cities[i + 1]);
    }
    sort(cities + 1, cities + N + 1, compy);
    for (int i = 1; i < N; ++i) {
        edges[++M].u = cities[i].id;
        edges[M].v = cities[i + 1].id;
        edges[M].w = getdis(cities[i], cities[i + 1]);
    }
    sort(edges + 1, edges + M + 1);
    cout << genMST() << endl;
}

signed main()
{
#   ifdef FNAME
        freopen(FNAME".in", "r", stdin);
        freopen(FNAME".out", "w", stdout);
#   endif
#   ifndef FTREAD
    	ios::sync_with_stdio(false);
    	cin.tie(0);
#   endif

#   ifdef MULTEST
        int T;
        readFig(T);
        while (T--)
            solve();
#   else
        solve();
#   endif

#   ifdef FNAME
        fclose(stdin);
        fclose(stdout);
#   endif
    	return 0;
}



Measured memory_bytes: 7584
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
 
    int n;
    cin>>n;
    int a[4],t[4];
    for(int i=0;i<4;i++) cin>>a[i];
    for(int i=0;i<4;i++) cin>>t[i];
    int ans = 1e9;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                for(int h=0;h<=n;h++){
                    int x = i*a[0] + j*a[1] + k*a[2] + h*a[3];
                    int m = i*t[0] + j*t[1] + k*t[2] + h*t[3];
                    if(m>=n) ans = min(ans,x);
                }
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3184
#include <iostream>

using namespace std;
long long dp[110][5][2];
int main(){
	int i,j,l,k;
	string s;
	cin >> s >> k;
	for(j=1;j<=s[0] - '0';j++){
		if(j<s[0] - '0') dp[0][1][0] += 1;
		else dp[0][1][1] += 1;
	}
	for(i=1;i<s.size();i++){
		for(j=1;j<=9;j++){
			dp[i][1][0] += 1;
		}
		for(j=0;j<=9;j++){
			for(l=0;l<=3;l++){
				if(j==0){
					dp[i][l][0] += dp[i - 1][l][0];
					if(s[i]=='0') dp[i][l][1] += dp[i - 1][l][1];
					else dp[i][l][0] += dp[i - 1][l][1];
				}else{
					dp[i][l + 1][0] += dp[i - 1][l][0];
					if(j<s[i] - '0') dp[i][l + 1][0] += dp[i - 1][l][1];
					if(j==s[i] - '0') dp[i][l + 1][1] += dp[i - 1][l][1];
				}
			}
		}
	}
	cout << dp[s.size() - 1][k][1] +  dp[s.size() - 1][k][0] << endl;
}

Measured memory_bytes: 256
while(1):
    s = input()
    if s=='.': break
    s = list(s.split('"'))
    t = list(input().split('"'))
    if len(s) != len(t):
        print("DIFFERENT")
    else:
        cnt=0
        ss=len(s)
        for i in range(ss):
            if i%2==0 and s[i]!=t[i]:
                cnt=100
            elif i%2==1 and s[i]!=t[i]:
                cnt+=1
        if cnt==1:
            print("CLOSE")
        elif cnt==0:
            print("IDENTICAL")
        else:
            print("DIFFERENT")



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

#define N 100
#define INFTY (1 << 21)

int n, M[N][N];
int d[N];

void bfs(int s) {
  queue<int> q;
  q.push(s);
  for ( int i = 0; i < n; i++ ) {
    d[i] = INFTY;
  }
  d[s] = 0;
  int u;
  while ( !q.empty() ) {
    u = q.front(); q.pop();
    for ( int v = 0; v < n; v++ ) {
      if ( M[u][v] == 0 ) continue;
      if ( d[v] != INFTY ) continue;
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
  for ( int i = 0; i < n; i++ ) {
    cout << i + 1 << " " << ( (d[i] == INFTY) ? (-1) : d[i] ) << endl;
  }
}

int main() {
  cin >> n;

  for ( int i = 0; i < n; i++ ) {
    for ( int j = 0; j < n; j++ ) {
      M[i][j] = 0;
    }
  }

  for ( int i = 0; i < n; i++ ) {
    int a, b;
    cin >> a >> b;
    --a;
    for ( int j = 0; j < b; j++ ) {
      int c;
      cin >> c;
      M[a][--c] = 1;
    }
  }

  bfs(0);

  return 0;
}

Measured memory_bytes: 3112
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

const int N = 3e3+5;
const int mod = 1e9+7;

int n;
double p[N];
bool vis[N][N];
double mem[N][N];

double go(int idx , int hea){
    if(idx == n + 1){
        int tail = n - hea;
        if(hea > tail)
            return 1.0;
        return 0.0;
    }
    if(vis[idx][hea])
        return mem[idx][hea];
    double a = go(idx + 1 , hea) * (1.0 - p[idx]);
    a += go(idx + 1 , hea + 1) * p[idx];
    vis[idx][hea] = 1;
    return mem[idx][hea] = a;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
    }
    cout << fixed << setprecision(9) << go(1 , 0) << endl;
}


Measured memory_bytes: 78208
/**
DufauX-XuafuD
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define reset(x) memset(x,-1,sizeof(x))
#define CheckBit(a,b) (a&(1ll<<b))
#define SetBit(a,b) a=(a|(1ll<<b))
#define UnSetBit(a,b) a=(a&(~(1ll<<b)))
#define maxx 10000006
#define PI 2*acos(0.0)
const long long INF = 2000000000000000000LL;	// 2e18
const int inf = 0x3f3f3f3f;	// 1061109567
const long double EPS = 1e-9;
//bitset<maxx/2>vis;
//bitset<maxx>pr;
//int mobi[maxx+10];
//vector<ll>prime;
//void sieve(){
//    ll x=maxx/2, y=sqrt(maxx)/2;
//    for(ll i=1;i<=y;i++){
//        if(vis[i]==0){
//            for(ll j=(i*(i+1)*2);j<x;j+=(2*i)+1)
//                vis[j]=1;
//        }
//    }
//    prime.push_back(2);
//    for(ll i=3;i<maxx;i+=2)
//        if(vis[i/2]==0)
//        prime.push_back(i);
//}
//void generate_mobius()
//{
//    for(int i=0;i<maxx;i++)mobi[i]=1;
//    for(int i=2;i<maxx;i++){
//        if(!pr[i]){
//            mobi[i]*=-1;
//            for(int j=i+i;j<maxx;j+=i){
//                pr[j]=1;
//                mobi[j]*=(j%(i*i)?-1:0);
//            }
//        }
//    }
//}
//bool isprime(ll a)
//{
//    if(a==1)return false;
//    if(a==2)return true;
//    if(a%2==0)return false;
//    for(ll i=0;i<prime.size() && prime[i]*prime[i]<=a;i++)
//        if(a%prime[i]==0)return false;
//    return true;
//}
/* Calculate ( a*b ) %c */
inline ll mulmod(ll a, ll b, ll c) {
    ll ret = 0 , cur = a % c ;
    while(b) { if(b%2) ret=(ret+cur)%c; cur=(cur<<1)%c; b=b>>1; }
    return ret%c;
}
//Calculate (b^p)%m || modular inverse: b^-1 = bigmod(b, m-2, m)
inline ll bigmod(ll b, ll p, ll m){
    ll ret = 1, cur = b % m;
    while(p) { if(p&1) ret=(ret*cur)%m; cur=(cur*cur)%m; p=p>>1; }
    return ret;
}
inline ll modulo(ll a,ll b,ll c) { //Same as big mod, use for numbers over 1e10
    ll ret = 1 , cur = a%c ;
    while(b) { if(b%2) ret=mulmod(ret,cur,c); cur=mulmod(cur,cur,c); b=b>>1; }
    return ret%c ;
}
inline ll power(ll b, ll p){
    ll ret = 1, cur = b;
    while(p) { if(p&1) ret=(ret*cur); cur=(cur*cur); p=p>>1; }
    return ret;
}
ll lcm(ll a,ll b)
{
    return (a/__gcd(a,b))*b;
}
ll gcd(ll a,ll b)
{
    return __gcd(a,b);
}
string s[200];
bool cmp(string a,string b)
{
    for(int i=0;i<a.size();i++){
        if(a[i]!=b[i]){
            return a[i]<b[i];
        }
    }
    return a<b;
}
void Dufaux()
{
    ll n,l;
    cin>>n>>l;
    for(int i=0;i<n;i++)cin>>s[i];
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++)cout<<s[i];
    cout<<endl;
}
int main()
{
    FastIO;
	///sieve();
	///generate_mobius();
	int test=1;
	while(test--){
        Dufaux();
	}
	return 0;
}






Measured memory_bytes: 3692
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define min3(a,b,c) min(a,min(b,c))
#define mai3(a,b,c) mai(a,mai(b,c))
#define all(i) i.begin(),i.end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define set_bit __builtin_popcount //gives number of set_bits
#define ff first
#define ss second
#define cases(t) int t; cin>>t; rep(casn,1,t+1)
#define el cout<<endl;
#define deci(n) int n; cin>>n;
#define decs(n) string n; cin>>n;
//SUNEET KUMAR -->  ਸੁਨੀਤ 
int power(int a,int n)//binary expo
{
    int r;
    if(n==0)
        return 1;
    else if(n==1)
        return a;
    else
        r=power(a,n/2);
    if(n%2==0)
        return ((r)%mod)*((r)%mod)%mod;
    else
        return ((((r)%mod)*((r)%mod))%mod*((a)%mod))%mod;
}
int mai(int a,int b)
{
    if(a>b)
    return a;
    else 
    {
        return b;
    }
}
int madd(int a,int b)
{
    int ans;
    ans=(a%mod+b%mod)%mod;
    return ans;
}
int mmult(int a,int b)
{
    int ans=1;
    ans=((a%mod)*(b%mod))%mod;
    return ans;
}

int modinverse(int a)
{
    return power(a,mod-2);
}
signed main()
{
     int flag=0;
     deci(n);
     int x=n/2;
     for(int i=1;i<=n;i++)
     {
         int ans;
         double v=1.08;
         double xx=(double)i;
         double res=xx*v;
        //  if(res-floor(res)<=0.50000)
        //  {
        //      ans=(int)(floor(res));
        //  }
        //  else
        //  {
        //      ans=(int)(ceil(res));   
        //  }
        ans=(floor(res));
         if(ans==n)
         {
             flag=1;
             cout<<i<<endl;
             break;
         }
     }
     if(flag==0)
     {
         cout<<":(";
     }
}

Measured memory_bytes: 256
class Binary_search():
    def __init__(self,S):
        self.num = 0
        self.S = S
    def binary_search(self,left,right,key):
        if left < right:
            mid =int((left + right) / 2)
            if self.S[mid] == key:
                self.num += 1
            elif self.S[mid] < key:
                self.binary_search(mid+1,right,key)
            else:
                self.binary_search(left,mid,key)

def main():
    N = int(input())
    S = [int(c) for c in input().split()]
    M = int(input())
    T = [int(c) for c in input().split()]
    binary_search = Binary_search(S)
    for i in range(M):
        binary_search.binary_search(0,N,T[i])
    print(binary_search.num)

if __name__ == '__main__':
    main()



Measured memory_bytes: 16900
#!python3.4.3

S = input()
N = len(S)


def hantei(s, n):
  flag = False
  if n % 2 == 1:
    flag = s[:n//2] == s[:n//2:-1]
  else:
    flag = s[:n//2] == s[:(n//2)-1:-1]
  if flag:
    return True
  else:
    return False

S1 = S[0:(N-1)//2]
S2 = S[((N+3)//2)-1:]

if hantei(S, N) and hantei(S1, len(S1)) and hantei(S2, len(S2)):
  print('Yes')
else:
  print('No')
    

Measured memory_bytes: 3064
N,M,C = list(map(int, input().split()))
B = list(map(int, input().split()))
A = []

for i in range(N):
	A.append(list(map(int, input().split())))

ans = 0

for i in range(N):
	tmp = 0
	for j in range(M):
		tmp = tmp + A[i][j]*B[j]
	if(tmp+C>0):
		ans += 1

print(ans)


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

#define N 200005

using namespace std;

int n,a[N],b[N],c[N];

template<typename Drake>
void read(Drake &x){
	x=0;char ch=getchar();bool f=1;
	while(!isdigit(ch)){
		if(ch=='-')f^=1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=(2*f-1);
}

template<typename Drake>
void write(Drake x){
	if(x<0){x=-x;putchar('-');}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

template<typename Drake>
void writeln(Drake x){
	write(x);
	puts("");
}

void init(){
	read(n);
	for(register int i=1;i<=n;i++)
	read(a[i]),b[i]=a[i];
}

int main(){
	init();
	sort(b+1,b+n+1);
	for(register int i=1;i<=n;i++){
		if(a[i]>b[n/2])
		c[i]=b[n/2];
		else c[i]=b[n/2+1];
	}
	for(register int i=1;i<=n;i++){
		writeln(c[i]);
	}
	puts("");
	return 0;
}

Measured memory_bytes: 4480
// Partition.cs

using System;

class Partition {
	public static void Main() {

		int n = int.Parse(Console.ReadLine());

		string[] str = Console.ReadLine().Split(' ');

		int[] a = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = int.Parse(str[i]);
		}

		int r = a[a.Length - 1], p = 0, q = 0, swap;

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

			if(r >= a[i]) {
				swap = a[p];
				a[p] = a[i];
				a[q] = swap;
				p++;
				q++;
			} else if(i == n - 1) {
				swap = a[p];
				a[p] = a[i];
				a[n - 1] = swap;
			} else {
				a[q] = a[i];
				q++;
			} 

		}
		
		for(int i = 0; i < n; i++) {
			if(a[i] == r && p - 1 == i) {
				Console.Write("[" + a[i] + "] ");
			} else if(i != n - 1) {
				Console.Write(a[i] + " ");
			} else {
				Console.WriteLine(a[i]);
			}
		}

	}
}

Measured memory_bytes: 17148
#include <iostream>
#include <queue>
using namespace std;
int main(){
	int n,k;
	int r,s,p;
	string t;
	cin>>n>>k;
	cin>>r>>s>>p;
	cin>>t;
	int ans=0;
	int dp[100000][3]={};
	for(int i=0;i<k;i++){
		int now=i;
		if(t[now]=='r'){
			dp[now][2]=p;
		}else if(t[now]=='s'){
			dp[now][0]=r;
		}else{
			dp[now][1]=s;
		}
		now+=k;
		while(now<n){
			if(t[now]=='r'){
				dp[now][0]=max(dp[now-k][1],dp[now-k][2]);
				dp[now][1]=max(dp[now-k][0],dp[now-k][2]);
				dp[now][2]=max(dp[now-k][0]+p,dp[now-k][1]+p);
			}else if(t[now]=='s'){
				dp[now][0]=max(dp[now-k][1]+r,dp[now-k][2]+r);
				dp[now][1]=max(dp[now-k][0],dp[now-k][2]);
				dp[now][2]=max(dp[now-k][0],dp[now-k][1]);
			}else{
				dp[now][0]=max(dp[now-k][1],dp[now-k][2]);
				dp[now][1]=max(dp[now-k][0]+s,dp[now-k][2]+s);
				dp[now][2]=max(dp[now-k][0],dp[now-k][1]);
			}
			now+=k;
		}
		ans+=max(dp[now-k][0],max(dp[now-k][1],dp[now-k][2]));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1664
#include <stdio.h>
int main(void){
    
   int x,y;
   
   while(1){
       scanf("%d %d",&x,&y);
       if(x==0 && y==0) break;
       else{
           if(x<y) printf("%d %d\n",x,y);
           else printf("%d %d\n",y,x);
       }
   }
 
    return 0;
    
}


Measured memory_bytes: 2128
//#include </Users/kmudda/Downloads/Karthik/stdc++.h>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#define ll long long int
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define vvl vector< vl >
#define vvi vector< vi >
#define pb push_back
#define mp make_pair
#define max_int_value 2147483647
#define max_long_value 9223372036854775807
#define min_long_value -9223372036854775806
#define ii pair<ll,ll>
#define F first
#define S second
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0)
 
#define CLR(v, d)     memset(v, d, sizeof(v))
 
template<typename T> T gcd(T a, T b){return (b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return (a*(b/gcd(a,b)));}
template<typename T> T mod(T a, T b) {return (a<b ? a : a%b);}
template<typename T> T mod_neg(T a, T b) {return ((a%b)+b)%b;}
ll mulmod(ll a,ll b, ll m){ll q=(ll)(((ld)a*(ld)b)/(ld)m);ll r=a*b-q*m;if(r>m)r%=m;if(r<0)r+=m;return r;}
template<typename T> T expo(T e, T n){T x=1,p=e;while(n){if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
template<typename T> T power(T e, T n, T m){T x=1,p=e;while(n){if(n&1)x=mod(x*p,m);p=mod(p*p,m);n>>=1;}return x;}
template<typename T> T extended_euclid(T a, T b, T &x, T &y){T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
template<typename T> T mod_inverse(T a, T n){T x,y;T d = extended_euclid(a, n, x, y);return (d>1?-1:mod_neg(x,n));}
 
using namespace std;
 
string IntToString (int a)
{
    ostringstream temp;
    temp<<a;
    return temp.str();
}
 
int StringToInt (string str)
{
    int xx;
    stringstream ss;
    ss << str;
    ss >> xx;
    return xx;
}
 
ll powerwithmodulus(ll base, ll exponent,ll modulus){
    ll result = 1; base%=modulus;
    while (exponent > 0)
    {
        if (exponent % 2 == 1) result = (result * base) % modulus;
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

/*  NCR using DP
for(int n = 0; n <= 1000; n++)
        for(int r = 0; r <= n; r++)
            if(r == 0 || n == r) ncr[n][r] = 1;
            else ncr[n][r] = (ncr[n-1][r-1] + ncr[n-1][r]) % mod;

*/

 
ll largestPowerOf2(ll n)
{
    return (ll)pow(2, floor(log(n) / log(2)));
}

inline bool cmp1(pair<ll,ll> &p1, pair<ll,ll> &p2) {
    if(p1.F == p2.F)
        return p1.S < p2.S;
    else
        return p1.F < p2.F;
}
 
//lower case std::transform(str.begin(), str.end(), str.begin(), ::tolower);
//Ascii A-65 Z-90 a-97 z-122 0-48 9-57

int cal(int pow, int val, int MOD){
   if(pow <= 0)
      return 1;
   int v = cal(pow/2, val, MOD);
   if(pow % 2 == 0)
      return (v*v) % MOD; 
   else
      return (((v*val) % MOD) * v) % MOD;
}

ll t,n,m,sum=0,coun=0,m1,m2,m3,i,j,k,sum1,sum2,p,q,r,p1,q1;
bool flag2;

int main() {

  fast_io;
  //freopen("inputf.in", "r", stdin);
  //freopen("outputf.in", "w", stdout);
  string str;
  int cccc = 0;
  cin>>str;
  for(i=1;i<4;i++) {
    if(str[i] == str[i-1])
      cccc++;
  }

  if(cccc == 0)
    cout<<"Good"<<endl;
  else
    cout<<"Bad"<<endl;
}


Measured memory_bytes: 256
//writer：Sakura
//problem：
//id：
//from：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
//#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int p[1005][1005];

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int x;
	int ans=0;
	scanf("%d",&x);
	/*for(int i=1;i<=1000;i++)p[i]=i*i;
	for(int i=1;i<=1000;i++){
		if(p[i]<=x){
			ans=max(p[i],ans);
			printf("%d\n",ans);
		}
		else break;
	}*/
	
	for(int i=1;i<=1000;i++){
		p[i][0]=p[i][1]=i;
	}
	
	for(int i=1;i<=1000;i++){
		for(int j=2;j<=10;j++){
			p[i][j]=p[i][j-1]*i;
			//printf("p[%d][%d]=%d\n",i,j,p[i][j]);
		}
	}
	
	for(int i=1;i<=1000;i++){
		for(int j=2;j<=10;j++){
			if(p[i][j]<=x){
				ans=max(ans,p[i][j]);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}



Measured memory_bytes: 4224
n, m, x = map(int, input().split())
grid = [0]*(n+1)
a = list(map(int, input().split()))

for i in a:
    grid[i-1] = 1

if sum(grid[0:x]) >= sum(grid[x:n]):
    print(sum(grid[x:n]))
else:
    print(sum(grid[0:x]))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
#define y1 itstakioi
const int N=2e5+10;

int gi() {
	int x=0,o=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int h,w,n,sr,sc;
char s[N],t[N];

void No() {
	cout<<"NO";exit(0);
}

int main() {
	cin>>h>>w>>n>>sr>>sc;
	scanf("%s%s",s+1,t+1);
	int now=sr;
	for(int i=1;i<=n;i++) {
		if(s[i]=='U') { --now;if(now<1) No(); }
		if(t[i]=='D') { if(now<h) ++now; }
	}
	now=sr;
	for(int i=1;i<=n;i++) {
		if(s[i]=='D') { ++now;if(now>h) No(); }
		if(t[i]=='U') { if(now>1) --now; }
	}
	now=sc;
	for(int i=1;i<=n;i++) {
		if(s[i]=='L') { --now;if(now<1) No(); }
		if(t[i]=='R') { if(now<w) ++now; }
	}
	now=sc;
	for(int i=1;i<=n;i++) {
		if(s[i]=='R') { ++now;if(now>w) No(); }
		if(t[i]=='L') { if(now>1) --now; }
	}
	cout<<"YES";
	return 0;
}


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

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int H = scan.nextInt();
        int W = scan.nextInt();
        char[][] map = new char[H][W];
        for (int i = 0; i < H; i++) {
            String line = scan.next();
            char[] data = line.toCharArray();
            for (int j = 0; j < W; j++) {
                map[i][j] = data[j];
            }
        }
        int[][] horizonL = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (map[i][j] == '#') {
                    horizonL[i][j] = j+1;
                    continue;
                }
                if (0 < j) {
                    horizonL[i][j] = horizonL[i][j-1];
                }
            }
        }
        int[][] horizonR = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = W - 1; 0 <= j; j--) {
                if (map[i][j] == '#') {
                    horizonR[i][j] = j+1;
                    continue;
                }
                if (j < W - 1) {
                    horizonR[i][j] = horizonR[i][j+1];
                } else {
                    horizonR[i][j] = W+1;
                }
            }
        }
        int[][] verticalT = new int[H][W];
        for (int j = 0; j < W; j++) {
            for (int i = 0; i < H; i++) {
                if (map[i][j] == '#') {
                    verticalT[i][j] = i+1;
                    continue;
                }
                if (0 < i) {
                    verticalT[i][j] = verticalT[i-1][j];
                }
            }
        }
        int[][] verticalB = new int[H][W];
        for (int j = 0; j < W; j++) {
            for (int i = H-1; 0 <= i; i--) {
                if (map[i][j] == '#') {
                    verticalB[i][j] = i+1;
                    continue;
                }
                if (i < H - 1) {
                    verticalB[i][j] = verticalB[i+1][j];
                } else {
                    verticalB[i][j] = H+1;
                }
            }
        }
        int answer = 0;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (map[i][j] == '#') {
                    continue;
                }
                int count = horizonR[i][j]-horizonL[i][j]-1;
                count += verticalB[i][j]-verticalT[i][j]-1;
                count -= 1;
                answer = Math.max(answer, count);
            }
        }
        System.out.println(answer);
    }
}


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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)

int dfs(int pos, vector<vector<int>>& G, vector<int>& memo)
{
    if(memo[pos] > 0) return memo[pos];

    int ret = 0;
    for(auto v: G[pos]) ret = max(ret, dfs(v, G, memo)+1);
    return memo[pos] = ret;
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    REP(i, M){
        int x, y;
        cin >> x >> y;
        --x, --y;
        G[x].push_back(y);
    }

    int ans = 0;
    vector<int> memo(N, 0);
    REP(i, N) ans = max(ans, dfs(i, G, memo));
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 8832
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main {
	
	public static final int N_MAX = 20 + 1;
	public static final int K_MAX = 10 + 1;
	public static final int S_MAX = 155 + 1;
	
	public static int memo(final int n, final int k, final int s, int[][][] memo){
		//System.out.println(n + " " + k + " " + s);
		if(memo[n][k][s] >= 0){
			return memo[n][k][s];
		}else if(k == 0 && s == 0){
			return memo[n][k][s] = 1;
		}else if(k == 0){
			return memo[n][k][s] = 0;
		}
		
		int ret = 0;
		for(int next_use_value = 1; next_use_value <= n; next_use_value++){
			if(s < next_use_value){
				break;
			}
			
			ret += memo(next_use_value - 1, k - 1, s - next_use_value, memo);
		}
		
		return memo[n][k][s] = ret;
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int[][][] memo = new int[N_MAX][K_MAX][S_MAX];
		
		for(int n = 0; n < N_MAX; n++){
			for(int k = 0; k < K_MAX; k++){
				for(int s = 0; s < S_MAX; s++){
					memo[n][k][s] = -1;
				}
			}
		}
		
		while(true){
			final int n = sc.nextInt();
			final int k = sc.nextInt();
			final int s = sc.nextInt();
			
			if(n == 0 && k == 0 && s == 0){
				break;
			}
			
			System.out.println(memo(n, k, s, memo));
		}
		
	}
	
}

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

using namespace std;

using ll = long long;

int main() {
  ll n, m;
  cin >> n >> m;
  vector<ll> v;
  for (ll i = 1; i * i <= m; ++i) {
    if (m % i == 0) {
      v.push_back(i);
      v.push_back(m / i);
    }
  }
  sort(v.begin(), v.end());
  ll ans = 1;
  for (auto x : v) {
    if (x * n <= m) {
      ans = x;
    } else
      break;
  }
  cout << ans << endl;
}

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

int main() {
  int x, y, z;
  cin >> x >> y >> z;
  cout << z << " " << x << " " << y << endl;
  return 0;
}


Measured memory_bytes: 3644