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

using namespace std;

#define int 		long long
#define endl		"\n"
#define mod			1000000007
#define IOS			ios::sync_with_stdio(0), cin.tie(0)

int32_t main() {

	IOS;

	char c;
	cin>>c;
	if(c >='A' && c <='Z')
		cout <<"A\n";
	else
		cout <<"a\n";


	return 0;
}


Measured memory_bytes: 3636
n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
dp = {}
ans = 0
for i in range(n):
    for k in range(i+1,n):
        dp[(i,k)] = (((a[i][0]-a[k][0])**2 + (a[i][1]-a[k][1])**2)**0.5)
        ans += dp[(i,k)]
print(ans*2/n)

Measured memory_bytes: 38256
import sys

a, b, x = map(int, input().split())
c = b // x
d = (a-1) // x

if a == 0 and b == 0:
    print(1)
    sys.exit()

elif a == 0 or b == 0:
    print(c + 1)
    sys.exit()

print(c - d)


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

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

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<int> L(n);
	rep(i,n) cin >> L[i];
	sort(L.begin(), L.end());
	int ans = 0;
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			for(int k = j+1; k < n; k++){
				if(L[i] == L[j] || L[j] == L[k]) continue;
				if(L[i] + L[j] > L[k]) ans++;
			}
		}
	}
	cout << ans << endl;
} 

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)  
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};



int main(){

  int n,k;
  cin>>n>>k;
  int h[n];
  REP(i,n){
    cin>>h[i];
  }
  int minScore[n];
  minScore[0] = 0;

  for(int i=1;i<n;i++){
    minScore[i] = INF;
    for(int j=1;j<=k;j++){
      if(i-j>=0){
        minScore[i] = min(minScore[i],minScore[i-j] + abs(h[i] - h[i-j]));
      }
    }
  }

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



  return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define IOS ios::sync_with_stdio(false); cin.tie(NULL);
#ifdef LOCAL
#define dbg(...) {cerr << "> "; ZZ(#__VA_ARGS__,__VA_ARGS__);}
template <typename Arg1> void ZZ(const char* val1, Arg1&& arg1) { cerr << val1 << ": " << arg1 << endl; }
template <typename Arg1, typename... Args> void ZZ(const char* vals, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(vals + 1, ',');
    std::cerr.write(vals, comma - vals) << ": " << arg1<<" , ";
    ZZ(comma+1, args...);
}
#else
#define dbg(...) ;
#define endl '\n'
#endif

const int inf = 1e15;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;

char c[21][21];
vector<pii> v, g[21][21];
int vis[21][21], dis[21][21];

signed main(){
    IOS;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
        }
    }
    int a, b;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (c[i][j] != '.') continue;
            v.push_back({i, j});
            if (c[i+1][j] == '.') g[i][j].pb({i+1, j});
            if (c[i-1][j] == '.') g[i][j].pb({i-1, j});
            if (c[i][j+1] == '.') g[i][j].pb({i, j+1});
            if (c[i][j-1] == '.') g[i][j].pb({i, j-1});
        }
    }
    int mx = 0;
    for (int i = 0; i < v.size(); i++){
            memset(vis, 0, sizeof(vis));
            memset(dis, 0, sizeof(dis));
            queue<pii> q;
            q.push({v[i].fi, v[i].se});
            vis[v[i].fi][v[i].se] = 1;
            while (!q.empty()) {
                pii t = q.front();
                q.pop();
                for (auto it : g[t.fi][t.se]) {
                    if (vis[it.fi][it.se]) continue;
                    vis[it.fi][it.se] = 1;
                    q.push({it.fi, it.se});
                    dis[it.fi][it.se] = dis[t.fi][t.se] + 1;
                    mx = max(mx, dis[it.fi][it.se]);
                }                
            }
    }
    cout << mx << endl;
    return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    const int MAX_N = 500, MAX_C = 30;
    int N, C, D[MAX_C][MAX_C];
    int cc[3][MAX_C];
    memset(cc[0], 0, sizeof(cc));
    cin >> N >> C;
    REP(i, C) {
        REP(j, C) {
            cin >> D[i][j];
        }
    }
    REP(i, N) {
        REP(j, N) {
            int c;
            cin >> c;
            cc[(i + j) % 3][c - 1]++;
        }
    }
    int res = INT_MAX;
    REP(c1, C) {
        REP(c2, C) {
            if (c1 == c2) {
                continue;
            }
            REP(c3, C) {
                if (c1 == c3 || c2 == c3) {
                    continue;
                }
                int sum = 0;
                REP(c, C) {
                    sum += D[c][c1] * cc[0][c];
                    sum += D[c][c2] * cc[1][c];
                    sum += D[c][c3] * cc[2][c];
                }
                amin(res, sum);
            }
        }
    }
    cout << res << endl;
    return 0;
}


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

using namespace std;

int main(){
  vector<int> v(3); cin >> v[0]>>v[1]>>v[2];
  sort(v.begin(),v.end());
  cout << v[0]+v[1]+v[2]*10<<endl;
  return 0;
}

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

const int N = 100;
char g[N][N];
int row[N] , col[N];
int main(){
  int h , w, k;
  cin >> h >> w >> k;
  int tot = 0;
  for(int i = 1;i <= h ; ++i){
    for(int j = 1;j <=w ; ++j){
      cin >> g[i][j];
      if(g[i][j] == '#'){
        ++tot;
        row[i]++;
        col[j]++;
      }
    }
  }
  //cout << tot << endl;
  int ans = 0;
  for(int mask = 0; mask < (1<<h) ; ++mask){
    for(int mask1 = 0; mask1 < (1<<w) ; ++mask1){
      int red = 0;
      for(int i = 0;i < h ; ++i){
        if(mask&(1<<i)) red += row[i+1];
        else continue;
        for(int j = 0;j < w ; ++j){
          if(mask1&(1<<j) && g[i+1][j+1] == '#')--red;
        }
      }
      for(int i = 0;i < w; ++i)
        if(mask1&(1<<i)) red += col[i+1];
      if(tot - red == k) ++ans;
    }
  }
  /*
   *for(int i=  1;i <= h ; ++i){
   *  for(int j = 1;j <= w ; ++j){
   *    int red = row[i] + col[j];
   *    if(g[i][j] == '#') --red;
   *    cout << i << ' ' << j << ' ' << red << endl;
   *    if(tot-red == k)
   *      ++ans;
   *  }
   *}
   */
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long double PI = acos(-1.0);
// cout << fixed << setprecision(14);
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int A, B;
	cin >> A >> B;
	cout << A*B << endl;
}

Measured memory_bytes: 3636
#include<iostream>
#include<iomanip>
#include<string>
#include<array>
#include<cmath>
#include<vector>
#include<utility>
#include<algorithm>
#include<ctype.h>
using namespace std;


int main() {
	char c,x;
	cin >> c;
	x = c + 1;
	cout << x << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n;
    cin >> n;

    vl a(n);
    rep(i, n) {
        cin >> a[i];
    }

    ll ans = 0;
    rep(i, n-1) {
        if(a[i] == a[i+1]) {
            ans++;
            i++;
        }
    }
    
    out(ans);
    re0;
}

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

int main() {
   int n,m,c;
   cin >> n >> m >> c;
   int b[101];
   rep(i,m)
   cin >> b[i];

   int a,ans=0;
   rep(i,n){
      int sum=c;
      rep(j,m){
         cin >> a;
         sum+=a*b[j];
      }
      if(sum>0)
      ans++;
   }
   cout << ans << endl;
}

Measured memory_bytes: 256
a = gets.to_i
b = gets.to_i
c = gets.to_i
x = gets.to_i
 

count = 0
(a + 1).times do |i|
  d = x - (500 * i)
  if d < 0
    break
  end
  
  (b + 1).times do |j|
    e = d - (100 * j)
    if e < 0
      break
    end
    
    if (e / 50) <= c 
      count += 1
    end
  end
end
 
puts count

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
long long int mod = 1000000007;
typedef long long int lli;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<lli> vlli;
typedef vector<bool> vb;
long long int max(long long int a,long long int b){
  if(a>b)
    return a;
  else
    return b;
}
long long int min(long long int a,long long int b){
  if(a<b)
    return a;
  else
    return b;
}
long long int binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1)
      res = res * a % m;
      a = a * a % m;
      b >>= 1;
    }
  return res;
}
long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}
 
//############################ENDOFTEMPLATE############################
vector<vi> adj(100005);
vector<int> dp(100005,-1);
int dfs(int x){
  if(dp[x]!=-1){
    return dp[x];
  }

  dp[x] = 0;
  for(auto v:adj[x]){
    dp[x] = max(dp[x],dfs(v)+1);
  }

  return dp[x];
}

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

  for(int i = 0;i<m;i++){
    int x,y;
    cin>>x>>y;
    adj[x].push_back(y);
  }
  for(int i = 1;i<=n;i++){
    adj[0].push_back(i);
  }

  cout<<dfs(0)-1;


}
 
 
 
 
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  //freopen("moobuzz.in","r",stdin);
  //freopen("moobuzz.out","w",stdout);
  int t=1;
  //cin>>t;
  while(t--){
    solve();
  }
}

Measured memory_bytes: 11644
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; i++)
#define rep_r(i, n) for (ll i = n - 1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define resize(x, n) x.resize(n)
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
const ll INF = 1000000000000000000;
const ll mod = 1000000007;
const ll MAX = 100000;
struct edge {
    ll from, to, weight;
    edge(ll f, ll t, ll w) : from(f), to(t), weight(w) { }
};
vector<vector<edge>> edges;
vector<vector<ll>> graph;
vector<bool> visited;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
ll n, sum;
vl a;

ll cost(ll i) {
    return sum - abs(a[i-1]-a[i]) - abs(a[i]-a[i+1]) + abs(a[i-1]-a[i+1]);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    resize(a, n+2);
    rep(i, n+2) {
        if (i == 0 || i == n+1) a[i] = 0;
        else cin >> a[i];
        if (i > 0) sum += abs(a[i-1]-a[i]);
    }
    rep(i, n+1) {
        if (i == 0) continue;
        printf("%ld\n", cost(i));
    }
}

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

#define ll long long

using namespace std;

vector <ll> v[300];

ll in[300];

int main()
{
    string s;
    string t;
    cin >> s >> t;
    for(ll i = 0; i < s.length(); i++)
    {
        v[s[i]].push_back(i);
        in[s[i]]++;
    }
    for(ll i = 0; i < t.length(); i++) if(!in[t[i]]) return cout << -1, 0;
    ll cur = 0;
    ll res = 0;
    for(ll i = 0; i < t.length(); i++)
    {
        if(lower_bound(v[t[i]].begin(), v[t[i]].end(), cur) == v[t[i]].end()) res += s.length(), cur = 0;
        auto it = lower_bound(v[t[i]].begin(), v[t[i]].end(), cur);
        cur = *it + 1;
        //cout << cur << endl;
    }
    res += cur;
    cout << res;
}


Measured memory_bytes: 1724
program sample
    implicit none
    character(100)::s,t
    integer(8) :: i,j,k,m,n,ans
    integer(8)::a,b,c,d
    integer(8),allocatable::x(:),y(:)
  
    read(*,*)k
    do i=1,k/2+1
        m=m+i
        if(m>=k)then
            
            ans=i
            
            write(*,*)ans
            stop
        end if
    end do       
    
    stop
end program sample
  



Measured memory_bytes: 2852
package main

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

func solution(s string) string {
        var memo [26]int

        for _, r := range s {
                memo[r-'a']++
        }
        for i := range memo {
                if memo[i] == 0 {
                        return string(i + 'a')
                }
        }
        return "None"
}

func main() {
        reader := bufio.NewReaderSize(os.Stdin, 10240*10240)
        str, _, _ := reader.ReadLine()
        fmt.Println(solution(strings.TrimRight(string(str), "\r\n")))
}

Measured memory_bytes: 4096
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
#include<map>
#include<set>
using namespace std;
#define INF 11000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> P;

int num[110000];

int main(){
  int N,temp,count1=0,count2=0,nokori=0;
  cin>>N;

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

  for(int i=0;i<110000;i++){
    if(num[i]==1) count1++;
    else if(num[i]>=2){
      count2++;
      nokori+=num[i]-1;
    } 
  }
  if(nokori%2==0) cout<<count1+count2<<endl;
  else cout<<count1+count2-1<<endl;
}


Measured memory_bytes: 888
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>

#define LL  long long
using namespace std;
int K;

int gcd1(int m, int n) {
    return n==0?m:gcd1(m%n, n);
}

int gcd2(int m, int n) {
    int t;
    while(n>0) {
        t = m%n;
        m = n;
        n = t;
    }
    return m;
}
int main()
{
    scanf("%d", &K);
    LL sum = 0;
    for(int a = 1; a<=K; a++) {
        for(int b=1; b<=K; b++) {
            int t = gcd2(a, b);
            for(int c=1; c<=K; c++) {
                int tt = gcd2(t, c);
                sum += tt;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3656
import sys
import collections
import bisect


def main():
    n = int(input())
    A = [int(input()) for _ in range(n)]
    c = collections.Counter(A)
    sumA = 0
    cKeys = c.keys()
    for cKey in cKeys:
        sumA += c[cKey] % 2
    print(sumA)


if __name__ == '__main__':
    main()


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

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

int main()
{
    ll i,j;
    ll h,w,d;
    cin >> h >> w >> d;
    vector<vector<ll>> a(h,vector<ll>(w));
    vector<pair<ll,ll>> mapa(h*w+1); 
    for(i = 0;i < h;++i){
        rep(j,w){
            cin >> a.at(i).at(j);
            mapa.at(a.at(i).at(j)) = make_pair(i,j); 
        }
    }
    vector<ll> ruiseki(h*w+1,0);
    for(i = 1;i <= d;++i){
        for(j = i+d;j <= h*w;j += d){
            ll tmp = abs(mapa.at(j).first - mapa.at(j-d).first) + abs(mapa.at(j).second - mapa.at(j-d).second);
            ruiseki.at(j) = ruiseki.at(j-d) + tmp; 
        }
    }
    ll q;
    cin >> q;
    for(i = 0;i < q;++i){
        ll l,r;
        cin >> l >> r;
        cout << ruiseki.at(r) - ruiseki.at(l) << endl;
    }

    return 0;
}

Measured memory_bytes: 3968
import java.awt.print.Printable;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		String[] str1=new String[n];
		for(int i=0;i<n;i++){
			str1[i]=scanner.next();
		}
		String[] str2=Arrays.copyOf(str1, str1.length);
		
		bubbleSort(str1,n);
		selectionSort(str2,n);
		
		
		print(str1,n);
		System.out.println("Stable");
		print(str2,n);
		if(isStable(str1, str2, n)){
			System.out.println("Stable");
		}
		else{
			System.out.println("Not stable");
		}
	}



	private static boolean isStable(String[] str1, String[] str2, int n) {
		// TODO Auto-generated method stub
		for(int i=0;i<n;i++){
			if(str1[i].charAt(0)!=str2[i].charAt(0))
				return false;
		}
		
		return true;
	}



	private static void selectionSort(String[] str, int n) {
		// TODO Auto-generated method stub
		for(int i=0;i<n;i++){
			int min=i;
			for(int j=i+1;j<n;j++){
				if(str[j].charAt(1)<str[min].charAt(1)){
					min=j;
				}
			}
			
			String tmp=str[i];
			str[i]=str[min];
			str[min]=tmp;
			
		}
	}

	private static void bubbleSort(String[] str, int n) {
		// TODO Auto-generated method stub
		for(int i=0;i<n;i++){
			for(int j=n-1;j>i;j--){
				if(str[j].charAt(1)<str[j-1].charAt(1)){
					String tmp=str[j];
					str[j]=str[j-1];
					str[j-1]=tmp;
				}
			}
		}
	}

	private static void print(String[] str, int n) {
		// TODO Auto-generated method stub
		int i=0;
		for(i=0;i<n-1;i++){
			System.out.print(str[i]+" ");
		}
		System.out.println(str[i]);
	}

	
}



Measured memory_bytes: 26324
using System;
using System.Collections.Generic;
using CompLib.Util;

public class Program
{
    private int K;

    public void Solve()
    {
        var sc = new Scanner();
        K = sc.NextInt();

        List<long> ans = new List<long>();
        List<long> l = new List<long>();
        for (int i = 1; i <= 9; i++)
        {
            l.Add(i);
        }

        while (ans.Count < K)
        {
            var next = new List<long>();
            foreach (long j in l)
            {
                long m = j % 10;
                if (m < 9)
                {
                    next.Add(j * 10 + m + 1);
                }

                if (m > 0)
                {
                    next.Add(j * 10 + m - 1);
                }

                next.Add(j * 10 + m);
                ans.Add(j);
            }

            l = next;
        }

        ans.Sort();
        Console.WriteLine(ans[K - 1]);
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 27488
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int MOD = (int)1e9 + 7;
const double PI = 3.14159265358979323846;

int main(void) {
  ll x, k, d;
  cin >> x >> k >> d;
  ll pos = x;
  ll cnt1 = 0;
  cnt1 = pos / d;
  if (cnt1 < 0) cnt1 *= -1;  // 0をまたぐ直前までdをタス（ひく）回数
  if (k < cnt1) cnt1 = k;
  if (pos > 0) {
    pos -= cnt1 * d;
  } else {
    pos += cnt1 * d;
  }
  k -= cnt1;
  if (k > 0 && k % 2 == 1) {
    if (pos > 0) {
      pos -= d;
    } else {
      pos += d;
    }
  }
  if (pos < 0) pos *= -1;
  cout << pos << endl;
  return 0;
}

Measured memory_bytes: 3632
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

    def same(self, x, y):
        return self.root(x)==self.root(y)

    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:
            return

        if self.par[x]>self.par[y]:
            x,y = y,x

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self,x):
        return -self.par[self.root(x)]

from collections import defaultdict

n,k,l = map(int, input().split())
u = UnionFind(n+1)
v = UnionFind(n+1)

for _ in range(k):
  p,q = map(int, input().split())
  u.unite(p,q)

for _ in range(l):
  r,s = map(int, input().split())
  v.unite(r,s)

d = defaultdict(int)
for i in range(1,n+1):
  x = (u.root(i), v.root(i))
  d[x] += 1

print(*[d[(u.root(i), v.root(i))] for i in range(1,n+1)])

Measured memory_bytes: 41580
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const long long MOD = 1e9+7;
template<typename T> inline void add(T& a, T b) { a += b; if (a >= MOD) a -= MOD; }

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

  int H,W; cin >> H >> W;
  vector<string> S;
  vector<bool> WHITE_W(W, true);

  rep(h, H) {
    string tmp; cin >> tmp;
    bool all_white = true;
    rep(w, W) {
      if(tmp[w] == '#') {
        all_white = false;
        WHITE_W[w] = false;
      }
    }
    if(!all_white) {
      S.push_back(tmp);
    }
  }

  vector<string> ANS(S.size());

  rep(h, S.size()) {
    string ans = "";
    rep(w, W) {
      if(!WHITE_W[w]) {
        ans.push_back(S[h][w]);
      }
    }
    ANS[h] = ans;
  }

  rep(i, ANS.size()) cout << ANS[i] << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll inf = numeric_limits<ll>::max()/3;

int main(void){
  int n,k,q;
  cin >> n >> k >> q;
  vector< ll > a;
  vector< P > sorted;
  for(int i = 0;i < n;++i){
    ll tmp; cin >> tmp;
    a.push_back(tmp);
    sorted.push_back(P(tmp,i));
  }
  sort(sorted.begin(),sorted.end());

  ll res = inf;
  int alive[2010];
  fill(alive,alive+2010,1);
  alive[n] = 0;
  for(auto pa : sorted){
    ll val,idx;
    tie(val,idx) = pa;
    if(!alive[idx])
      continue;

    vector< ll > ok;
    vector< ll > st;
    for(int i = 0;i <= n;++i){
      if(alive[i]){
        st.push_back(a[i]);
      }
      else{
        sort(st.begin(),st.end());
        for(int j = 0;j < (int)st.size()-k+1;++j){
          ok.push_back(st[j]);
        }
        st.clear();
      }
    }
    if(ok.size() < q)
      break;

    sort(ok.begin(),ok.end());
    res = min(res, ok[q-1] - val);
    alive[idx] = 0;
  }
  cout << res << endl;
  return 0;
}



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

void upper(string &s) {
    for (int i = 0; i < s.size(); i++) {
        if (isalpha(s[i]) && islower(s[i])) s[i] = toupper(s[i]);
    }
}

int main() {
    string W, T;
    cin >> W;
    upper(W);
    int sum = 0;
    while (true) {
        cin >> T;
        if (T == "END_OF_TEXT") break;
        upper(T);
        if (T == W) sum += 1;
    }
    cout << sum << endl;
}

Measured memory_bytes: 1192
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int HWMAX = 1501;
int Hs[1501];
int Ws[1501];
int HW[1501*2002];

int main(){
    while(1){
        memset(Hs,0,sizeof(int)*HWMAX);
        memset(Ws,0,sizeof(int)*HWMAX);
        memset(HW,0,sizeof(int)*HWMAX*2002);
        int N,M;
        int i,j;
        scanf("%d %d",&N,&M);
        if(N == 0) break;
        for(i=1;i<=N;i++){
            int h;
            scanf("%d",&h);
            Hs[i] = (Hs[i-1]+h);
        }

        for(i=0;i<M;i++){
            int w;
            scanf("%d",&w);
            Ws[i] = (Ws[i-1]+w);
        }
        for(i=0;i<N+1;i++){
            for(j=0;j<M+1;j++){
                HW[Hs[i]+Ws[j]]++;
            }
        }
        int cnt = 0;
        for(i=0;i<2002*HWMAX;i++){
            cnt += HW[i]*(HW[i]-1)/2;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

Measured memory_bytes: 12356
#include <bits/stdc++.h>
using namespace std;
#define M 500005
#define bug printf("bug\n")
#define ll long long
int n,arr[5][M],dp[M][5];

int f(int pos,int mask)
{
    if(pos>n) return 0;
    if(dp[pos][mask]!=-1) return dp[pos][mask];
    if(!mask) return dp[pos][mask] = max(f(pos+1,2)+arr[2][pos] , max(f(pos+1,3)+arr[3][pos],f(pos+1,3)+arr[3][pos]));
    if(mask==1) return dp[pos][mask] = max(f(pos+1,2)+arr[2][pos] , f(pos+1,3)+arr[3][pos]);
    if(mask==2) return dp[pos][mask] = max(f(pos+1,1)+arr[1][pos] , f(pos+1,3)+arr[3][pos]);
    if(mask==3) return dp[pos][mask] = max(f(pos+1,2)+arr[2][pos] , f(pos+1,1)+arr[1][pos]);

}

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        dp[i][1] = dp[i][2] = dp[i][3] = -1;
        scanf("%d %d %d",&arr[1][i],&arr[2][i],&arr[3][i]);
    }
    printf("%d\n",max(f(1,1),max(f(1,2),f(1,3))));
    return 0;
}


Measured memory_bytes: 13056
#金額
moto = int(input())
num   = int((moto + 1 ) / 2)
retu    = input().split()
card = list( map((lambda x:int(x)),retu))
cardList = sorted(card, reverse=True)
Alice = 0
Bob = 0

for w in range(num):
    Alice = Alice + cardList[w*2]
    if moto > (w*2+1):
        Bob = Bob + cardList[w*2+1]

print(Alice - Bob)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <numeric>
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define LL long long
#define Dev 1000000007

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
int n,h,w;
cin>>n>>h>>w;
cout<<(n-h+1)*(n-w+1)<<endl;
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//const long long INF64 = 1'000'000'000'000'000'000ll;
#define MOD 1000000007
double pow(double a, int n){
    double ret =1;
    while(n){
        if(n%2==1)ret*=a;
        a*=a;
        n/=2;
    }
    return ret;
}
const int MAX_SIZE = 1000009; 
vector<int >isprime(MAX_SIZE , true); 
vector<int >prime; 
vector<int >SPF(MAX_SIZE); 
void manipulated_seive(int N) 
{ 
	 isprime[0] = isprime[1] = false ; 
	 for (int i=2; i<N ; i++) 
	 { 
		 if (isprime[i]) 
		 { 
			 prime.push_back(i); 
			 SPF[i] = i; 
		 } 
		 
		 for (int j=0;j < (int)prime.size() && i*prime[j] < N && prime[j] <= SPF[i];j++) 
		 { 
			 isprime[i*prime[j]]=false; 
			 SPF[i*prime[j]] = prime[j] ; 
		 } 
	 } 
}
int gcd(int a,int b){
	if(a==0){
		return b;
	}
	return gcd(b%a,a);
}
#undef int
int main() {
    #define int long long
    //fastio;
	int n,m,sum=0;
	cin>>n>>m;
	priority_queue<int> q;
	for(int i=0;i<n;i++){
		int a;
		cin>>a;
		sum+=a;
		q.push(a);
	}
	while(!q.empty()&& m>0){
		if(q.top()>0 ){
			int a=q.top();
			q.pop();
			sum-=(a%2==0)?a/2:(a/2+1);
			if(a/2>0){
				q.push(a/2);
			}
			m--;
		}
	}
	cout<<sum;
    return 0;
}


Measured memory_bytes: 17016
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
ll k_th(ll x,ll y)
{
    if(y<x) return  y;
    return y+1;
}
bool judge(ll m)
{
    ll k=m/2;
    for(ll i=max(1ll,k-1);i<=min(k+1,m);i++)
        if(k_th(a,i)*k_th(b,m-i+1)>=a*b) return false;
    return true;
}
int main()
{
    int q;scanf("%d",&q);
    while(q--)
    {
        scanf("%lld%lld",&a,&b);
        ll l=0,r=2e9,ans;
        while(l<=r)
        {
            ll m=l+r>>1;
            if(judge(m)) ans=m,l=m+1;
            else r=m-1;
        }
        printf("%lld\n",ans);
    }
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000000)

N,M=map(int, input().split())
a = [0]*M
for i in range(M):
  a[i] = int(input())

def memoize(f):
  table = {}
  def func(*args):
    if not args in table:
      table[args] = f(*args)
    return table[args]
  return func

@memoize

def step(n):
  if n==0:
    return(1)
  elif n==1:
    return(1)
  else:
    return((step(n-1)+step(n-2))%1000000007)

if M==0:
  print(step(N))
else:
  b = [0]*(M+1)
  b[0] = step(a[0]-1)
  if M>=2:
    for i in range(M-1):
      if a[i+1]-a[i] == 1:
        b[i+1] = 0
      else:
        b[i+1] = step(a[i+1]-a[i]-2)
  b[M] = step(N-a[M-1]-1)

  answer = 1
  for i in range(M+1):
    answer = answer*b[i]%1000000007
  print(answer)

Measured memory_bytes: 231908
#include <cstdio>
#include <cmath>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;


int main()
{
	int A, B, C;
	scanf("%d %d %d", &A, &B, &C);
	int ans = max(B + C - A, 0);
	printf("%d", ans);
}

Measured memory_bytes: 128
w = int(input())
n = int(input())

amida = []
amida.append(-1)
for i in range(w):
    amida.append(i)

for l in range(n):
    a,b = [int(i) for i in input().split(",")]
    tmp = amida[a]
    amida[a] = amida[b]
    amida[b] = tmp

for i in range(w):
    print(amida[i+1]+1)



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

uint64_t gcd(uint64_t a, uint64_t b) {
    if (a > b) {
        if (a % b == 0) {
            return b;
        } else {
            return gcd(b, a % b);
        }
    } else {
        if (b % a == 0) {
            return a;
        } else {
            return gcd(a, b % a);
        }
    }
}

uint64_t lcm(uint64_t a, uint64_t b) {
    return a / gcd(a, b) * b;
}

int main() {
    int N;
    std::cin >> N;

    uint64_t l = 0, T;
    for (int i = 0; i < N; ++i) {
        std::cin >> T;
        if (i == 0) {
            l = T;
        } else {
            l = lcm(l, T); 
        }
    }

    std::cout << l << std::endl;

    return 0;
}


Measured memory_bytes: 256
using System;

namespace aoj8d
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string p = Console.ReadLine();

            s = s + s;
            if(s.IndexOf(p) == -1)  //p???s?????????????????????????????£?????´???
            {
                Console.WriteLine("No");
            }
            else
            {
                Console.WriteLine("Yes");
            }
        }
    }
}

Measured memory_bytes: 9728
import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

n,=I()
arr=I()
sumi=0
for i in range(1,n):
    if arr[i-1]>arr[i]:
        sumi+=arr[i-1]-arr[i]
        arr[i]=arr[i-1]

print(sumi)


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

typedef int VAL;
const int MAX_UF = 110000;
const VAL SUM_UNITY = 0;

struct UnionFind {
  int par[MAX_UF];
  int rank[MAX_UF];
  VAL weight[MAX_UF];

  UnionFind(int n = 0) {
	for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, weight[i] = SUM_UNITY;
  }
  
  void init(int n) {
	for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, weight[i] = SUM_UNITY;
  }
  
  int root(int x) {
	if (par[x] == x) {
	  return x;
	}
	else {
	  int r = root(par[x]);
	  weight[x] += weight[par[x]];
	  return par[x] = r;
	}
  }

  VAL calc_weight(int x) {
	root(x);
	return weight[x];
  }
  
  bool issame(int x, int y) {
	return root(x) == root(y);
  }

  bool merge(int x, int y, VAL w) {
	w += calc_weight(x); w -= calc_weight(y);
	x = root(x); y = root(y);
	if (x == y) return false;
	if (rank[x] < rank[y]) swap(x, y), w = -w;
	if (rank[x] == rank[y]) ++rank[x];
	par[y] = x;
	weight[y] = w;
	return true;
  }

  VAL diff(int x, int y) {
	return calc_weight(y) - calc_weight(x);
  }
  
} uf;



int N, M;
int main() {
  cin >> N >> M;
  uf.init(N);
  for (int i = 0; i < M; ++i) {
	int l, r, d;
	cin >> l >> r >> d;
	--l, --r;
	if (uf.issame(l, r)) {
	  int diff = uf.diff(l, r);
	  if (diff != d) {
		puts("No");
		return 0;
	  }
	}
	else {
	  uf.merge(l, r, d);
	}
  }
  puts("Yes");
}




Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
// type
typedef long long ll;
typedef long double ld;
// loop
//#define For(i, l, r, x)     for (int i = l; i < r; i+=x)
//#define ForE(i, l, r, x)    for (int i = l; i <= r; i+=x)
//#define Ford(i, r, l)       for (int i = r; i > l; i--)
//#define FordE(i, r, l)      for (int i = r; i >= l; i--)
//#define Fora(i, a)          for (auto i : a)
// I/O
#define FAST_IO             std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//#define PrintV(a)           Fora(ii, a) cout << ii << ' '; cout << rl;
//#define PrintVl(a)          Fora(ii, a) cout << ii << rl;
//#define PrintA(a, l, r)     for (int ii = l; ii <= r; ii++) cout << a[ii] << ' '; cout << rl;
//#define PrintAl(a, l, r)    for (int ii = l; ii <= r; ii++) cout << a[ii] << rl;
//#define Ptest(x)            return cout << x, 0;
#define setpre(n)           fixed << setprecision(n)
// pair
#define F                   first
#define S                   second
#define pii                 pair<int, int>
#define pll                 pair<ll, ll>
#define pdd                 pair<ld, ld>
// vector & !!?(string)
#define eb                  emplace_back
#define pb                  push_back
#define all(a)              a.begin(), a.end()
#define rall(a)             a.rbegin(), a.rend()
#define sz(a)               a.size()
#define len(a)              a.length()
// geometry calc
#define pi                  acos(-1.0)
#define g_sin(a)            sin(a*pi/180)
#define g_cos(a)            cos(a*pi/180)
#define g_tan(a)            tan(a*pi/180)
// set val
#define ms0(a)              memset(a,        0, sizeof(a));
#define ms1(a)              memset(a,        1, sizeof(a));
#define msn1(a)             memset(a,       -1, sizeof(a));
#define msinf(a)            memset(a, 0x3f3f3f, sizeof(a));
// constant
const int mod1 = 998244353, mod = 1e9+7;
const int MAXN = 1e5 + 5, MAX_M = 2e5 + 5;
// code
#define int long long

int d[MAXN], pos[MAXN], n;
int par[MAXN], sz[MAXN], subd[MAXN];
map<int, int> orc;

bool comp(const int &a, const int &b){
    return d[a] > d[b];
}

void Solve() {
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> d[i]; pos[i] = i;
        orc[d[i]] = i;
    }
    sort(pos+1, pos+n+1, comp);
    // root at pos[n];
    for (int i = 1; i < n; i++){
        sz[pos[i]] ++;
        int parD = d[pos[i]] - n + 2*sz[pos[i]];
        if (parD >= d[pos[i]] || !orc.count(parD)){
            cout << "-1";
            return;
        }
        par[pos[i]] = orc[parD];
        sz[par[pos[i]]] += sz[pos[i]];
        // dist on subtree
        subd[par[pos[i]]] += subd[pos[i]] + sz[pos[i]];
    }
    if (subd[pos[n]] != d[pos[n]]){
        cout << -1;
        return;
    }
    for (int i = 1; i < n; i++){
        cout << pos[i] << ' ' << par[pos[i]] << endl;
    }
}

signed main(){
    FAST_IO;
    int TC = 1;
	//cin >> TC;
    while(TC--) Solve();
    return 0;
}


Measured memory_bytes: 13836
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

/*
文字の読み込み

何種類の文字があるか確かめる  O(N)
0出ない部分を取り出す
昇順にソート
counter = 0;
n = num - K
while(n>0){
    counter = 
    n--
}
*/
long long l[1000];



int main(void){
    int a,b,c,d,bit,val=0;
    char op1,op2,op3,_a,_b,_c,_d;
    scanf("%c%c%c%c",&_a,&_b,&_c,&_d);
    a = (int)_a-48;
    b = (int)_b-48;
    c = (int)_c-48;
    d = (int)_d-48;
    for(bit=0;bit<(1<<3);++bit){
        if(bit&1){
            val = a+b;
            op1 ='+';
        }else{
            val = a-b;
            op1 = '-';
        }
        if(bit&(1<<1)){
            val += c;
            op2 = '+';
        }else{
            val -=c;
            op2 = '-';
        }
        if(bit&(1<<2)){
            val+=d;
            op3 = '+';
        }else{
            val-=d;
            op3 = '-';
        }
        if(val == 7){
            printf("%d%c%d%c%d%c%d=7\n",a,op1,b,op2,c,op3,d);
            break;
        }
    }
    
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
constexpr int64_t mod=1e9+7;

int main()
{
  int n;
  cin>>n;
  vector<int> h(n),vec(n,0);
  for (int i = 0; i < n; ++i)
  {
    cin>>h[i];
  }
  reverse(h.begin(), h.end());
  for (int i = 1; i < n; ++i)
  {
    if(h[i]>=h[i-1]){
      vec[i]=vec[i-1]+1;
    }
    else{
      vec[i]=0;
    }
  }
  cout<<*max_element(vec.begin(), vec.end());
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 1<<30;
const ll MOD = 1e9+7;
const double EPS = 1e-9;


int main(int argc, const char * argv[]) {
  ll r, D, x;
  cin >> r >> D >> x;
  int ans = x;
  for (int i=0; i<10; i++){
    ans = ans*r - D;
    cout << ans << endl;
  }
  return 0;
}

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

int n;

int main() {
	cin >> n;
	bool isYes = 0;
	while (n) {
		if (n % 10 == 7) {
			isYes = 1;
			break;
		}
		n /= 10;
	}
	cout << (isYes ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;
#define mod 1000000007

long long ruijo(long long x,int n){
	long long p,ans;
	if(n==0)return 1;
	if(n==1)return x;
	if(n%2){
		p = ruijo(x,n/2);
		ans = (x*p)%mod;
		ans = (ans*p)%mod;
		return ans;
	}else{
		p = ruijo(x,n/2);
		ans = (p*p)%mod;
		return ans;
	}
}
long long dp[5002][5002]={};

int main(){
	dp[0][0]=1;
	for(int i=1;i<5001;i++){
		for(int j=0;j<5001;j++){
			if(j==0){
				dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
			}else{
				dp[i][j]=(2*dp[i-1][j-1]+dp[i-1][j+1])%mod;
			}
		}
	}
	int n;
	long long ans;
	string s;
	cin >> n;
	cin >> s;
	ans = (dp[n][s.size()]*ruijo(ruijo(2,s.size()),mod-2))%mod;
	cout << ans <<endl;
	return 0;
}

Measured memory_bytes: 195712
<?php
while (true) {
	$line = readline();
	readline_add_history($line);
	$inputs = explode(" ", $line);
	$a = intval($inputs[0]);
	$b = intval($inputs[1]);
	if (($a == 0) && ($b == 0)) {
		break;
	}
	if ($a < $b) {
		echo "{$a} {$b}", PHP_EOL;
	} else {
		echo "{$b} {$a}", PHP_EOL;
	}
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int n, a[3], b[3];

ll calc(ll k, int idx, bool flag){
	if(flag){
		return k/a[idx]*b[idx]+k%a[idx];
	}
	return k/b[idx]*a[idx]+k%b[idx];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	cin>>n;
	REP(i, 3){
		cin>>a[i];
	}
	REP(i, 3){
		cin>>b[i];
	}
	int c[3];
	int cnt=0;
	vi pls, mns;
	REP(i, 3){
		c[i]=b[i]-a[i];
		if(c[i]>=0){
			++cnt;
			pls.push_back(i);
		}
		else{
			mns.push_back(i);
		}
	}
	ll ans=n;
	if(cnt==1){
		ans=calc(n, pls[0], 1);
		ll tmp=ans;
		REP(i, tmp+1){
			CHMAX(ans, calc(i, mns[0], 0)+calc(tmp-i, mns[1], 0));
		}
	}
	else if(cnt==2){
		REP(i, n+1){
			CHMAX(ans, calc(i, pls[0], 1)+calc(n-i, pls[1], 1));
		}
		ans=calc(ans, mns[0], 0);
	}
	else{
		if(cnt==0){
			swap(a, b);
		}
		REP(i, n+1){
			ll tmp=calc(i, 0, 1);
			REP(j, n-i+1){
				CHMAX(ans, tmp+calc(j, 1, 1)+calc(n-i-j, 2, 1));
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
vector<string> S;
int dh[] = {1,-1,0,0};
int dw[] = {0,0,-1,1};

int main(){
    IOS;

    ll H,W;
    cin >> H >> W;

    ll Ch,Cw,Dh,Dw;
    cin >> Ch >> Cw >> Dh >> Dw;

    Ch-=1;
    Cw-=1;
    Dh-=1;
    Dw-=1;

    for(ll i=0;i<H;i++){
        string s;
        cin >> s;
        S.push_back(s);
    }

    vector<vector<ll>> cost(H,vector<ll>(W,-1));

    cost[Ch][Cw]=0;
    
    deque<pair<ll,ll>> q;
    q.push_back({Ch,Cw});

    while(!q.empty()){
        ll h,w;
        tie(h,w) = q.front();
        q.pop_front();
        for(ll i=0;i <4; i++){
            ll h_new = h - dh[i];
            ll w_new = w - dw[i];
            if(h_new <0 || h_new >=H || w_new < 0 || w_new >=W) continue;
            if(S[h_new][w_new]=='#') continue;
            if(cost[h_new][w_new] != -1 && cost[h_new][w_new] <= cost[h][w]) continue;
            cost[h_new][w_new] = cost[h][w];
            q.push_front({h_new,w_new});
        }
        for(ll i = h - 2; i <= h + 2; i++){
            for(ll j = w - 2; j <= w + 2; j++){
                if(i < 0|| i >=H || j < 0 || j >=W) continue;
                if(S[i][j] == '#') continue;
                if(cost[i][j] != -1) continue;
                cost[i][j] = cost[h][w] + 1;
                q.push_back({i,j});
            }
        } 
    }

    cout << cost[Dh][Dw] << endl;

    return 0;

}

Measured memory_bytes: 12704
N,M,Q=map(int,input().split())
a=[0]*Q
b=[0]*Q
c=[0]*Q
d=[0]*Q
for i in range(Q):
  a[i],b[i],c[i],d[i] =map(int,input().split())

  
from copy import deepcopy

ans_list=[]
def dfs(x,M,N,ans):
  if len(ans)<=N-1:
    for j in range(x,M+1):
      tmp=deepcopy(ans)
      tmp.append(j)
      if len(tmp)==N:
        ans_list.append(tmp)
      else:
        dfs(j,M,N,tmp)
    
q=dfs(1,M,N,[])


f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

Measured memory_bytes: 27776
#include <bits/stdc++.h>
using namespace std;
  
int main() {
    int N;
    long long K;
    cin >> N >> K;
    vector<int>A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    vector<int>B(N,0);
    int count = 0;
    int i = 0;
    int j = 0;
    long long x,y,z;
    int now;
    while (count == 0){
        now = A.at(i);
        if (B.at(now-1) == 0){
            B.at(now-1) = j + 1;
            i = now - 1;
            j++;
        }
        else {
            x = B.at(now-1) - 1;
            y = j + 1 - B.at(now-1);
            count = 1;
        }      
    }

    if (x == 0){
        if (K <= j){
            z = K;
        }
        else {
            if (K % y == 0){
                z = y;
            }
            else {
                z = K % y;
            }
        }
    }
    else {
        if (K <= j){
            z = K;
        }
        else {
            if ((K-x) % y == 0){
                z = x + y;
            }
            else {
                z = (K-x) % y + x;
            }
        }
    }

    for (int k = 0; k < N; k++) {
        if (B.at(k) == z){     
            cout << k + 1 << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 4824
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
class Comp implements java.util.Comparator<HashMap<String, Integer>> {
	 
	public int compare(HashMap<String, Integer> o1, HashMap<String, Integer> o2) {
		return o1.get("key1") - o2.get("key1") > 0 ? 1 : o1.get("key1") - o2.get("key1") == 0 ? 0 : -1;
	}
 
}
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int n = stdIn.nextInt(); 
		
		String[] s = new String[n];
		
		for(int i = 0; i < n; i++) {
			s[i] = stdIn.next();
		}
		
		
		Map<String,Integer> map = new TreeMap<>();
		
		
		
		
		for(int i = 0; i < n; i++) {
			if(!map.containsKey(s[i])) {
				map.put(s[i], 0);
			}
			map.put(s[i], map.get(s[i])+1);
			
		}
		int max = 0;
		
		for(int i = 0; i < n; i++) {
			max = Math.max(max, map.get(s[i]));
		}
		
	
	
		
		
		for(String a: map.keySet()) {
			if(map.get(a)== max) {
				System.out.println(a);
			}
		}
		
		
	}

}


Measured memory_bytes: 84160
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long


signed main(){
  int n;
  cin>>n;
  pair<int,int> a[200050];
  rep(i,n){
    int b;
    cin>>b;
    a[i]=make_pair(b,i);
  }
  sort(a,a+n);
  int ansmx=a[(n-1)/2].fst;
  int ansmn=a[n/2].fst;
  int ans[300050];
  rep(i,n){
    if(i<((n+1)/2)){
      ans[a[i].scd]=ansmn;
    }else{
      ans[a[i].scd]=ansmx;
    }
  }
  rep(i,n){
    cout<<ans[i]<<endl;
  }
  
  return 0;
}





Measured memory_bytes: 7680
#-*-coding:utf-8-*-
import math

def calculate_length(A,B,theta):
    radian=math.radians(theta)
    length=(A**2)+(B**2)-(2*A*B*math.cos(radian))
    return  math.sqrt(length)

def main():
    A,B,H,M = map(int,input().split())
    thetaA=H*30+M*0.5
    thetaB=M*6
    if thetaA == thetaB:
        print(abs(A-B))
    else:
        if thetaA > thetaB:
            theta=thetaA-thetaB
        elif thetaA < thetaB:
            theta = thetaB-thetaA
        length=calculate_length(A,B,theta)
        print(length)

if __name__=="__main__":
    main()

Measured memory_bytes: 9532
import bisect

N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
# a <= b <= c
for b in range(N):
    for a in range(b):
        ab = L[a] + L[b]
        r = bisect.bisect_left(L, ab) - 1
        l = b
        ans += r - l
print(ans)

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

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

    while(1) {
        if(C-B <= 0) {
            cout << "Yes" << endl;
            break;
        }
        C = C - B;
        if(A - D <= 0) {
            cout << "No" << endl;
            break;
        }
        A = A - D;
    }

    return 0;
}


Measured memory_bytes: 3632