akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
typedef long long ll;
typedef pair<int,int> pii;

int main(){
    int n;
    cin>>n;
    vector<ll> vec;
    ll sum = 0;
    rep(i,n){
        ll a;
        cin>>a;
        sum = sum^a;
        vec.push_back(a);
    }
    rep(i,n){
        cout<<(sum^vec[i])<<" ";
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 5324
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repx(i,x,n) for(int (i)=(x);(i)<(int)(n);(i)++)
#define repeq(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define repxeq(i,x,n) for(int (i)=(x);(i)<=(int)(n);(i)++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
using namespace std;
using ll = long long;
using Int = long long;

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = 1e8;

//少数点表示
//cout <<std::fixed << std::setprecision(14) <<double値
string t="";
vector<string> s;
int n;

void dfs(string d,int ch){
    if(d.size() == n){
        cout << d << endl;
        return;
    }
    
    repeq(i,ch){
        if(i != ch){
            dfs(d + (char)('a' + i),ch);
        }else{
            dfs(d + (char)('a' + i),ch+1);
        }
    }
}

int main(){
    //cin.tie( 0 ); ios::sync_with_stdio( false );
    cin >> n;
    string t = "a";
    dfs("",0);
}

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

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int x, y;
    cin >> x >> y;
    if (x * y > 0) {
        if (x <= y) {
            cout << y - x << "\n";
        } else {
            cout << x - y + 2 << "\n";
        }
    } else if (x * y == 0) {
        if (x <= y) {
            cout << y - x << "\n";
        } else {
            cout << x - y + 1 << "\n";
        }
    } else {
        cout << 1 + abs(abs(x) - abs(y)) << "\n";
    }
}

Measured memory_bytes: 256
#include <iostream>

struct monster{
  int life;
  int attack;
};

int main(){
  monster takahashi = {0, 0};
  monster aoki = {0, 0};
  
  std::cin >> takahashi.life >> takahashi.attack;
  std::cin >> aoki.life >> aoki.attack;
  
  while(true){
    aoki.life -= takahashi.attack;
    if(aoki.life <= 0){
      break;
    }
    
    takahashi.life -= aoki.attack;
    if(takahashi.life <= 0){
      break;
    }
  }
  
  if(0 < takahashi.life){
    std::cout << "Yes" << std::endl;
  }
  else{
    std::cout << "No" << std::endl;
  }
  
  return 0;
}

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

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, x, d;
    cin >> n >> x >> d;

    if (d == 0) {
        cout << (x == 0 ? 1 : n + 1) << "\n";
        return 0;
    }

    if (d < 0) {
        x = -x;
        d = -d;
    }
    map<long long, vector<pair<long long, long long>>> mp;
    for (long long i=0; i<=n; i++)
        mp[(i * x % d + d) % d].emplace_back(i * x + (i - 1) * i / 2 * d, i * x + (2 * n - i - 1) * i / 2 * d);

    long long ret = 0;
    for (auto &p : mp) {
        sort(p.second.begin(), p.second.end());
        long long l = p.second[0].first, r = p.second[0].second;
        for (int i=1; i<(int)p.second.size(); i++) {
            if (p.second[i].first > r) {
                ret += (r - l) / d + 1;
                l = p.second[i].first;
            }
            r = max(r, p.second[i].second);
        }
        ret += (r - l) / d + 1;
    }
    cout << ret << "\n";

    return 0;
}

Measured memory_bytes: 25488
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cmath>
#include <climits>
#include <map>
#include <queue>
#include <functional>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)
#define rep1(i, n) for(int i = 1; i <= (int) n; i++)
#define all(v) v.begin(),v.end()
const ll mod = 1e9+7;

int main() {
    int a;
    cin >> a;
    cout << a+a*a+a*a*a << endl;
    return 0;
}

Measured memory_bytes: 3568
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
ans = 0
H, W = map(int, input().split())
c = []
for i in range(10):
    tc = list(map(int, input().split()))
    c.append(tc)
c = np.array(c)
short = shortest_path(c)
# print(shortest_path(c))
A = []
for i in range(H):
    ta = list(map(int, input().split()))
    A.append(ta)
    for j in ta:
        if j != -1:
            ans += short[j][1]
            # print(ans)
print(int(ans))


Measured memory_bytes: 28904
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;
 
template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)
 
const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

 
int main() {
    ll N, T; cin >> N >> T;
    ll t[200100];
    rep(i,N) cin >> t[i];

    ll res = 0;
    rep(i,N-1) {
        if (t[i+1] - t[i] <= T) {
            res += t[i+1] - t[i];
        }
        else {
            res += T;
        }
    }
    res += T;

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
#define SORTD(s) sort((s).rbegin(),(s).rend())
#define rep(i,n) for(int i=0;i<(n);i++)
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; }
typedef long long ll;
#define PI 3.14159265358979323846264338327950L


int main() {
	int n,m,x,y;
  	cin>>n>>m>>x>>y;
  
  	int p[n],q[m];
  	int ap=-100;
  	int aq=100;
  
	rep(i,n){
      cin>>p[i];
      if(ap<p[i]){
      	ap=p[i];
      }
    }
  
  	rep(j,m){
    	cin>>q[j];
      if(aq>q[j]){
      	aq=q[j];
      }
    }
  
  

  
  if(ap<aq&&x<aq&&aq<=y){
  	cout<<"No War"<<endl;
  }
  
  else{
  	cout<<"War"<<endl;
  }
  	



}

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

int lcs(string str1, string str2){
  int C[1001][1001];
  int maxl = 0;

  str1 = ' ' + str1;
  str2 = ' ' + str2;

  for(int i = 1 ; i <= str1.size() ; i++) C[i][0] = 0;
  for(int j = 1 ; j <= str2.size() ; j++) C[0][j] = 0;

  for(int i = 1 ; i <= str1.size()-1 ; i++){
    for(int j = 1 ; j <= str2.size()-1 ; j++){
     
      if(str1[i] == str2[j]) C[i][j] = C[i - 1][j - 1] + 1;
      else if(C[i - 1][j] >= C[i][j -1]) C[i][j] = C[i - 1][j];
      else C[i][j] = C[i][j - 1];

      if(C[i][j] >= maxl) maxl = C[i][j];

    }
  }

  return maxl;
}

int main(){
  string str1, str2;
  int n;

  cin >> n;

  for(int i = 0 ; i < n ; i++){
    cin >> str1 >> str2;
    cout << lcs(str1, str2) << endl;
  }

  return 0;
}

Measured memory_bytes: 5128
#include <stdio.h>
int main(){
int w,h,x,y,r;
scanf("%d%d%d%d%d",&w,&h,&x,&y,&r);
if(x+r>w||y+r>h||x-r<0||y-r<0)printf("No\n");
else printf("Yes\n");
}

Measured memory_bytes: 2676
#include<iostream>

using namespace std;

int main() {
	int n, m;
	int h[1500], w[1500];
	while(1) {
		cin >> n >> m;
		if(!n && !m) break;
		
		int list[1500000] = {0};
		int sqn = 0;
		
		for( int i=0; i<n; i++) {
			cin >> h[i];
			for( int j=0; j<i+1; j++) {
				if(i!=j) h[j] += h[i];
				list[ h[j] ] += 1;
			}
		}
		for( int i=0; i<m; i++) {
			cin >> w[i];
			for( int j=0; j<i+1; j++) {
				if(i!=j) w[j] += w[i];
				sqn += list[ w[j] ];
			}
		}
	
		cout << sqn << endl;
	}
	return 0;
}

Measured memory_bytes: 7036
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1001001001;
constexpr long long INFL = (1LL<<60);
constexpr double eps = (1e-9);

class UnionFind {
public:
  // 親の番号を格納する。親だった場合は-(その集合のサイズ)
  vector<int> parent;

  // 作るときは parent の値を全て -1 にする
  // こうすると全てバラバラになる
  UnionFind(const int& n = 0) : parent(n, -1) {}

  // x がどのグループに属しているか調べる
  int find(const int& x) {
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
  }

  // x と y をくっつける  O(log n)
  bool unite(int x, int y) {
    // x と y を直接くっつけるのではなく，root(x) に root(y) をくっつける
    x = find(x);
    y = find(y);
    if (x == y) return false;  // すでにくっついているからくっつけない

    // 大きい方(x) に小さい方(y)をくっつけたい 大小が逆だったらひっくり返す
    if (size(x) < size(y)) swap(x, y);

    parent[x] += parent[y];  // x のサイズを更新する
    parent[y] = x;  // y の親を x に変更する
    return true;
  }

  // 自分のいるグループの頂点数を調べる
  int size(const int& x) { return -parent[find(x)]; }

  // x と y が同じグループに属しているか否か
  bool same(const int& x, const int& y) { return find(x) == find(y); }
};

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

  int n, m;
  cin >> n >> m;

  UnionFind uf(n);

  rep(i, m) {
    int a, b; cin >> a >> b; a--; b--;
    uf.unite(a, b);
  }

  int ans = 0;
  rep(i, n) chmax(ans, uf.size(i));

  cout << ans << endl;

  return 0;
}


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

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

    sort(p.begin(),p.end());
 
    int ans = 0;
    rep(i,k) ans += p[i];
  
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <map>

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBAG = true;

int main(){

    int a, b;
    cin >> a >> b;

    if(b == 1){
        cout << 0 << endl;
    }
    else{
        cout << a - b<< endl;
    }

}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 2000001145
#define LINF 100000000000000007
#define MOD 1000000007
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repb(i, n) for (int i = n - 1; i >= 0; i--)
#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
int ceil2(int a,int b){if(a%b){return a/b+1;}else{return a/b;}}
//typedef long long int ll;
typedef pair<int,int> P;
struct edge{int to,cost;};

int ans;
int n,m,x,y;
string s;
bool dp[6002][16009];//i番目の合計がjのとき
bool dp2[6002][16009];
signed main(){
	cin>>s>>x>>y;
	vector<int> v,w;
	int cnt=0,num=0;
	rep(i,s.size()){
		if(s[i]=='T'){
			if(cnt%2==0)v.push_back(num);
			else w.push_back(num);
			cnt++;
			num=0;
		}
		else{
			num++;
		}
		if(i==s.size()-1 && s[i]!='T'){
			if(cnt%2==0)v.push_back(num);
			else w.push_back(num);
		}
	}
	
	//DEB(v.size())END
	//DEB(w.size())END
	
	x+=8000;y+=8000;
	dp[0][8000]=1;
	for(int i=0;i<v.size();i++){
		if(x<8000){
			for(int j=16000;j>=0;j--){
				dp[i+1][j+v[i]]=(dp[i+1][j+v[i]]||dp[i][j]);
				if(i!=0)dp[i+1][j-v[i]]=(dp[i+1][j-v[i]]||dp[i][j]);
			}
		}
		else{
			for(int j=0;j<=16000;j++){
				dp[i+1][j+v[i]]=(dp[i+1][j+v[i]]||dp[i][j]);
				if(i!=0)dp[i+1][j-v[i]]=(dp[i+1][j-v[i]]||dp[i][j]);
			}
		}
	}
	dp2[0][8000]=1;
	for(int i=0;i<w.size();i++){
		if(y<8000){
			for(int j=16000;j>=0;j--){
				dp2[i+1][j+w[i]]=(dp2[i+1][j+w[i]]||dp2[i][j]);
				dp2[i+1][j-w[i]]=(dp2[i+1][j-w[i]]||dp2[i][j]);
			}
		}
		else{
			for(int j=0;j<=16000;j++){
				dp2[i+1][j+w[i]]=(dp2[i+1][j+w[i]]||dp2[i][j]);
				dp2[i+1][j-w[i]]=(dp2[i+1][j-w[i]]||dp2[i][j]);
			}
		}
	}
	if(dp[v.size()][x]&&dp2[w.size()][y])cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
}


Measured memory_bytes: 129408
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  int a, b, c;
  cin >> a >> b >>c;

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


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

using ll = long long;
using ull = unsigned long long;
using namespace std;
constexpr int inf = 1<<30;
constexpr int mo = 1e9+7;
constexpr ll infl = 1ll<<60;


int main(){
    cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    
    ll n,d;
    cin>>n>>d;
    int count = 0;
    for(int i=0;i<n;++i){
        ll x,y;
        cin>>x>>y;
        if(x*x + y*y <= d*d){
            count++;
        }
    }
    cout << count << endl;
    return 0;
    
}

Measured memory_bytes: 3652
import java.util.Scanner;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int[] p = new int [3];
		for(int i = 0; i < 3; i++) {
			p[i] = sc.nextInt();
		}

		Arrays.sort(p);

		System.out.println(p[0] + p[1]);
	}
}


Measured memory_bytes: 23252
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
constexpr int kMod = 1000000007;
typedef long long LL;

template<typename T>
class Mat {
 public:
  explicit Mat(int row, int col) : row_(row), col_(col) {
    a_ = std::vector<std::vector<T>>(row, std::vector<T>(col, 0));
  }

  int row() const { return row_; }
  int col() const { return col_; }
  std::vector<T>& operator[](int row) {
    return a_[row];
  }

  Mat& operator=(const Mat &m) {
    a_ = m.a_;
    return *this;
  }

  Mat operator*(const Mat& m) const {
    Mat ret(row_, col_);
    for (int r = 0; r < row_; ++r) {
      for (int c = 0; c < col_; ++c) {
        for (int k = 0; k < col_; ++k) {
          T v = (a_[r][k] * m.a_[k][c]) % kMod;
          ret[r][c] = (ret[r][c] + v) % kMod;
        }
      }
    }
    return ret;
  }

  Mat& operator*=(const Mat& m) {
    *this = (*this) * m;
    return *this;
  }

  std::vector<T> operator*(const std::vector<T> &v) const {
    std::vector<T> ret(row_, 0);
    for (int r = 0; r < row_; ++r) {
      for (int k = 0; k < col_; ++k) {
        ret[r] += (a_[r][k] * v[k]) % kMod;
      }
    }
    return ret;
  }

  void Display() {
    for (int r = 0; r < row_; ++r) {
      for (int c = 0; c < col_; ++c) {
        std::cout << a_[r][c] << " ";
      }
      std::cout << std::endl;
    }
  }

  private:
   std::vector<std::vector<T>> a_;
   int row_;
   int col_;
};

template<typename T>
Mat<T> pow(Mat<T> m, LL k) {
  int row = m.row();
  int col = m.col();

  Mat<T> ret(row, col);
  for (int r = 0; r < row; ++r) ret[r][r] = 1;

  LL i = 1;
  while (i <= k) {
    if (i & k) ret *= m;
    i <<= 1;
    m = m * m;
  }

  return ret;
}

int main() {
  LL dp[51] = {};
  int N; LL K; std::cin >> N >> K;
  Mat<LL> m(N, N);
  for (int c = 0; c < N; ++c) {
    for (int r = 0; r < N; ++r) {
      std::cin >> m[r][c];
    }
  }

  auto v = pow(m, K) * std::vector<LL>(N, 1);
  LL sum = 0;
  for (LL a : v) sum = (sum + a) % kMod;
  std::cout << sum << std::endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long int;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1e11;
const ll MOD = 1000000007;
typedef pair<int,int> P;
ll match[10] = {0,2,5,5,4,5,6,3,7,6};
string big(string s,string t){
    string res = "";
    rep(i,s.length()){
        if (s[i]-'0' > t[i]-'0'){
            res = s;
            break;
        }
        else if (s[i]-'0' < t[i]-'0'){
            res = t;
            break;
        }
    }
    if (res == "") res = s;
    return res;
}
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    PRINT(a*b/2);
}

Measured memory_bytes: 256
N,K=map(int,input().split())
x=list(map(int,input().split()))

tmp=10**10
for i in range(N-K+1):
  if x[i]*x[i+K-1]<0:
    tmp=min(tmp,min(abs(x[i]),abs(x[i+K-1]))*2+max(abs(x[i]),abs(x[i+K-1])))
  else:
    tmp=min(tmp,max(abs(x[i]),abs(x[i+K-1])))
print(tmp)

Measured memory_bytes: 14228
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = LI()

    ans = (sum(A) ** 2 - sum([i ** 2 for i in A])) // 2 % MOD
    print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 32476
n = int(input())
a = list(map(int, input().split()))
l = [0] * n
r = [0] * n

for i, h in enumerate(a):
    if 0 <= i + h < n:
        l[i + h] += 1
    if 0 <= i - h < n:
        r[i - h] += 1

ans = 0
for i in range(n):
    ans += l[i] * r[i]
print(ans)


Measured memory_bytes: 103092
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <math.h>

using namespace std;

//conversion
//------------------------------------------
inline long toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline long toLong(string s) {long v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const long double EPS = 1e-12;
const int INF = 10000;

struct edge{int to,cost;};
typedef pair<int,int> P;//firstは最短距離,secondは頂点番号


int main(){
	int n;
	
	while(cin>>n){
		if(n==0)break;
		
		int sum=0,mi=INF,ma=-1;
		REP(i,n){
			int s;
			cin>>s;
			sum+=s;
			ma=max(ma,s);
			mi=min(mi,s);
		}
		cout<<floor((sum-ma-mi)/(n-2))<<endl;
	}
	return 0;
}

Measured memory_bytes: 1228
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	try {
    		final int A = sc.nextInt();
    		final int B = sc.nextInt();

    		int kuchi = 1;
    		if (B == 1) {
				System.out.println(0);
				System.exit(0);
    		}
    		for (int i=1; i<=B; i++) {
    			kuchi = kuchi - 1 + A;
    			if (kuchi>=B) {
    				System.out.println(i);
    				System.exit(0);
    			}
    		}

    	} finally {
    		sc.close();
    	}
    }
}



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

int main() {
    int K;
    cin >> K;
    queue<string> que;
    for (char c = '1'; c <= '9'; ++c) {
        if (c == '1') que.push("1");
        if (c == '2') que.push("2");
        if (c == '3') que.push("3");
        if (c == '4') que.push("4");
        if (c == '5') que.push("5");
        if (c == '6') que.push("6");
        if (c == '7') que.push("7");
        if (c == '8') que.push("8");
        if (c == '9') que.push("9");
    }
    int cnt = 0;
    while (true) {
        string s = que.front();
        que.pop();
        ++cnt;
        if (cnt == K) {
            cout << s << endl;
            return 0;
        }
        if (s[s.size() - 1] == '0') {
            que.push(s + "0");
            que.push(s + "1");
        }
        else if (s[s.size() - 1] != '9') {
            char l = s[s.size() - 1];
            string ll;
            ll = (l - 1);  que.push(s + ll);
            ll = l;        que.push(s + l);
            ll = (l + 1);  que.push(s + ll);
        }
        else {
            que.push(s + "8");
            que.push(s + "9");
        }
    }
}


Measured memory_bytes: 13824
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC exit(0);
using namespace std;
int k;
string s;
int main() {
    DAU
    cin >> k >> s;
    for (char& c : s)
        c = (c - 'A' + k) % 26 + 'A';
    cout << s;
    PLEC
}


Measured memory_bytes: 3556
fn main() {
    let input = {
        use std::io::*;
        let mut input = String::new();
        let _ = stdin().read_to_string(&mut input);
        input
            .replace("JPY", "1.0")
            .replace("BTC", "380000.0")
            .split_whitespace()
            .skip(1)
            .map(|w| w.parse::<f64>().unwrap())
            .collect::<Vec<_>>()
    };
    let total = input.chunks(2).fold(0.0, |r, x| r + x[0] * x[1]);
    println!("{:?}", total);
}

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

// Define
using ll = int64_t;
using ul = uint64_t;
using ld = long double;
const ll MOD = 1e9 + 7;
const ll INF = LONG_MAX;
const ul MAX = ULONG_MAX;
#define endl '\n'
#define space ' '
#define elif else if
#define def inline auto
#define func inline constexpr ll
#define run __attribute__((constructor)) def _
#define all(v) begin(v), end(v)

// Debug
#define debug(x) cerr << (x) << " (L:" << __LINE__ << ")" << '\n'

// Loop
#define inc(i, a, n) for (ll i = (a), _##i = (n); i <= _##i; ++i)
#define dec(i, a, n) for (ll i = (a), _##i = (n); i >= _##i; --i)
#define rep(i, n) inc (i, 0, n - 1)

// Stream
#define fout(n) cout << fixed << setprecision(n)
#define fasten cin.tie(0), ios::sync_with_stdio(0)

// Speed
run() { fasten, fout(10); }
#pragma GCC optimize("-O3")
#pragma GCC target("avx")

// Math
func gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
func lcm(ll a, ll b) { return a * b / gcd(a, b); }

signed main() {
    ll A, B, C;
    cin >> A >> B >> C;
    ll D = A + B + C - max(A, max(B, C));
    cout << max(A, max(B, C)) * 10 + D << endl;
}

// for compilation: g++ -O3 -o _ _.cpp -std=c++17


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

typedef long long ll;

const int MAXN = 16;
const int MAXL = (1 << 16) + 10;
const ll NEG = -1e18;

vector<int> grafo[MAXL];
ll valor[MAXL],dp[MAXL],mat[MAXN][MAXN];
int vis[MAXL],N;

void brute(int pos,int bitmask,int submask){

	if(pos == N){
		if(__builtin_popcount(submask) == 0) return;
		grafo[bitmask].push_back(submask);
		return;
	}

	brute(pos+1,bitmask,submask);
	brute(pos+1, bitmask | (1 << pos), submask );
	brute(pos+1, bitmask | (1 << pos), submask | (1 << pos) );

}

void calcula(){

	for(int bitmask = 1;bitmask < (1 << N);bitmask++){
		for(int i = 0;i<N;i++){
			if(!(bitmask & (1 << i))) continue;
			for(int j = i+1;j<N;j++){
				if(!(bitmask & (1 << j))) continue;
				valor[bitmask] += mat[i][j];
			}
		}
	}

}

ll solve(int bitmask){

	if(bitmask == 0) return 0;
	if(vis[bitmask]) return dp[bitmask];

	vis[bitmask] = 1;

	ll best = NEG;

	for(int submask : grafo[bitmask]){
		best = max(best, solve(bitmask ^ submask) + valor[submask] );
	}

	return dp[bitmask] = best;

}

int main(){

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

	brute(0,0,0);
	calcula();

	cout << solve((1 << N) - 1) << endl;

	return 0;

}

Measured memory_bytes: 172796
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)

ll dp[102][102];
vector<pii> c;

ll solve(int left,int right){
	if(dp[left][right]!=INF)return dp[left][right];
	
	for(int k=left+1;k<right;k++){
		dp[left][right] = min(solve(left,k)+solve(k,right)+c[left].first*c[k-1].second*c[k].first*c[right-1].second,dp[left][right]);
	}
	return dp[left][right];
}

int main(){
	int n;
	cin>>n;
	c.resize(n);
	rep(i,n)cin>>c[i].first>>c[i].second;
	
	rep(i,102)rep(j,102)dp[i][j]=INF;
	rep(i,n)dp[i][i+1]=0;
	
	cout<<solve(0,n)<<endl;
}

Measured memory_bytes: 3116
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dunk(n) cout << n << endl
#define all(v) v.begin(), v.end()


int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    map<char,long long> mp;
    rep(i,n) mp[s.at(i)]++;
    
    long long ans = mp['R']*mp['G']*mp['B'];

    for(int i=0; i<=n-3; i++){
        for(int j=i+1; j<=n-2; j++){
            int k = j+(j-i);
            if(k>=n) break;
            if(s.at(i)!=s.at(j) && s.at(j)!=s.at(k) && s.at(k)!=s.at(i)) ans--;
        }
    }
    
    dunk(ans);
}



Measured memory_bytes: 3636
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <stack>

using namespace std;

typedef long long ll;
typedef long double ld;

//#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define mkt make_tuple
#define no {cout << -1; return;}

const int N = 2e5 + 7;

int ans[N];

void solve() {
    loop(i, N)
        ans[i] = -1;
    int n, q;
    cin >> n >> q;
    vector <ti> cut(n);
    loop(i, n) {
        int l, r, x;
        cin >> l >> r >> x;
        cut[i] = mkt(x, l - x, r - x);
    }
    sort(all(cut));
    set <pi> ask;
    loop(i, q) {
        int x; cin >> x;
        ask.insert({ x, i });
    }
    loop(i, n) {
        auto it = ask.lower_bound({ get<1>(cut[i]), 0 });
        while (it != ask.end() && it->F < get<2>(cut[i])) {
            ans[it->S] = get<0>(cut[i]);
            it = ask.erase(it);
        }
    }
    loop(i, q)
        cout << ans[i] << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

Measured memory_bytes: 15848
#include<iostream>
#include<algorithm>

using namespace std;

int pc(int b){
  return __builtin_popcount(b);
}

int main(){
  int R,C;
  cin>>R>>C;
  string s[128];
  for(int i=0;i<R;i++){
    cin>>s[i];
  }
  int dp[1<<16];
  fill(begin(dp),end(dp),-1e9);
  dp[0]=0;
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      int ndp[1<<16];
      fill(begin(ndp),end(ndp),-1e9);
      for(int k=0;k<1<<C;k++){
	if(dp[k]>=0){
	  ndp[(k<<1)%(1<<C)]=max(ndp[(k<<1)%(1<<C)],dp[k]);
	  int nc=pc(k%(1<<j));
	  if(nc<s[i].size()){
	    ndp[(k*2+1)%(1<<C)]=max(ndp[(k*2+1)%(1<<C)],dp[k]
				+(i&&k>>C-1&1&&s[i-1][s[i-1].size()-pc(k>>j)]==s[i][nc])
				+(C>1&&k%2&&nc&&s[i][nc-1]==s[i][nc])
				);
	  }
	}
      }
      copy(begin(ndp),end(ndp),begin(dp));
    }
    for(int j=0;j<1<<C;j++){
      if(pc(j)<s[i].size()){
	dp[j]=-1e9;
      }
    }
  }
  cout<<2**max_element(begin(dp),end(dp))<<endl;
}

Measured memory_bytes: 1728
#[allow(unused_imports)]
use std::cmp::*;
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: isize = read();
    let m: isize = read();
    let X: isize = read();
    let Y: isize = read();

    let mut flag = false;

    let mut mx = -100;
    for _ in 0..n {
        let x = read();
        mx = max(mx, x);
    }

    let z = mx + 1;

    for _ in 0..m {
        let y: isize = read();
        if y < z {
            flag = true;
        }
    }

    if X >= z || z > Y {
        flag = true;
    }

    if flag {
        println!("War");
    } else {
        println!("No War");
    }
}

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

int main()
{
    ll k,n,x,maxi=0,d=0,first;
    cin>>k>>n;
    ll a[n+1];
    for(ll i=0; i<n;i++)
    {
        cin>>x;
        if(i==0)
            first=x;
        maxi=max(x-d,maxi);
        d=x;
    }
    maxi=max(k-x+first,maxi);
    cout<<k-maxi<<endl;

}




Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	try {
    		final int N = sc.nextInt();
    		final int Q = sc.nextInt();
    		int[] tree = new int[N];
    		int[] values = new int[N];
    		int[] sumValues = new int[N];
    		boolean[] calclated = new boolean[N];

    		for (int i=0; i<N-1; i++) {
    			final int ai = sc.nextInt();
    			final int bi = sc.nextInt();
    			tree[bi-1] = ai-1;
    		}

    		for (int i=0; i<Q; i++) {
    			final int pi = sc.nextInt();
    			final int xi = sc.nextInt();
    			values[pi-1] += xi;
    		}

    		sumValues[0] = values[0];
    		calclated[0] = true;
    		for (int i=1; i<N; i++) {
    			calcSum(tree, values, sumValues, i, calclated);
    		}
    		for (int i=0; i<N; i++) {
    			System.out.print(sumValues[i]);
    			System.out.print(" ");
    		}
    		System.out.println();

    	} finally {
    		sc.close();
    	}
    }

    public static int calcSum(int[] tree, int[] values, int[] sumValues, int currentIndex, boolean[] calculated) {
    	if (!calculated[currentIndex]) {
        	sumValues[currentIndex] = values[currentIndex] + calcSum(tree, values, sumValues, tree[currentIndex], calculated);
        	calculated[currentIndex] = true;
    	}
    	return sumValues[currentIndex];
    }
}



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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define SORTG(v) sort(v.begin(),v.end(),greater<>())
#define SORT(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/3

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<string> Vs;

template<class T> void chmax(T& a, T b) {if(a<b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a>b){a=b;}}
void YesNo(int a) {if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
void YESNO(int a) {if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}
void AorB(int a,string b,string c) {if(a){cout<<b<<endl;}else{cout<<c<<endl;}}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void start(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);}

signed main(){start();
    int r,g,b,n,ans=0;
    cin>>r>>g>>b>>n;
    REP(i,0,n/r+1){
        REP(j,0,(n-r*i)/g+1){
            if(n-r*i-g*j>=0 && (n-r*i-g*j)%b==0) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}



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

const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const int MOD=1000000007;

ll n,K;
ll calc(ll x){
	ll sum=0;
	int cnt=0;
	while(x){
		sum+=x;
		x>>=1;
		cnt++;
		if(cnt==n)break;
	}
	return sum;
}

int main(){
	cin>>n>>K;
	ll ok=0,ng=K+1;
	while(ng-ok>1){
		ll t=(ok+ng)/2;
		if(calc(t)<=K)ok=t;
		else ng=t;
	}
	cout<<ok<<endl;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define OUTPUT(x) (output(x), output("\n"))
#else
#define OUTPUT(x) (void)0
#endif

ll modpow(ll x, ll b){
    ll res = 1;
    while(b){
        if(b&1)res = res * x % MOD;
        x = x * x % MOD;
        b>>=1;
    }
    return res;
}

ll modinv(ll x){
    return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
    if(was_output)cout << " ";
    cout << a;
    was_output = true;
}
void outendl(){
    was_output = false;
    cout << endl;
}
ll in(){
    ll res;
    scanf("%lld", &res);
    return res;
}

template<class t>
istream& operator>>(istream& is, vector<t> &x){
    for(auto &i:x)is >> i;
    return is;
}

template<class t, class u>
istream& operator>>(istream& is, pair<t, u> x){
    is >> x.first >> x.second;
    return is;
}


int main(){
    int n = in();
    int k = in();
    int ans = 0;
    while(n){
        n /= k;
        ++ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
A = list(map(int, input().split()))
s = set(A)
F = [False]*(10**6+100)
cnt = Counter(A)

for i in range(10**6+100):
    if i in s:
        F[i] = True

for i in range(1, 10**6+100):
    if i in s:
        for j in range(2*i, 10**6+100, i):
            F[j] = False
    
ans = 0

for i in range(10**6+100):
    if F[i] and cnt[i]==1:
        ans += 1

print(ans)

Measured memory_bytes: 155380
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		while (true) {
			int H = sc.nextInt();
			int W = sc.nextInt();
			if (H == 0 && W == 0) {
				break;
			}

			for (int j = 0; j < H; j++) {

				for (int i = 0; i < W; i++) {
					System.out.printf("#");

				}

				System.out.printf("\n");
			}
			System.out.printf("\n");

		}

	}
}

Measured memory_bytes: 62076
#include <bits/stdc++.h>
#define PI acos(-1)
#define eq(x,y) (fabs((x)-(y)) < eps)
#define debug(x) cerr<<x<<endl;
#define endl "\n"
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9+7;
const int nmax=1e5+10;
const int eps=1e-8;


int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout<<fixed;
    //cout.tie(NULL);
    int k,x;
    cin>>k>>x;

    for(int i=x-k+1;i<x+k;i++)
        cout<<i<<" ";
    cout<<endl;


    return 0;
}


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> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;


template<int mod> struct ModInt{
    long long x=0; 
    constexpr ModInt(long long x=0):x((x%mod+mod)%mod){}
    constexpr ModInt operator+(const ModInt& r)const{return ModInt(*this)+=r;}
    constexpr ModInt operator-(const ModInt& r)const{return ModInt(*this)-=r;}
    constexpr ModInt operator*(const ModInt& r)const{return ModInt(*this)*=r;}
    constexpr ModInt operator/(const ModInt& r)const{return ModInt(*this)/=r;}
    constexpr ModInt& operator+=(const ModInt& r){ if((x+=r.x)>=mod) x-=mod; return *this;}
    constexpr ModInt& operator-=(const ModInt& r){ if((x-=r.x)<0) x+=mod; return *this;}
    constexpr ModInt& operator*=(const ModInt& r){ if((x*=r.x)>=mod) x%=mod; return *this;}
    constexpr ModInt& operator/=(const ModInt& r){ return *this*=r.inv();}
    ModInt inv() const {
        long long s=x,sx=1,sy=0,t=mod,tx=0,ty=1;
        while(s%t!=0){
            long long temp=s/t,u=s-t*temp,ux=sx-temp*tx,uy=sy-temp*ty;
            s=t;sx=tx;sy=ty;
            t=u;tx=ux;ty=uy;
        }
        return ModInt(tx);
    }
    ModInt pow(long long n) const {
        ModInt a=1;
        while(n>0){
            if(n&1) a*=*this;
            *this*=*this;
            n>>=1;
        }
        return a;
    }
    friend constexpr ostream& operator<<(ostream& os,const ModInt<mod>& a) {return os << a.x;}
    friend constexpr istream& operator>>(istream& is,ModInt<mod>& a) {return is >> a.x;}
};
using mint = ModInt<MOD>;

struct combination{
    int N;
    vector<mint> fac,finv,inverse;
    combination(int N):N(N){
        fac.resize(N+1);finv.resize(N+1);
        fac[0]=1;
        for(int i=1;i<=N;++i){fac[i]=fac[i-1]*i;}
        finv[N]=fac[N].inv();
        for(int i=N-1;i>=0;--i){finv[i]=finv[i+1]*(i+1);}
    }
    void inverse_build(){
        inverse.resize(N+1);
        inverse[1]=1;
        for(int i=2;i<=N;++i){inverse[i]=finv[i]*fac[i-1];}
    }
    mint c(int n,int k){
        if(n<k||n<0||k<0) return 0;
        return fac[n]*finv[n-k]*finv[k];
    }
    mint p(int n,int k){
        if(n<k||n<0||k<0) return 0;
        return fac[n]*finv[n-k];
    }
};

int main(){
    ll s;
    cin >> s;
    if(s<=2){
        cout << 0 << endl;
        return 0;
    }
    mint ans = 0;
    combination com(10000);
    for(int i=1;3*i<=s;i++){
        ans += com.c(s-3*i+i-1,i-1);
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  int h, w;
  cin >> h >> w;
  vector<string> a(h);
  rep(i,h) cin >> a.at(i);
  
  vi x(h), y(w);
  rep(i,h){
    int cnt = 0;
    rep(j,w){
      if (a.at(i).at(j) == '.') cnt++;
    }
    if (cnt != w) x.at(i) = 1;
  }
  rep(i,w){
    int cnt = 0;
    rep(j,h){
      if (a.at(j).at(i) == '.') cnt++;
    }
    if (cnt != h) y.at(i) = 1;
  }
  
  rep(i,h){
    rep(j,w){
      if (x.at(i) == 1 && y.at(j) == 1) cout << a.at(i).at(j);
    }
   if (x.at(i) == 1) cout << endl;
  }
  return 0;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i, s, n) for (int i = s; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
using namespace std;
using ll = long long;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
const int inf = (1<<29);

int main() {
    // 入力
    int n, m; cin >> n >> m;
    vector<int> P(m), Y(m);
    for (int i = 0; i < m; ++i) cin >> P[i] >> Y[i], --P[i];
    
    // vals[v] := P[i] = v であるような i についての Y[i] の値を集めたもの
    vector<vector<int> > vals(n);
    for (int i = 0; i < m; ++i) vals[P[i]].push_back(Y[i]);
    
    // 各 p の値に対して
    for (int v = 0; v < n; ++v) {
        sort(vals[v].begin(), vals[v].end());
        
        // 今回は不要だが、通常は数のダブりをなくす
        vals[v].erase(unique(vals[v].begin(), vals[v].end()), vals[v].end());
    }

    // 答え
    for (int i = 0; i < m; ++i) {
        int v = P[i];
        printf("%06d", v + 1);
        
        // 座標圧縮して導いた答え
        int id = lower_bound(vals[v].begin(), vals[v].end(), Y[i]) - vals[v].begin();
        printf("%06d\n", id + 1);
    }
}

// int main() {

//     int N, M;
//     cin >> N >> M;

//     vector<int> P(M), Y(M);
//     vector<vector<int>> yd(N);

//     REP(i, M) {
//         cin >> P[i] >> Y[i];
//         P[i]--;
//         yd[P[i]].push_back(Y[i]);
//     }

//     REP(i, N) {
//         sort(yd[i].begin(), yd[i].end());
//         // ダブりをなくす
//         yd[i].erase(unique(yd[i].begin(), yd[i].end()), yd[i].end());
//     }

//     REP(i, M) {
//         int v = P[i];
//         printf("%06d", v+1);

//         // 座標圧縮して導いた答え
//         int id = lower_bound(yd[i].begin(), yd[i].end(), Y[i]) - yd[i].begin();
//         printf("%06d\n", id+1);
//     }

//     return 0;

    
//     // vector<tuple<int, int, int>> tp; // i, 県, 年
//     // vector<int> Y, P;
//     // REP(i, M) {
//     //     cin >> Y[i] >> P[i];
//     //     vp.push_back(make_tuple(i, Y[i], P[i]));
//     // }

//     // sort(ALL(tp));

//     // vector<pint> ans; //answer
//     // ans.push_back(make_pair(1, 1));
//     // RREP(i, 1, n) {
//     //     if (tp[i][1] == tp[i-1][1]) 
//     // }
    

//     return 0;
// }

Measured memory_bytes: 7808
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr ll INF = (ll)1e9;
constexpr double PI = 3.1415926535897932;
template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int func(string str) {
	int res = 0;
	rep(i, 0, str.size()) {
		res += str[i] - '0';
	}
	return res;
}

int main() {
	init();

	int N; cin >> N;
	int ans = INF;
	rep(i, 1, N) {
		string a = to_string(i), b = to_string(N - i);
		int cnt = func(a) + func(b);
		chmin(ans, cnt);
	}
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <tuple>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <cstdio>
#include <numeric>
#define REP(i, n) for(LL i = 0;i < n;i++)
#define REPR(i, n) for(LL i = n;i >= 0;i--)
#define FOR(i, m, n) for(LL i = m;i < n;i++)
#define FORR(i, m, n) for(LL i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define INF 999999999
#define MOD 1000000007
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;
typedef pair<int, P> PP;
typedef pair<LL, LP> LPP;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

/*************** using variables ***************/
LL n, h;
LL a[100005], b[100005];
LL sum_b = 0;
LL max_a = 0;
LL sum = 0;
LL ans = 0;
/**********************************************/

int main(){
    cin >> n;
    cin >> h;
    REP(i, n){
        cin >> a[i] >> b[i];
        max_a = max(max_a, a[i]);
    }
    
    SORT(b, n);
    REPR(i, n-1){
        if(b[i] < max_a) break;
        sum += b[i];
        ans++;
        if(sum >= h ) break;
    }

    if(sum >= h){
        cout << ans << endl;
        return 0;
    }
    while(sum < h){
        sum += max_a;
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		boolean flg = true;

		// 整数の入力
		int n = sc.nextInt();

		int array[] = new int[n];

		int flg2 = -1;
		
		for(int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
		}
		
		for(int i = 0; i < n; i++) {
			//array[i] = sc.nextInt();
			
			if(flg2 != -1 && array[i-1] > array[i]) {
				int tmp = array[flg2];
				array[flg2] = array[i];
				array[i] = tmp;
				
				flg2 = -1;
				break;
			}
			
			if(i > 0 && flg2 == -1 && array[i-1] > array[i]) {
				flg2 = i-1;
			}
		}
		
		if(flg2 != -1) {
			int tmp = array[flg2+1];
			array[flg2+1] = array[flg2];
			array[flg2] = tmp;
		}
		
		for(int i = 0; i < n-1; i++) {
			if(array[i] > array[i+1]) {
				flg = false;
				break;
			}
		}

		if(flg) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}

        sc.close();
	}
}

Measured memory_bytes: 21716
#coding:UTF-8
import math

def KC(n,p1,p2):
    if n==0:
        return
    s=[(2*p1[0]+p2[0])/3,(2*p1[1]+p2[1])/3]
    t=[(p1[0]+2*p2[0])/3,(p1[1]+2*p2[1])/3]
    u=[(t[0]-s[0])*math.cos(math.pi/3)-(t[1]-s[1])*math.sin(math.pi/3)+s[0],(t[0]-s[0])*math.sin(math.pi/3)+(t[1]-s[1])*math.cos(math.pi/3)+s[1]]
    KC(n-1,p1,s)
    print(str(format(s[0],'.8f'))+" "+str(format(s[1],'.8f')))
    KC(n-1,s,u)
    print(str(format(u[0],'.8f'))+" "+str(format(u[1],'.8f')))
    KC(n-1,u,t)
    print(str(format(t[0],'.8f'))+" "+str(format(t[1],'.8f')))
    KC(n-1,t,p2)
    
  
if __name__=="__main__":
    n=int(input())
    p1=[0,0]
    p2=[100,0]
    print(str(format(p1[0],'.8f'))+" "+str(format(p1[1],'.8f')))
    KC(n,p1,p2)
    print(str(format(p2[0],'.8f'))+" "+str(format(p2[1],'.8f')))

Measured memory_bytes: 8056