akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

template<typename T, typename U>
using pv=vector<pair<T,U>>;
template<typename T>
using matrix=vector<vector<T>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using ilpair=pair<int,ll>;
using lipair=pair<ll,int>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;

#define PI 3.141592653589793
#define INTINF ((1<<30)-1)
#define LLINF ((1LL<<62)-1)
#define MPRIME 1000000007
#define MPRIME9 998244353
#define MMPRIME ((1ll<<61)-1)

#define len length()
#define pushb push_back
#define fi first
#define se second

#define setpr fixed<<setprecision(15)
#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())

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;
}

template<class T>
inline void init(T& v) {
	for(auto &a: v) cin>>a;
}
template<class T, class U>
inline void init(vector<pair<T,U>>& v) {
	for(auto &a: v) cin>>a.first>>a.second;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a;
}
template<class T, class U, class N>
inline void init(vector<pair<T,U>>& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a.first>>a.second;
}

inline void out() {
	cout<<endl;
}
template<class T, class... U>
inline void out(T a, U... alist) {
	cout<<a<<" ";
	out(forward<U>(alist)...);
}

template<class N>
void resiz(N n) {
	//empty
}
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

bool isout(int h, int w, int H, int W) {
	return ( h<0 || h>=H || w<0 || w>=W );
}

ll binpow(ll a, ll ex, ll p) {
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}


int N;
string S,T;

void input() {
	cin>>N>>S;
}

bool rec(string t) {
	T=t;
	for(int i=1; i<N-1; i++) {
		if((S[i]=='o') ^ (T[i]=='S') ^ (T[i-1]=='S')) T.pushb('S');
		else T.pushb('W');
	}
	
	if( ((S[N-1]=='o') ^ (T[N-1]=='S') ^ (T[N-2]==T[0])) && ((S[0]=='o') ^ (T[0]=='S') ^ (T[N-1]==T[1])) ) {
		cout<<T<<endl;
		return true;
	}

	return false;
}

void solve() {
	string Tl[]={"SS","SW","WS","WW"};
	for(int i=0; i<4; i++) {
		if(rec(Tl[i])) return;
	}
	cout<<-1<<endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(15);
	int t=1;
	while(t) {
		input();
		solve();
		t--;
	}
}

Measured memory_bytes: 3736
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int N;
vector<long long> a, b;

int main()
{
    long long ans = 0;

    cin >> N;
    a.resize(N);
    b.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < N; i++)
    {
        cin >> b[i];
    }

    vector<long long> aa, bb;
    aa.resize(N);
    bb.resize(N);
    long long num;
    for (int k = 0; k < 30; k++)
    {
        long long T1 = pow(2, k);
        long long T2 = 2 * T1;
        long long T3 = 3 * T1;
        long long T4 = 4 * T1;
        for (int i = 0; i < N; i++)
        {
            aa[i] = a[i] % T2;
            bb[i] = b[i] % T2;
        }
        sort(bb.begin(), bb.end());
        num = 0;
        for (int j = 0; j < N; j++)
        {
            int l1 = distance(bb.begin(), lower_bound(bb.begin(), bb.end(), T1 - aa[j]));
            int r1 = distance(bb.begin(), lower_bound(bb.begin(), bb.end(), T2 - aa[j]));
            int l2 = distance(bb.begin(), lower_bound(bb.begin(), bb.end(), T3 - aa[j]));
            int r2 = distance(bb.begin(), lower_bound(bb.begin(), bb.end(), T4 - aa[j]));
            //printf("%d %d %d %d\n", l1, r1, l2, r2);
            num += r1 - l1 + r2 - l2;
        }
        //cout << num << endl;
        ans += T1 * (num % 2);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 7040
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9 + 7, MOD = 1e9 + 7;
const long long LINF = 1e18;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
	int n;
	cin >> n;
	string s = "AB";
	s += (char)'C' + (n / 1000);
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
def get_parent x
    @parent[x] = get_parent(@parent[x]) if @parent[x] != x
    @parent[x]
end

while true
    w, h = gets.chomp.split.map(&:to_i)
    break if [w, h] == [0, 0]
    map = []
    h.times{map << gets.chomp.split.map(&:to_i)}
    @parent = (0...(w * h)).to_a
    for y in 0...h
        for x in 0...w
            if map[y][x] == 1
                [[y - 1, x - 1], [y - 1, x], [y - 1, x + 1], [y, x - 1]].each{|y2, x2|
                    next if y2 < 0 || x2 < 0 || x2 >= w
                    next if map[y2][x2] == 0
                    p1 = get_parent(y * w + x)
                    p2 = get_parent(y2 * w + x2)
                    min, max = [p1, p2].minmax
                    @parent[max] = min
                }
            else
                @parent[y * w + x] = nil
            end
        end
    end
    count = 0
    @parent.each_with_index{|x, i| count += 1 if x == i}
    puts count
end



Measured memory_bytes: 7028
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int n, x;
    cin >> n >> x;
    int p = 0;
    int ans = 1;
    REP(i, n)
    {
        int t;
        cin >> t;
        p += t;
        if (p <= x)
        {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
#import numpy as np

N, Y = list(map(int, input().split()))

ans_x, ans_y, ans_z = -1, -1, -1

#n_list = np.append([0], range(N+1))
#n_list = np.append(n_list, [N])

#print(n_list)
#print(len(n_list))
#print(range(len(n_list)))
#print(range(10 ,len(n_list)))

for i in range(N+1) :
  x = i
  #sum = 10000*x
  #if sum > Y :
  #  continue

  for j in range(N+1-x) :
    y = j
    z = N - x - y
    sum = 10000*x + 5000*y + 1000*z
    #print("tameshi : " + str(x) + " " + str(y) + " " + str(z))
    if sum == Y :
      ans_x=x
      ans_y=y
      ans_z=z

print(str(ans_x) + " " + str(ans_y) + " " + str(ans_z))

Measured memory_bytes: 3064
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <limits.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#ifndef ULLONG
typedef unsigned long long ULLONG;
#endif
#ifndef LLONG
typedef long long LLONG;
#endif
template <class _T> static _T tp_abs(const _T& a) {
	return ((a < 0) ? (a * -1) : a);
}
template <class _T> static _T tp_min(_T a, _T b) {
	return a < b ? a : b;
}
template <class _T> static _T tp_max(_T a, _T b) {
	return a > b ? a : b;
}
template<class _T> static void get1int(_T& a) {
	const char* fmt = " %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld";
	}

	if (scanf(fmt, &a) < 0) {
		printf("g1int Error\n");
	}
}
template<class _T> static void get2int(_T& a, _T& b) {
	const char* fmt = " %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld";
	}

	if (scanf(fmt, &a, &b) < 0) {
		printf("g2int Error\n");
	}
}
template<class _T> static void get3int(_T& a, _T& b, _T& c) {
	const char* fmt = " %d %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld %lld";
	}

	if (scanf(fmt, &a, &b, &c) < 0) {
		printf("g3int Error\n");
	}
}

static void B_task();

int main()
{
	B_task();
	
	fflush(stdout);
	return 0;
}

static void B_task()
{
	int N;
	get1int(N);

	int seq[21] = { 0 };
	for (int i = 0; i < N; i++) {
		get1int(seq[i]);
	}

	int cnt = 0;
	for (int i = 1; i < N - 1; i++) {
		if ((seq[i - 1] < seq[i]) && (seq[i] < seq[i + 1])) {
			cnt++;
		}
		else if ((seq[i - 1] > seq[i]) && (seq[i] > seq[i + 1])) {
			cnt++;
		}
	}
	printf("%d\n", cnt);
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args) {	
	Main main = new Main();
    	main.solveA();
    }
    
    private void solveA() {
    	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
 
	if (n>=1000){
	       System.out.println("ABD");
	}
	else{
               	       System.out.println("ABC");
	    }
    }
}

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

#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define eb emplace_back

typedef long long ll;
typedef pair<int,int> ii;
typedef vector< pair<int,int> > vii;
const int INF = 0x3f3f3f3f;
 
int main() {
    ios_base::sync_with_stdio(false);
    int a,b;
    cin >> a >> b;
    int x = 1;
    int ans = 0;
    while(x < b) x = (x-1) + a, ans++;
    cout << ans << endl;
    return 0;
}



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

typedef long long ll;

const int MOD = (int) 1e9 + 7;
const int N = 100001;
int dp[N];
int n, k;

ll add(ll a, ll b) {
    return (a + b + MOD) % MOD;
}

ll power(ll a, int b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    ll res = 0;
    for (ll i = k; i > 0; --i) {
        ll cnt = power(k / i, n);
        for (int j = i + i; j <= k; j += i) {
            cnt = add(cnt, -dp[j]);
        }
        dp[i] = cnt;
        res = add(res, dp[i] * i % MOD);
    }

    cout << res << endl;

    return 0;
}



Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

const int MOD_TYPE = 1;
const ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(50) << setiosflags(ios::fixed);
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  int q;
  cin >> q;
  rep(qi, q)
  {
    int b, e;
    cin >> b >> e;
    reverse(a.begin() + b, a.begin() + e);
  }
  rep(i, a.size()) cout << a[i] << (i == a.size() - 1 ? "\n" : " ");
  return 0;
}



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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

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;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

using vi=vector<int>;
using vii=vector<vi>;

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()
#define decimal(x) fixed<<setprecision(x)

double n(double key){
    double ans=0.0;
    double L=0.0,R=key/3,mid=0.0;
    int cnt=0;
    //cout<<key-3*mid<<endl;
    while(key-(3*mid)>=0.00001){
        mid=L+(R-L)/2;
        if(key>3*mid)L=mid;
        else R=mid;
        //cout<<R<<" "<<L<<" "<<mid<<" "<<key-(3*mid)<<endl;
        //cout<<endl;
        if(cnt==11)break;
        cnt++;
    }
    return R*R*R;
}

//直方体
int main(){
    double L;
    cin>>L;
    cout<<decimal(10)<<(L/3)*(L/3)*(L/3)<<endl;
    return 0;
}

//a=97,z=122

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
using namespace std;
using ll = long long;

struct Pair {
	ll a,b;
};

bool Less(Pair &left, Pair &right) {
	return left.b < right.b;
}	

int main() {
	ll N, M;
	cin >> N >> M;
	vector<Pair> v(M);
	for (ll i=0;i<M;++i) {
		cin >> v[i].a >> v[i].b; 
		// valueを0-originに変換
		v[i].a--;
		v[i].b--;
	}
	sort(v.begin(), v.end(), Less); 
	/*
	for (ll i=0; i<M; ++i) {
		cout << v[i].a << "," << v[i].b << endl;
	}
	*/

	// bについて昇順としておいて, index が b-1(0-origin)の橋で分割できるかどうかを順に調べていく.
	// 分割ずみの要望(a,b)については橋を壊さなくて良い.
	// 壊す橋について追加していく.
	ll ans = 1;// 1つめの要望については必要
	ll latest_bridgh = v[0].b - 1;
	for (ll i=1; i<M; ++i) {
		if (v[i].a <= latest_bridgh && latest_bridgh < v[i].b) {
			continue;
		}
		ans++;
		latest_bridgh = v[i].b - 1;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define in(a, n) for(int i=0;i<n;i++)
#define w while(t--)
#define tc int t; cin>>t;
int intlog(double base, double x) {
    return (int)(log(x) / log(base));
}
bool sortbysec(const pair<string,long long> &a,
              const pair<string,long long> &b)
{
    return (a.second < b.second);
}
long long b[1000009];
long long z[1000009];
int lcm(int a, int b)
 {
    return (a*b)/__gcd(a, b);
 }
int main()
{
    int q[3];
    in(q,3) cin>>q[i];
    if(q[0]-q[1]==0)
        cout<<q[2];
    else if(q[0]-q[2]==0)
        cout<<q[1];
    else
        cout<<q[0];

}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{ 
  int a,b;
  cin>>a>>b;
  int c;
  c=a*b;
  if(c%2==1)
  cout<<"Odd";
  else	
  cout<<"Even";
  system("pause");
  return 0;
}


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

int main()
{   
	while (1) {
		int a;
		cin >> a;
		if (a == 0)break;
		vector<int>b(a);
		vector<int>c(0);
		for (int d = 0; d < a; d++) {
			int e;
			cin >> e;
			b[d] = e;
		}
		sort(b.begin(), b.end());
		int g = 0;
		for (int f = 1; f < a * 2 + 1; f++) {
			for (int j = 0; j < a; j++) {
				if (b[j] == f)break;
				if (a - 1 == j)c.push_back(f);
			}
		}
		int ba = 0;
		for (int k = 0;; k++) {
		ss:;
			if (k % 2 == 0) {
				for (int l = 0; l < b.size(); l++) {
					if (ba < b[l]) {
						
						ba = b[l];
						for (int q = l; q < b.size(); q++)b[q] = b[q + 1];
						b.pop_back(); k++; if (b.size() == 0 || c.size() == 0)goto pp; goto ss;
					}
					int x = b.size();
					x--;
					if (x == l) { ba = 0; k++; goto ss; }
				}
			}
			else {
				for (int l = 0; l < c.size(); l++) {
					if (ba < c[l]) {
						
						ba = c[l];
						for (int q = l; q < c.size(); q++)c[q] = c[q + 1];
						c.pop_back(); k++; if (b.size() == 0 || c.size() == 0)goto pp; goto ss;
					}
					int x = c.size();
					x--;
					if (x == l) { ba = 0; k++; goto ss; }
				}
			}
			if (b.size() == 0 || c.size() == 0)goto pp;
		}
	pp:;
		cout << c.size() << endl << b.size() << endl;
	}
}

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

int main() {
	int a = 1;
	vector<int> xy(2);
	while (a == 1) {
		cin >> xy[0] >> xy[1];
		sort(xy.begin(), xy.end());
		if (!(xy[0]== 0 & xy[1] == 0)) {
			cout << xy[0] << " " << xy[1] << endl;
		}
		else if (xy[0] == 0 & xy[1] == 0) {
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 3088
#include <cstdint>
#include <iostream>

using namespace std;

int32_t main()
{
  uint32_t num;

  uint32_t mi = UINT32_MAX;
  uint32_t ma = 0;

  cin >> num;
  for (uint32_t i = 0; i < num; i++) {
    uint32_t val;
    cin >> val;
    mi = min(mi, val);
    ma = max(ma, val);
  }

  cout << ma - mi << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// 方針
// 連結文字列のうち、内部に”AB"を含むものはその数を直接sumに足せばいい。
// その他で問題になるのが、

// 1,左にB,右にAをもつ
// 2,左にB
// 3,右にA
// 4,どちらもない

// の４つだが、4は無視していい。

// c1,c2,c3 をそれぞれ、1,2,3の数とすると

// 1, if(c1 == 0 ) のとき
//      2,3の数で決まり、min(2,3)　によってABの数はきまる。

// 2, if(c1 != 0 ) && ( c2,c3 が両方とも0ではない ) のとき
//      1と同様に min(2,3) を考えた後、”AB"のAとB間に1を挟んでいくと、そのぶんだけABの数は増える。

// 3, if(c1 != 0 ) && c2 == 0 && c3 == 0 のとき
//      初めに一つ両端のどちらかにA、Bが必要なので、その分をひいて　1の数 - 1 個のABがうまれる。

// 以上を作る。
// その際、ABを含む、1234の判別を可能にする関数か何かを作る必要がありそう。



// 反省点
// 1234に分類するところまでは思いついたが、内部にABを含むものをどう処理していいか思いつかず、飛ばしてしまった。
// 冷静に考えて、ABはそのまま足せばいいはずなのに、C問題だから難しいと思って飛ばしちゃった。


//（参照渡しではnullは渡せないので、
//  値がnullになる可能性があるものは変更の可能性がなくてもpointerで渡しましょう。）

int check_AB(string &S,int *pc){
    int res = 0;
    if(S[0] == 'B' && S[S.size() - 1] == 'A'){
        pc[0] += 1;
    }
    else if (S[0] == 'B'){
        pc[1] += 1;
    }
    else if (S[S.size() - 1] == 'A'){
        pc[2] += 1;
    }

    for (int i = 0;i < S.size() - 1 ;i++){
        if(S[i] == 'A' && S[i + 1] == 'B'){
            res += 1;
        }
    }
    return res;
}



int main(){
    int N;
    cin >> N;
    string S;
    
    int count = 0;
    int c[3] = {0,0,0};

    for (int j = 0;j<N;j++){
        cin >> S ;
        count += check_AB(S,c);
      //  cout << c[0] << ' ' << c[1] << ' ' << c[2] << endl; 　c[i]の内部の確認用ループ
    }

    if(c[0] == 0){ // case 1
        count += min(c[1],c[2]);
    }
    else if(c[1] == 0 && c[2] == 0){ // case 3
        count += c[0] - 1 ;
    }
    else { // case 2
        count += min(c[1],c[2]) + c[0] ;
    }

    cout << count << endl;

}

Measured memory_bytes: 256
#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(int i=(int)a, i##_len=(b); i<i##_len; i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define int long long
using namespace std;
using P = pair<int, int>;
using ll = long long;
using prique = priority_queue<int>;
const ll INF = LLONG_MAX/3;

/*-----Library-----*/

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; }

struct UnionFind {
    vector<int> par; // 親ノード
    vector<int> rank; // ランク
    vector<int> sizeuf; //要素数
    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n); rank.resize(n); sizeuf.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
            rank[i] = 0;
            sizeuf[i]=1;
        }
    }

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

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

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

    int size(int x){
        return sizeuf[root(x)];
    }
};

long long gcd(long long a,long long b){
    if(b==0)return a;
    return gcd(b,a%b);
}

long long lcm(long long i,long long j){
    return i*(j/gcd(i,j));
}
//コンビネーション
/*
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 */
/*-----Library-----*/
const int MOD=1234567;
signed main(){
	int n,q;
	cin>>n>>q;
	int a[110000];
	rep(i,n){
		cin>>a[i];
	}
	sort(a,a+n);
	rep(i,q){
		int l,r;
		cin>>l>>r;
		cout<<(upper_bound(a,a+n,r)-a)-(lower_bound(a,a+n,l)-a)<<endl;
	}
}




Measured memory_bytes: 3948
#include <iostream>
using namespace std;
int main(void){
    int h,w,n,p=-1;
    cin>>h>>w>>n;
    int s[h*w];
    for(int i=0;i<n;i++){
        int c;
        cin>>c;
        for(int j=0;j<c;j++){p++;s[p]=i+1;}
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(i%2==0){
                cout<<s[w*i+j]<<" ";
            }
            else{
                cout<<s[w*i-j+w-1]<<" ";
            }
        }
        cout<<endl;
    }
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define f              first
#define s              second
#define gc getchar_unlocked
#define fo(i,start,end) for(int i=start;i<end;i++)
#define FORR(i,end,start) for(int i=end-1;i>start;i--)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define inf std::numeric_limits<double>::infinity()
//#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define INPUT(a,n) fo(i,0,n) cin>>a[i];
#define INPUT2d(a,n,k) fo(i,0,n) fo(j,0,k) cin>>a[i][j];
#define mk(a,n,type)  type *a=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define SIZE 100005
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int mpow(int base, int exp); 
void ipgraph(int n, int m);
void dfs(int u, int par);

const int mod = 1'000'000'007;
const int N = 3e5, M = N;
//=======================

vi g[N];
int a[N];

void solve() {
  ll n,ans=0; cin>>n;
  ll a[n];
  INPUT(a,n)
  sort(a,a+n);
  fo(p,0,n) fo(j,p+1,n) fo(k,j+1,n){
    if(a[p]+a[j]>a[k] && a[p]!=a[j] && a[j]!=a[k]) ++ans;
  }
  cout<<ans<<'\n';
  
}

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif


    // ll t = 1;
    // cin >> t;
    // while(t--) {
      solve();
    //}

    return 0;
}

int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}

void ipgraph(int n, int m){
	int i, u, v;
	while(m--){
		cin>>u>>v;
    u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
}



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

int main() {
	// your code goes here
	int a[5],b[5],c[5];
	for(int i = 0; i < 5; i++)
	{
	    cin >> a[i];
	    b[i] = a[i] / 10;
	    c[i] = a[i] % 10;
    }
	int sum[5];
	for(int i = 0; i < 5; i++)
	{
	    sum[i] = 0;
	}
	for(int i = 0; i < 5; i++)
	{
	    for(int j = 0; j < 5; j++)
	    {
	        if(i == j)
	        {
	            sum[i] += a[j];
	        }
	        else
	        {
	            if(c[j] == 0)
	            {
	                sum[i] += a[j];
	            }
	            else
	            {
	                sum[i] = sum[i] + (b[j] + 1) * 10;
	            }
	        }
	    }
	}
	sort(sum,sum+5);
	cout << sum[0];
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define abdelrahman010 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
int n , a[N] , pref[N] , suf[N];
int main() {
    abdelrahman010
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i <= n;i++)
        pref[i] = __gcd(pref[i - 1] , a[i]);
    for(int i = n;i >= 1;i--)
        suf[i] = __gcd(suf[i + 1] , a[i]);
    int ans = 0;
    for(int i = 1;i <= n;i++)
        ans = max(ans , __gcd(pref[i - 1] , suf[i + 1]));
    cout << ans;
    return 0;
}

Measured memory_bytes: 4808
#include<stdio.h>

int main(void){
	int n,ans=100000;
	int i;
	
	scanf("%d",&n);
	for(i=0;i<n;i++){
		ans+=ans*0.05;
		if(ans%1000!=0)
			ans=(ans/1000+1)*1000;
	}
	printf("%d\n",ans);
	
	return 0;
}

Measured memory_bytes: 0
from operator import itemgetter
n,m = map(int,input().split())
*a,= map(int,input().split())
l = [tuple(map(int,input().split()))for _ in range(m)]
a.sort()
l.sort(key = itemgetter(1), reverse = True)
cmp = []
cnt = 0
for b,c in l:
	cmp += [c]*b
	cnt += b
	if cnt >= n:
		cnt = n
		break
cut = cnt
for i,(x,y) in enumerate(zip(a,cmp[:min(n,cnt+1)])):
	if x > y:
		cut = i
		break
print(sum(cmp[:cut] + a[cut:]))

Measured memory_bytes: 23284
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i] and is_prime[(i+1)//2]]


d = primes(100000)
cumsum = [0]
for i in range(1, 100001):
    if i in d:
        cumsum.append(cumsum[-1] + 1)
    else:
        cumsum.append(cumsum[-1])

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(cumsum[r] - cumsum[l-1])

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

int main(){

int x, y;
  cin >> x >> y;
  for (int i = 0; i <= x; i++) {
    if (i * 2 + (x - i) * 4 == y) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  
  return 0;
}


Measured memory_bytes: 3644
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inl = lambda: [int(x) for x in sys.stdin.readline().split()]
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))


def solve():
    n, k = inl()
    s = list(ins())
    s[k - 1] = s[k - 1].lower()
    return "".join(s)


print(solve())


Measured memory_bytes: 9188
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
for i in range(1, 10):
	if 100*i + 10*i + i >= N:
		print(100*i + 10*i + i)
		exit()

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

int main(void)
{
 int a,b,w;
 cin>>w>>a>>b;
 if(a+w<b){
	 cout<<b-w-a<<endl;}
 else if(b<=a+w&&a+w<=b+w){
	 cout<<0<<endl;
 }
 else if(b+w<a){
	 cout<<a-w-b<<endl;
 }
 else{
	 cout<<0<<endl;
 }
}


Measured memory_bytes: 256
//written by libra9z
#define LOCAL_TIME
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> pii;
typedef pair <ll,int> plli;
typedef pair <int,pii> pipii;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <vi> vvi;
typedef vector <pii> vpii;
typedef vector <vector<int> > mat;
#define rep(i,n) for (int i=0;i<(n);i++)
#define Rep(i,a,b) for (int i=(a);i<=(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rRep(i,a,b) for (int i=(a);i>=b;i--)
#define repit(it,a) for ((__typeof(a.begin())) it=a.begin();it!=a.end();it++)
#define repx(x,a) for (auto x:a)
#define pb push_back
#define mp make_pair()
#define eb emplace_back
#define X first
#define Y second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Debug(x) cerr<<#x<<" = "<<x<<endl
#define Debug22(x,y) cerr<<#x<<" = "<<x<<" , "<<#y<<" = "<<y<<endl
#define Debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")\n"
#define Debug3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<")\n"
#define Debug_arr(v,n) for(int i=0;i<n;++i) cerr<<#v<<"["<<i<<"]"<<" = "<<v[i]<<endl
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define prl cerr << "called: " << __LINE__ << endl
#define get1(x,a) x>>a
#define get2(x,a,b) x>>a>>b
#define get3(x,a,b,c) x>>a>>b>>c
#define getn(x,n,v) rep(i,n) x>>v[i]
#define put1(x,a) x<<a
#define put2(x,a,b) x<<a<<" "<<b
#define put3(x,a,b,c) x<<a<<" "<<b<<" "<<c
#define putn(x,n,v) rep(i,n) x<<v[i]<<" ";
#define eaq(n,x) __typeof(x) n=x;
#define RET(p,x) return p<<x<<endl,0;
const ll h1=999999937;
const ll h2=1000000009;
const int inf=2e9;
const ll mod=1000000007;
const int dx[]={1,0,-1,0,1,0,-1,0};
const int dy[]={0,1,0,-1,1,0,-1,0};
const double pi=3.141592653589793;
const bool multitests=false,alotoftests=false;
ifstream fin("input.txt");ofstream fout("output.txt");
stringstream sinout;
int n,a,b;
bool solve(int __test)
{
	cin>>n;
	a=n/10;
	b=n%1000;
	if (a%111==0 || b%111==0) puts("Yes");
	else puts("No");
	return false;
}
signed main()
{
	int __tests,__test=1;
	(multitests==true)?((alotoftests==false)?scanf("%d",&__tests):__tests=inf):__tests=1;
	for (;(alotoftests==true && multitests==true)?(!solve(__test)):(__test<=__tests);++__test)
	{
		if (!(multitests==true && alotoftests==true))
		{
			solve(__test);
		}
	}
	#ifdef LOCAL_TIME
	eprintf("\n\nSystem Time : %d ms",clock());
	#endif
	fin.close();fout.close();
	return 0;
}


Measured memory_bytes: 256
from collections import deque

n = int(input())
L = []
li = ['3', '5', '7']
que = deque(li)
while que:
    num = que.popleft()
    for i in range(3):
        nn = num + li[i]
        L.append(nn)
        if int(nn) < 10 ** 9:
            que.append(nn)
ans = 0
for num in L:
    if int(num) > n:
        break
    elif all(i in num for i in li):
        ans += 1
print(ans)


Measured memory_bytes: 9844
# -*- coding:utf-8 -*-
import numpy as np

n = int(input())

lis = []
for i in range(40000):
    if i**2 <= 1000000000:    
        lis.append(i**2)

np_lis = np.array(lis)

ans = np_lis[np_lis <= n]

print(ans[-1])



Measured memory_bytes: 13856
//#include <bits/stdc++.h>
#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;
typedef vector<int> VI;
typedef vector<VI> VVI;//例: VVI dp(10, vector<int>(10, INF);
typedef priority_queue<int, vector<int>, less<int> > QUE_int;
const int INF = 2 * pow(10, 9) + 1;//+1しないとREになるかも(out of rangeになるんかな?? )

vector<int> dx = { -1, 0, 1, 0, -1, -1, 1, 1 };
vector<int> dy = { 0, -1, 0, 1, -1, 1, -1, 1 };

int main(void) {
	int N, K;
	cin >> N >> K;

	vector<double> p(N);
	for (int i = 0; i < N; i++) {
		cin >> p[i];

	}

	//sort(p.begin(), p.end(), std::greater<int>());
	//for (int i = 0; i < N; i++) cout << p[i] << " " << endl;
	//cout << endl;

	int sum = 0;
	int index = 0;
	for (int i = 0; i < K; i++) {
		sum += p[i];
	}

	int sum_tmp = sum;
	for (int i = K; i < N; i++) {
		 sum_tmp = sum_tmp + p[i] - p[i - K];
		
		//cout << "i: " << i <<" p[i]: "<< p[i] << " p[i-K]: " << p[i-K] <<  " sum: " << sum << " sum_tmp: " << sum_tmp << endl;
		if (sum_tmp > sum) {
			index = i - K + 1;
			sum = sum_tmp;

		}

	}


	double ans = 0;
	for (int i = index; i < index + K; i++) {
		ans += p[i] * (p[i] + 1) / 2 / p[i];
		//cout << p[i] << endl;
	}

	cout << fixed;//小数点を確実に8桁で表示するためのもの
	cout << setprecision(8) << ans << endl;

}



Measured memory_bytes: 1792
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m, k, a;
    scanf("%d%d", &n, &m);
    vector<int> d(m + 1);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &k);
        for (int j = 0; j < k; ++j) {
            scanf("%d", &a);
            ++d.at(a);
        }
    }
    printf("%d\n", count(d.begin() + 1, d.end(), n));
    return 0;
}


Measured memory_bytes: 256
n = int(input())

import math
m = math.floor(n**0.5)

for i in range(m,0,-1):
    if n % i ==0:
        ii = math.floor(math.log(i,10))+1
        ij = math.floor(math.log(n//i,10))+1
        print(max(ii,ij))
        exit()

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		if((A % 2 != 0) && (B % 2 != 0)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
        int n;
        cin>>n;
        vector<int> mons(n+1);
        vector<int> hero(n);
        
        for(int i=0;i<n+1;i++) cin>>mons[i];
        for(int i=0;i<n;i++) cin>>hero[i];
        
        long long ans=0;
        
        for(int i=0;i<n;i++){
            if(mons[i]>=hero[i]){
                ans+=hero[i];
            }else{
                ans+=mons[i];
                hero[i]-=mons[i];
                //第二ラウンド
                if(mons[i+1]>=hero[i]){
                    ans+=hero[i];
                    mons[i+1]-=hero[i];
                }else{
                    ans+=mons[i+1];
                    mons[i+1]=0;
                }
                
            }
        }
        
        cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <map>
#define REP(i, a, n) for(int i = (a); i < (n); i++)
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

struct dice { int f, l, b, r, t, d; };
int N, T, F;
const int dd[5] = { 0, 1, 0, -1, 0 };

void init(dice &m, int t, int f) {
  int l[7][7] = {
    { 0, 0, 0, 0, 0, 0, 0, },
    { 0, 0, 4, 2, 5, 3, 0, },
    { 0, 3, 0, 6, 1, 0, 4, },
    { 0, 5, 1, 0, 0, 6, 2, },
    { 0, 2, 6, 0, 0, 1, 5, },
    { 0, 4, 0, 1, 6, 0, 3, },
    { 0, 0, 3, 5, 2, 4, 0, },
  };
  m.t = t; m.f = f; m.l = l[t][f]; m.d = 7 - m.t; m.b = 7 - m.f; m.r = 7 - m.l;
}

int number(dice &m, int k) {
  switch(k) {
    case 0: return m.f;
    case 1: return m.l;
    case 2: return m.b;
    case 3: return m.r;
    case 4: return m.t;
    case 5: return m.d;
  }
  return -1;
}

void roll(dice &m, int k) {
  int tmp;
  switch(k) {
    case 0: tmp = m.f; m.f = m.t; m.t = m.b; m.b = m.d; m.d = tmp; break;
    case 1: tmp = m.l; m.l = m.t; m.t = m.r; m.r = m.d; m.d = tmp; break;
    case 2: tmp = m.b; m.b = m.t; m.t = m.f; m.f = m.d; m.d = tmp; break;
    case 3: tmp = m.r; m.r = m.t; m.t = m.l; m.l = m.d; m.d = tmp; break;
  }
}

int rolldir(map<pii, pii> &v, dice &m, pii p) {
  int dir = -1, n = -1;
  REP(i, 0, 4) {
    pii np = pii(p.fi + dd[i], p.se + dd[i + 1]);
    if(v[np].se < v[p].se && number(m, i) > max(3, n)) {
      n = number(m, i);
      dir = i;
    }
  }
  return dir;
}

int main(void) {
  while(cin >> N, N) {
    map<pii, pii> v;
    REP(i, 0, N) {
      cin >> T >> F;
      int dir;
      pii p = pii(0, 0);
      dice m;
      init(m, T, F);
      while((dir = rolldir(v, m, p)) != -1) {
        p = pii(p.fi + dd[dir], p.se + dd[dir + 1]);
        roll(m, dir);
      }
      v[p] = pii(number(m, 4), v[p].se + 1);
    }
    int ans[7] = { 0, 0, 0, 0, 0, 0 };
    for(auto it = v.begin(); it != v.end(); it++) ans[it->se.fi]++;
    REP(i, 1, 7) {
      cout << ans[i];
      if(i != 6) cout << " ";
      else cout << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3072
#include<stdio.h>
int main(){
	
	int takasa[10],no[10],yama,i,j;
	for(i=0;i<10;i++){
		scanf("%d",&takasa[i]);
	}
	
	for(i=0;i<10;i++){
		for(j=0;j<10;j++){
			if(takasa[i]<takasa[j]){
				yama=takasa[i];
				takasa[i]=takasa[j];
				takasa[j]=yama;
			}
		}
	}
	no[0]=takasa[9];
	no[1]=takasa[8];
	no[2]=takasa[7];
	
	for(i=0;i<3;i++){
		printf("%d\n",no[i]);
	}	
		
							
	return 0;
}

Measured memory_bytes: 600
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 505
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fll
int n, A[N][N];
ll sum1[N][N], sum2[N][N], f[N][N];
ll Getsum1(int La, int Ra, int Lb, int Rb)
{
	if (La > Ra || Lb > Rb)return 0;
	return sum1[Ra][Rb] - sum1[Ra][Lb - 1] - sum1[La - 1][Rb] + sum1[La - 1][Lb - 1];
}
ll Getsum2(int La,int Ra,int Lb,int Rb)
{
	if (La > Ra || Lb > Rb)return 0;
	return sum2[Ra][Rb] - sum2[Ra][Lb - 1] - sum2[La - 1][Rb] + sum2[La - 1][Lb - 1];
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i != j)
				scanf("%d", &A[i][j]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			sum1[i][j] = sum1[i - 1][j] + sum1[i][j - 1] - sum1[i - 1][j - 1] + (i > j ? A[i][j] : 0);
			sum2[i][j] = sum2[i - 1][j] + sum2[i][j - 1] - sum2[i - 1][j - 1] + (i < j ? A[i][j] : 0);
		}
	n++;
	memset(f, 0x3f, sizeof(f));
	ll ans = inf;
	f[0][0] = 0;
	for (int i = 1; i < n; i++)
		for (int j = 0; j < i; j++)
		{
			for (int k = 0; k <= j; k++)
				f[i][j] = min(f[i][j], f[j][k] + Getsum1(i + 1, n - 1, k + 1, j) + Getsum2(j + 1, i, j + 1, i));
			if (i == n - 1)
				ans = min(ans, f[i][j]);
		}
	printf("%lld\n", ans);
}


Measured memory_bytes: 7296
# -*- coding: utf-8 -*-
n = int(input())
al = list(map(int, input().split()))
MOD = 10**9 + 7

# aのmod Mでの逆元
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t*v
        u,v = v,u
    u %= m
    if u<0:
        u += m
    return u

# GCD
def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def lcm(a,b):
    return a*b//gcd(a,b)

def lcmlist(l):
    res = l[0]
    for x in l[1:]:
        res = lcm(res, x)
    return res

l = lcmlist(al)%MOD
res = 0
for a in al:
    res += l*modinv(a,MOD)
    res %= MOD

print(res)

Measured memory_bytes: 42588
N, M = map(int, input().split())
SC = [list(map(int, input().split())) for _ in range(M)]

start = 10 ** (N - 1) if N != 1 else 0

for i in range(start, 10 ** N):
    flag = 1
    si = str(i)
    for s, c in SC:
        if si[s - 1] != str(c):
            flag = 0
            break
    if flag:
        print(i)
        exit()
print(-1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
using pp=pair<int,pair<int,int>>;
#define MAX 200003
#define MOD 1000000007
#define INF 1000000000000000000

int D;
vector<ll> c(26);
vector<vector<ll>> s;

ll calc_score(vector<int> t){
  vector<ll> last(26,0);
  ll ans=0;
  for(ll i=0;i<D;i++){
    ans+=s.at(i).at(t.at(i));
    last.at(t.at(i))=i+1;
    for(ll j=0;j<26;j++){
      ans-=c.at(j)*((i+1)-last.at(j));
    }
  }
  return ans;
}


int main(){
  cin>>D;
  for(int i=0;i<26;i++){
    cin>>c.at(i);
  }
  s.resize(D);
  for(int i=0;i<D;i++){
    s.at(i).resize(26);
    for(int j=0;j<26;j++){
      cin>>s.at(i).at(j);
    }
  }

  vector<int> t(D,1);
  ll max_score=calc_score(t);
  for(ll k=0;k<26;k++){
    ll score=0;
    vector<int> nt(D,0);
    vector<int> last(26,0);
    for(ll i=0;i<D;i++){
      int l=0;
      for(int j=0;j<26;j++){
        ll kk=min<ll>(D,i+1+k);
        if(s.at(i).at(j)+c.at(j)*(kk-i)*((i+1)-last.at(j))>s.at(i).at(l)+c.at(l)*(kk-i)*((i+1)-last.at(l))){
          l=j;
        }
      }
      last.at(l)=i+1;
      nt.at(i)=l;
    }
    score=calc_score(nt);
    if(score>max_score){
      max_score=score;
      t=nt;
    }
  }

  for(int i=0;i<D;i++){
    cout<<t.at(i)+1<<endl;
  }


}


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

int main(){
    int N,M;  cin >> N;
    vector<string> S;
    vector<int> scount;

    string s;
    cin >> s;
    S.push_back(s);
    scount.push_back(1);


    for(int i = 0;i < N - 1;i++){
      cin >> s;
      if(find(S.begin(),S.end(),s) == S.end()){//入力した文字列がSに入っていないとき
        S.push_back(s);//文字列の追加.
        scount.push_back(1);
      }
      else{
        scount[find(S.begin(),S.end(),s)-S.begin()]++;//カウントを+1する.
      }
    }

    vector<string> T;
    vector<int> tcount;

    cin >> M;

    string t;
    cin >> t;
    T.push_back(t);
    tcount.push_back(1);
    for(int j = 0;j < M-1;j++){
      cin >> t;
      if(find(T.begin(),T.end(),t) == T.end()){//入力した文字列がTに入っていないとき
        T.push_back(t);
        tcount.push_back(1);
      }
      else{
        tcount[find(T.begin(),T.end(),t) - T.begin()]++;//カウントを+1する.
      }
    }

    int max = -10000;
    int l;
    for(int i = 0;i < S.size();i++){
      if(find(T.begin(),T.end(),S[i]) != T.end()){//S[i]がTに含まれるとき
          l = scount[i] - tcount[find(T.begin(),T.end(),S[i]) - T.begin()];//差額
          if(max < l)max = l;
      }
      else{
        if(scount[i] > max)max = scount[i];
      }
    }

    if(max < 0)cout << 0 << endl;
    else cout << max << endl;


}

Measured memory_bytes: 256
import sys
readline = sys.stdin.buffer.readline

import numpy as np

n = int(readline())
a = np.array(readline().split(), np.int64)

ai = np.argsort(a)[::-1]
a = a[ai]
ai += 1

dp = np.zeros(1, np.int64)
for k, (i, e) in enumerate(zip(ai, a), 1):
    dp_new = np.append(dp, 0)

    add_left = e * np.abs(np.arange(1, k + 1) - i)
    np.maximum(dp_new[1:k+1], dp[:k] + add_left, out=dp_new[1:k+1])

    add_right = e * np.abs(np.arange(n - k + 1, n + 1) - i)
    np.maximum(dp_new[:k], dp[:k] + add_right, out=dp_new[:k])

    dp = dp_new

ans = dp.max()
print(ans)


Measured memory_bytes: 27840
n = int(input())
h = list(map(int, input().split()))
dp = [0] * n
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for k in range(2, n):
	dp[k] = min(dp[k - 1] + abs(h[k] - h[k - 1]), dp[k - 2] + abs(h[k] - h[k - 2]))
print(dp[-1])

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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

template<typename T>
T vec_sum(V<T> v, T init_val=0){return accumulate(ALL(v),T(init_val));}

template<typename T>
T vec_max(V<T> v){return *max_element(ALL(v));}

int main(){
    int n;
    cin>>n;
    Vi p(n);
    REP(i,n){
        cin>>p[i];
    }

    cout<<vec_sum(p)-vec_max(p)/2<<endl;
}

Measured memory_bytes: 256
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N = int(input())
    A = list(map(int, input().split()))
    a = sorted(A, reverse=1)
    res1 = 0
    res2 = []
    for i in range(N-3):
        if a[i]==a[i+1]==a[i+2]==a[i+3]:
            res1 = a[i]
            break
    for i in range(N-1):
        if a[i]==a[i+1] and not a[i] in res2:
            res2.append(a[i])
        if len(res2)==2:
            break
    if len(res2)<2:
        print(res1**2)
    else:
        print(max(res1**2, res2[0]*res2[1]))



if __name__ == '__main__':
    main()

Measured memory_bytes: 14756
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int n;
    string s;
    cin>>n>>s;
    int ans=0;
    rep(i,n){
        if(s[i]=='.')ans++;
    }
    int t=0;
    rep(i,n){
        if(s[i]=='#')t++;
    }
    ans=min(ans,t);
    t=0;
    vi a(n),b(n);
    rep(i,n){
        if(s[i]=='#')a[i]++;
        else b[i]++;
    }
    rep(i,n-1)a[i+1]+=a[i],b[i+1]+=b[i];
    rep(i,n){
        ans=min(ans,a[i]+b[n-1]-b[i]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3732
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000


int main(){
	int a[N];
	f(i, N)a[i] = 0;
	int n, k;
	int x, m;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &x);
		a[x - 1] = i;
	}
	m = 1;
	k = 1;
	for (int i = 1; i < n; i++){
		if (a[i - 1] < a[i])k++;
		else{
			m = max(m, k);
			k = 1;
		}
	}
	m = max(m, k);

	printf("%d\n", (n - m));


	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 1000000000
#define InfLL 1000000000000000000LL
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=(n-1);(i)>=(0);(i)--)
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

int main() {

	string S, ans;
	cin >> S;
	ans = (S == "ABC") ? "ARC" : "ABC";

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

Measured memory_bytes: 3624