akhauriyash/Code-Regression huggingface dataset:
n, c = [int(i) for i in input().split(" ")]
x = [0] * (n + 1)
v = [0] * (n + 1)

for i in range(1, n + 1):
    x[i], v[i] = [int(i) for i in input().split(" ")]

def s(x, v):
    #print(x, v)
    sum_v = [0] * (n + 1)
    for i in range(1, n + 1):
        sum_v[i] = sum_v[i - 1] + v[i]
    v_sub = [sum_v[i] - x[i] for i in range(0, n + 1)]
    max_v = [0] * (n + 1)
    for i in range(1, n + 1):
        max_v[i] = max(max_v[i - 1], v_sub[i])
    #print(max_v)
    
    sum_r = v[n]
    max_v_sub = max_v[n]
    for i in range(1, n // 2 + 1):
        v_sub = sum_r - (c - x[n - i + 1]) * 2 + max_v[n - i]
        #print(v_sub, i)
        if v_sub > max_v_sub:
            max_v_sub = v_sub
        sum_r += v[n - i]
    return max_v_sub
        
print(max(s(x, v), s([0] + [c - xi for xi in x[1::]][::-1], [0] + v[1::][::-1])))

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

int distance(vector<int> a, vector<int> b) {
  int dist = 0;
  for(int i=0; i<a.size(); i++) {
    dist += (a.at(i) - b.at(i)) * (a.at(i) - b.at(i));
  }
  return dist;
}

int main() {
  int n, d;
  cin >> n >> d;
  vector<vector<int>> x(n,vector<int>(d));
  for(int i=0; i<n; i++) {
    for(int j=0; j<d; j++)
      cin >> x.at(i).at(j);
  }
  
  int count = 0;
  
  for(int i=0; i<n-1; i++) {
    for(int j=i+1; j<n; j++) {
      int l = distance(x.at(i), x.at(j));
      for(int k=1; k*k<=l; k++) {
        if(k*k == l)
          count++;
      }
    }
  }
  
  cout << count << endl;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;
class Main{
	public static void main(String[] args)throws NumberFormatException, IOException{
		Scanner scan = new Scanner(System.in);
		String textString = scan.next();
		char[] text = textString.toCharArray();
		int decreeTimes = scan.nextInt();
		int A = 0;
		int B = 0;
		String replaceText =  "";
		String answer = "";

		for (int i=0; i<decreeTimes; i++){
			String decree = scan.next();
			A = scan.nextInt();
			B = scan.nextInt();
			if(decree.equals("replace")){
				replaceText = scan.next();
				for(int j=0; j<(B-A+1); j++){
					text[A+j] = replaceText.charAt(j);
				}
			}
			else if(decree.equals("reverse")){
				char[] temp = (char[])text.clone();
				for(int j=0; j<B-A+1; j++){
					text[B-j] = temp[j+A];
				}
			}
			else if(decree.equals("print")){
				answer = "";
				for(int j=A; j<B+1; j++){
					answer = answer + text[j];
				}
				System.out.println(answer);
			}
		}
	}
}

Measured memory_bytes: 45568
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> pa;
int main(){
	int n,i,a,sum=0,d=1;
	cin >> n;
	for(i=0;i<n;i++){
		cin >> a;
		pa.push(a);
	}
	while(!pa.empty()){
		sum+=d*pa.top();
		pa.pop();
		d=-d;
	}
	cout << sum << endl;
	return 0;
}


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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    ll n,m; cin >> n >> m;
    vb be(n),en(n);
    rep(i,m){
        int a,b; cin>> a>>b;
        a--;b--;
        if(a==0)be[b]=1;
        else if(b==n-1)en[a]=1;
    }
    rep(i,n)if(be[i] && en[i]){
        out("POSSIBLE");
        return 0;
    }
    out("IMPOSSIBLE");
}


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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  while(true){
    C-=B;
    if(C<=0){
      cout << "Yes" << endl;
      break;}
    A-=D;
    if(A<=0){
      cout << "No" << endl;
      break;}
  }
 }

Measured memory_bytes: 3624
/****************************
*  Developer : joshi08
*  Date  :  22-06-2020
*  Year  :  2020
****************************/

#include <bits/stdc++.h>

#define lli long long int
#define mod 1000000007
#define fi first
#define se second
#define ii pair<lli, lli>
#define mp make_pair
#define endl '\n'
const double PI = 3.141592653589793238460;
lli gcd(lli a, lli b) { if (a == 0) return b; return gcd(b % a, a);}
lli max(lli a, lli b) {if (a > b) return a; else return b;}
lli min(lli a, lli b) {if (a < b) return a; else return b;}
lli power(lli a,lli b) {lli i,p=1; for(i=0;i<b;i++){p*=a;} return p;}

using namespace std;

int main()
{
    ios::sync_with_stdio(false);

	string s;
	cin>>s;
	lli q,counter=0;
	cin>>q;
	
	while(q--)
	{
		lli n,f;
		char c;
		cin>>n;
		
		if(n==1)
		{
			counter++;
		}
		else
		{
			cin>>f>>c;
			if(counter%2==0)
			{
				if(f==1)
				{
					string sn;
					sn += c;
					sn += s;
					s = sn;
				}
				else
				if(f==2)
				{
					s += c;
				}
			}
			else
			{
				if(f==2)
				{
					string sn;
					sn += c;
					sn += s;
					s = sn;
				}
				else
				if(f==1)
				{
					s += c;
				}
			}
		}
		//cout<<s<<endl;
	}
	
	if(counter%2!=0)
	{
		reverse(s.begin(),s.end());
	}
	
	cout<<s;

    return 0;
}



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

int getSum(int n){
	int sum=0;
	while(n>0){
		sum+=n%10;
		n/=10;
	}
	return sum;
}

int main(){
	int N;
	cin>>N;
	
	int min=getSum(1)+getSum(N-1);
	
	int sum;
	for(int i=1;i<N;i++){
		int j=N-i;
		sum=getSum(i)+getSum(j);
		if(min>sum)
			min=sum;
	}
	cout<<min<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
int ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{ return firstElof.second < secondElof.second; }
//**Snippetリスト**//
//rep, vin, all//
//gcdlcm, isPrime, eratos, modinv, bitSearch, dfs, bfs, dijkstra, UnionFind, COM, digitDP//
ll i, j, k, l, m, n; ll N, M, K, H, W, L; 
ll MOD = 1000000007; ll INF = 9999999999999; ll ans = 1;
vl flag, color; vll path; vl D;
//***********//
int main() {
	long double L;
	cin >> L;
	long double p = 3;
	long double x = L / p;
	cout << fixed << setprecision(12) << x * x * x;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
 
using namespace std;
 
int main(){
    int a[10] = {0};
    for(int i = 0; i < 10; i++){
        cin >> a[i];
    }
    sort(a, a + 10);
    for(int i = 9; i > 6; i--){
        cout << a[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define INF 11451400


/*
int main(){
	while(true){
		int lineL, statL;
		cin >> lineL >> statL;
		if(lineL==0&&statL==0){return 0;}

		long leastCosts[statL][statL];
		long leastTimes[statL][statL];
		FOR(aStat,0,statL){
			FOR(bStat,0,statL){
				leastCosts[aStat][bStat] = leastTimes[aStat][bStat] = (aStat==bStat)?0:INF;
			}
		}

		REP(lineI,lineL){
			int naStat,nbStat,nCost,nTime;
			cin >> naStat >> nbStat >> nCost >> nTime;
			naStat -=1; nbStat -=1;
			FOR(aStat,0,statL){
				FOR(bStat,0,statL){
					leastCosts[aStat][bStat] = min(leastCosts[aStat][bStat] , leastCosts[aStat][naStat]+nCost+leastCosts[nbStat][bStat]);
					leastCosts[aStat][bStat] = min(leastCosts[aStat][bStat] , leastCosts[aStat][nbStat]+nCost+leastCosts[naStat][bStat]);
					leastTimes[aStat][bStat] = min(leastTimes[aStat][bStat] , leastTimes[aStat][naStat]+nTime+leastTimes[nbStat][bStat]);
					leastTimes[aStat][bStat] = min(leastTimes[aStat][bStat] , leastTimes[aStat][nbStat]+nTime+leastTimes[naStat][bStat]);
				}
			}
		}

		int reqL;
		cin >> reqL;
		REP(reqI,reqL){
			int aStat,bStat,costOrTime;
			cin >> aStat >> bStat >> costOrTime;
			aStat-=1;bStat-=1;
			if(costOrTime==0){cout<<leastCosts[aStat][bStat]<<endl;};
			if(costOrTime==1){cout<<leastTimes[aStat][bStat]<<endl;};
		}
	}
}
*/

int main(){
	while(true){
		int lineL, statL;
		cin >> lineL >> statL;
		if(lineL==0&&statL==0){return 0;}

		long leastCosts[statL][statL];
		long leastTimes[statL][statL];
		FOR(aStat,0,statL){
			FOR(bStat,0,statL){
				leastCosts[aStat][bStat] = leastTimes[aStat][bStat] = (aStat==bStat)?0:INF;
			}
		}

		REP(lineI,lineL){
			int naStat,nbStat,nCost,nTime;
			cin >> naStat >> nbStat >> nCost >> nTime;
			naStat -=1; nbStat -=1;
			leastCosts[naStat][nbStat] = leastCosts[nbStat][naStat] = nCost;
			leastTimes[naStat][nbStat] = leastTimes[nbStat][naStat] = nTime;
		}

		REP(k,statL) REP(i,statL) REP(j,statL) {
			leastCosts[i][j] = min(leastCosts[i][j] , leastCosts[i][k]+leastCosts[k][j]);
			leastTimes[i][j] = min(leastTimes[i][j] , leastTimes[i][k]+leastTimes[k][j]);
		}

		int reqL;
		cin >> reqL;
		REP(reqI,reqL){
			int aStat,bStat,costOrTime;
			cin >> aStat >> bStat >> costOrTime;
			aStat-=1;bStat-=1;
			if(costOrTime==0){cout<<leastCosts[aStat][bStat]<<endl;};
			if(costOrTime==1){cout<<leastTimes[aStat][bStat]<<endl;};
		}
	}
}

Measured memory_bytes: 1316
#include <bits/stdc++.h>
using namespace std;
template<typename T> struct Dinitz{
	int n, source, sink;
	vector<vector<T>> adj;
	struct edge {
		int u;
		T flow, cap;
	};
	vector<edge> edges;
	Dinitz(int n, int source, int sink): n(n), source(source), sink(sink), adj(n) {}
	int add_edge(int a, int b, T abcap, T bacap = 0) {
		int result = edges.size();
		adj[a].push_back(edges.size());
		edges.push_back({b, 0, abcap});
		adj[b].push_back(edges.size());
		edges.push_back({a, 0, bacap});
		return result;
	}
	vector<int> mindist, position;
	bool bfs() {
		queue<int> q;
		fill(mindist.begin(), mindist.end(), INT_MAX / 2);
		mindist[source] = 0;
		q.push(source);
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (int edid: adj[v]) {
				edge &ed = edges[edid];
				if (ed.flow < ed.cap && mindist[ed.u] > mindist[v] + 1) {
					mindist[ed.u] = mindist[v] + 1;
					q.push(ed.u);
				}
			}
		}
		return mindist[sink] < n;
	}
	T dfs(int v, T maxf) {
		if (v == sink) return maxf;
		for (int &pos = position[v]; pos < (int)adj[v].size(); ++pos) {
			int edid = adj[v][pos];
			edge &ed = edges[edid], &reved = edges[edid ^ 1];
			if (ed.flow < ed.cap && mindist[ed.u] == mindist[v] + 1) {
				T f = dfs(ed.u, min(maxf, ed.cap - ed.flow));
				if (f > 0) {
					ed.flow += f;
					reved.flow -= f;
					return f;
				}
			}
		}
		return 0;
	}
	T maxflow() {
		T result = 0;
		mindist.resize(n);
		position.resize(n);
		while (bfs()) {
			T extra;
			do {
				fill(position.begin(), position.end(), 0);
				extra = dfs(source, numeric_limits<T> :: max());
				result += extra;
			} while (extra > 0);
		}
		return result;
	}
};
const int maxn = 111;
char g[maxn][maxn];
int cn, nd[2][maxn][maxn], row[maxn], col[maxn];
int main(){
	int n, m; cin >> n >> m;
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> g[i][j];
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) nd[0][i][j] = cn++, nd[1][i][j] = cn++;
	for(int i = 0; i < n; i++) row[i] = cn++;
	for(int i = 0; i < m; i++) col[i] = cn++;
	int S = cn++, T = cn++;
	Dinitz<int> flow(cn, S, T);
	const int inf = 11111;
	for(int i = 0; i < n; i++) {
		int pc = 0;
		for(int j = 0; j < m; j++) if(g[i][j] == 'S' || g[i][j] == 'T') pc++;
		if(pc == 2) return cout << -1 << endl, 0;
	}
	for(int j = 0; j < m; j++) {
		int pc = 0;
		for(int i = 0; i < n; i++) if(g[i][j] == 'S' || g[i][j] == 'T') pc++;
		if(pc == 2) return cout << -1 << endl, 0;
	}
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
		if(g[i][j] != '.'){
			if(g[i][j] == 'S'){
				flow.add_edge(S, nd[0][i][j], inf);
				flow.add_edge(nd[0][i][j], nd[1][i][j], inf);
			} else if(g[i][j] == 'T'){
				flow.add_edge(nd[1][i][j], T, inf);
				flow.add_edge(nd[0][i][j], nd[1][i][j], inf);
			} else {
				flow.add_edge(nd[0][i][j], nd[1][i][j], 1);
			}
			flow.add_edge(row[i], nd[0][i][j], inf);
			flow.add_edge(nd[1][i][j], row[i], inf);
			flow.add_edge(col[j], nd[0][i][j], inf);
			flow.add_edge(nd[1][i][j], col[j], inf);
		}
	}
	int x = flow.maxflow();
	if(x > n + m - 2) cout << -1 << endl;
	else cout << x << endl;
	return 0;
}


Measured memory_bytes: 3000
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

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

  int n, k;
  cin >> n >> k;
  vector<int> p(n);
  for (auto &x: p) cin >> x;

  vector<double> p_sum(n+1);
  for (int i = 0; i < n; i++) p_sum[i+1] = p_sum[i] + (double) (p[i] - 1) / 2.0 + 1.0;

  double maximum = 0;
  for (int i = 0; i < n - k + 1; i++) {
    if (p_sum[i+k] - p_sum[i] > maximum) maximum = p_sum[i+k] - p_sum[i];
  }

  cout << setprecision(16) << maximum << endl;

  return 0;
}


Measured memory_bytes: 2560
/*
ID: dorijan1
TASK: tu napisi ime zadatka molim te molim te ali samo ako si na usaco training
LANG: C++11
*/
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define rand rund
#define pb push_back

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
const int MOD=1000000007;
const int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w)
{
	cout<<w.size()<<endl;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<endl;
}

ll raand()
{
	ll a=rand();
	a*=RAND_MAX;
	a+=rand();
    return a;
}

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=10;
		k+=a[i]-'0';
	}
	return k;
}

string its(ll k)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%10)+'0');
		k/=10;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

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

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

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

int sub(int a,int b)
{
	return (a-b+MOD)%MOD;
}

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

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

ll has(string x)
{
	ll h1=0,h2=0;
	x=to_lower(x);
	for (char a: x)
	{
		h1*=bases[0];
		h1+=a-'a';
		h1%=bases[3];
		h2*=bases[1];
		h2+=a-'a';
		h2%=bases[4];
	}
	return h1*(MOD+13893829)+h2;
}

const int N=300010;
int n,dp[N],h[N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back(raand()%MOD+13893829);
	cin>>n;
	for (int i=1;i<n;++i) dp[i]=MOD;
	for (int i=0;i<n;++i)
	{
		cin>>h[i];
	}
	for (int i=0;i<n-1;++i)
	{
		dp[i+1]=min(dp[i+1],dp[i]+abs(h[i]-h[i+1]));
		dp[i+2]=min(dp[i+2],dp[i]+abs(h[i]-h[i+2]));
	}
	cout<<dp[n-1];
}



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

int main()
{

    string S;
    cin >> S;
    int strlen = S.size();
    int end = S.size() / 2;
    int answer = 0;
    for (int i = 0; i < end; i++)
    {
        if(S[i] != S[strlen - 1 - i]){
            answer++;
        }
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
        int p, q, r;
        scanf("%d %d %d", &p, &q, &r);
        if (p >= q && p >= r) {
                printf("%d\n", q + r);
        }
        else if (q >= p && q >= r) {
                printf("%d\n", p + r);
        }
        else if (r >= p && r >= q) {
                printf("%d\n", p + q);
        }
        return 0;
}


Measured memory_bytes: 128
#pragma region Macros
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())
#define IN(x, a, b) x >= a and x < b

using namespace std;
using ll = long long;

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;
}
template <typename T> constexpr T INF = numeric_limits<T>::max() / 2;
#pragma endregion

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

  int N;
  cin >> N;
  vector<int> L(N);
  REP(i, N) { cin >> L[i]; }
  sort(ALL(L));
  int ans = 0;
  REP(i, N - 2) {
    FOR(j, i + 1, N - 1) {
      int k = L[i] + L[j];
      int ok = j;
      int ng = N;
      while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (L[mid] < k) {
          ok = mid;
        } else {
          ng = mid;
        }
      }
      ans += ok - j;
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
package main

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

const size = 1000000
var reader = bufio.NewReaderSize(os.Stdin,size)
func NextLine() string {
  var line,buffer []byte
  var isPrefix bool = true
  var err error
  for ;isPrefix; {
    line,isPrefix,err = reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
  }
  return string(buffer)
}
func NextInt() int {
  var n int
  n,_ = strconv.Atoi(NextLine())
  return n
}

func main() {
  var n int = NextInt()
  var s []string = strings.Split(NextLine()," ")
  var a int
  var m []int = []int{0,0,0}
  for i:=0;i<n;i++ {
    a,_ = strconv.Atoi(s[i])
    switch a%4 {
      case 0 : m[2]++
      case 2 : m[1]++
      default: m[0]++
    }
  }
  if m[1] == 0 && m[2] >= m[0]-1  {
    fmt.Println("Yes")
  } else if m[1] != 0 && m[2] >= m[0] {
    fmt.Println("Yes")
  } else {
    fmt.Println("No")
  }
}

Measured memory_bytes: 5248
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma warning(disable:4996)
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <set>
#include <map>
#include <iomanip> 
#include <ctime>
#include <numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const double PI = 3.14159265358979323846;
const int MAX = 1e10;
const int MOD = 1e9+7;

const int MAX_N = 100005;

P f(int x) {
	int a = x % 10;
	int b = 0;
	while (x) {
		b = x % 10;
		x /= 10;
	}
	return P(a, b);
}

int main(int argc, char *args[]) {
	int n; cin >> n;
	map<P, int> count;
	for (int i = 1; i <= n; i++) {
		P p = f(i);
		count[p]++;
	}
	ll ans = 0;
	for (int i = 0; i <= n; i++) {
		P p = f(i);
		P q(p.second, p.first);
		ans += count[q];
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
   int n,q,i;
   string s;
   std::cin >>n>>q ;
   std::cin >> s;
   int v[n];
   int count=0;
   int a,b;
   int ans;
   for (i=0;i<n-1;i++){
       if(s[i]=='A'&&s[i+1]=='C')count++;
       v[i]=count;
       //std::cout << v[i] << std::endl;
   }
   v[n]=v[n-1];
   for(i=0;i<q;i++){
       std::cin >> a>>b;
       ans=v[b-1]-v[a-1];
       std::cout << v[b-2]-v[a-2] << std::endl;
   }
}

Measured memory_bytes: 1408
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int a, b; readV(a, b);
  writeln(a.predSwitch!"a<=b"(5, 0, 12, b/2, b));
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

// char c[55][55];
int H, W, cnt;

int main() {
    cin >> H >> W;
    vector<vector<char>> c(H + 2, vector<char>(W + 2));
    for(int i = 1; i <= H; i++) {
        for(int j = 1; j <= W; j++)
            cin >> c[i][j];
    }
    for(int i = 1; i <= H; i++) {
        for(int j = 1; j <= W; j++) {
            if(c[i][j] == '#' && c[i][j - 1] != '#' && c[i - 1][j] != '#' &&
               c[i][j + 1] != '#' && c[i + 1][j] != '#')
                cnt++;
        }
    }
    // cout << "========================" << endl;
    // for(int i = 1; i <= H; i++) {
    //     for(int j = 1; j <= W; j++) {
    //         cout << c[i - 1][j] << '|';
    //     }
    //     cout << endl;
    // }
    if(cnt == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;

int main()
{
	string S;
	cin >> S;

	int32_t N = S.size();
	int32_t cntZero = 0;
	for (int32_t i = 0; i < N; i++)
		if (S[i] == '0')
			cntZero++;
	cout << min(cntZero, N - cntZero) * 2 << endl;

	return 0;
}


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

int main() {
 int w,a,b; cin >> w >> a >> b;
 int len1 = b - (w + a), len2 = a - (b + w);
 if (len1 > 0) {
  printf("%d\n" , len1);
 } else if (len2 > 0) {
  printf("%d" , len2);
 } else {
  puts("0");
 }
}

Measured memory_bytes: 3696
/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

int b[100][100];

int main(){
  int w, h, n, x, y, a;
  cin >> w >> h >> n;
  rep(n){
    cin >> x >> y >> a;
    if (a == 1) rep(xx, x) rep(yy, h) b[xx][yy] = 1;
    if (a == 2) rep(xx, x, w) rep(yy, h) b[xx][yy] = 1;
    if (a == 3) rep(xx, w) rep(yy, y) b[xx][yy] = 1;
    if (a == 4) rep(xx, w) rep(yy, y, h) b[xx][yy] = 1;
  }
  int s = w * h;
  rep(i, w) rep(j, h) s -= b[i][j];
  cout << s << endl;
}


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

using namespace std;
#define ALL(v) (v).begin(), (v).end()

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

  vector<int> X(N), Y(N);
  for (int i = 0; i < N; ++i) {
    cin >> X[i];
    Y[i] = X[i];
  }

  sort(ALL(Y));

  for (int i = 0; i < N; ++i) {
    if (X[i] < Y[N/2]) cout << Y[N/2] << endl;
    else cout << Y[N/2-1] << endl;
  }
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100001],b[100001];
priority_queue <int,vector<int>,greater<int> > q;
priority_queue <int> p;
main() {
	int m,ans=0,L,zz,js=0,res1=0,res2=0,tot1=0,tot2=0;
	cin>>m;
	for(int i=1; i<=m; i++) {
		cin>>L;
		if(L==2)
			(ans%2)?printf("%lld %lld\n",p.top(),(ans-ans/2)*p.top()-res2+res1-ans/2*p.top()+js):printf("%lld %lld\n",min(p.top(),q.top()),(ans/2)*min(p.top(),q.top())+res1-res2-(ans/2)*min(p.top(),q.top())+js);
		else {
			int hh;
			ans++;
			cin>>hh>>zz;
			js+=zz;
			q.push(hh);
			res1+=hh;
			p.push(q.top());
			res1-=q.top();
			res2+=q.top();
			q.pop();
			if(ans%2==0)
				res2-=p.top(),res1+=p.top(),q.push(p.top()),p.pop();
//			cout<<res1<<res2<<js<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3828
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


N = int(input())
S = input()
Q = int(input())
queries = [list(input().split()) for _ in range(Q)]


def lam(x, y):
    return x | y


def a2n(a):
    return ord(a)-ord("a")


def createInp(n):
    return 1 << n


Seg = SegmentTree(len(S), lam, init=0)
for i, s in enumerate(S):
    Seg.set(i, createInp(a2n(s)))
Seg.build()

for q, l, r in queries:
    if q == "1":
        Seg.update(int(l)-1, createInp(a2n(r)))
    else:
        print(bin(Seg.query(int(l)-1, int(r))).count('1'))


Measured memory_bytes: 48532
#define _USE_MATH_DEFINES
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<cctype>
#include<iomanip>
#include<cassert>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

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

    int dice_num[6];
    int q;//質問の数
    int above, front;
    int above_index, front_index;//上面、全面が第何面にあるかを入れる

    int right[55];//上面と前面のindexから右面のindexを返す
    right[1] = 2;
    right[2] = 4;
    right[3] = 1;
    right[4] = 3;
    right[10] = 3;
    right[12] = 0;
    right[13] = 5;
    right[15] = 2;
    right[20] = 1;
    right[21] = 5;
    right[24] = 0;
    right[25] = 4;
    right[30] = 4;
    right[31] = 0;
    right[34] = 5;
    right[35] = 1;
    right[40] = 2;
    right[42] = 5;
    right[43] = 0;
    right[45] = 3;
    right[51] = 3;
    right[52] = 1;
    right[53] = 4;
    right[54] = 2;

    rep(i, 6){
        cin >> dice_num[i];
    }
    cin >> q;

    rep(i, q){//質問の数だけループ
        cin >> above >> front;

        rep(j, 6){
            if(above == dice_num[j]){
                above_index = j;//上面が第何面か
            }
            else if(front == dice_num[j]){
                front_index = j;//全面が第何面か
            }
        }

        cout << dice_num[right[above_index * 10 + front_index]] << '\n';
    }

    return 0;
}


Measured memory_bytes: 3128
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

int binpow(int a, int b) {
    if (b == 0)
    {
        return 1;
    }
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
    {
        return res * a;
    }
    return res;
}

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

string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    ll ans=0;
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
        {
            for (int k=1;k<=n;++k)
            {
                ans+=gcd(i,gcd(j,k));
            }
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
#define F first
#define S second
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long 
#define ld long double
#define pii pair <int ,int >
#define bug(x)  cout<<"passed "<<x<<endl;

long long const inf = 2e18, linf = 2e9, mod = 1e9+7;
int const mxn = 1e6 + 10 ;  ; 

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

long long ans ;
int main(){
	int n ; 
	cin>>n ;
	for (int i = 1; i <=n ; i++){
		if (i%3!=0 and i%5 !=0)
			ans+=i ; 
	}
	cout<<ans;

}

Measured memory_bytes: 3644
from operator import mul
from functools import reduce


def cmb(n, r):
	if n < r:
		return 0
	r = min(n - r, r)
	if r == 0:
		return 1
	numer = reduce(mul, range(n, n - r, -1))
	denom = reduce(mul, range(1, r + 1))
	return numer // denom % INF


N, K = map(int, input().split())
INF = 10 ** 9 + 7

for i in range(1, K + 1):
	print(cmb(K - 1, i - 1) * cmb(N - K + 1, i) % INF)


Measured memory_bytes: 3944
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//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 SQ(a) (a*a)
#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,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

int cnt[100005];

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	REP(i, m) {
		int x, y;
		scanf("%d%d", &x, &y);
		cnt[x]++;
		cnt[y]++;
	}
	REP(i, n + 1) {
		if (cnt[i] % 2) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;

	return 0;
}

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

int main() {
  int N;
  cin >>N;
  vector<int> x(N), y(N);
  for (int i=0; i<N; i++){
    cin >>x.at(i) >> y.at(i);
  }
  
  vector<int> order(N);
  for (int i=0; i<N; i++){
    order.at(i) = i;
  }
  
  double sum;
  int cnt=0;
  do{
    for (int i=1; i<N; i++){
      double x1, x2, y1, y2;
      double dis;
      x1 = x.at(order.at(i-1));
      x2 = x.at(order.at(i));
      y1 = y.at(order.at(i-1));
      y2 = y.at(order.at(i));
      dis = sqrt((pow(x1-x2, 2.0)+pow(y1-y2,2.0)));
      sum += dis;
      //cout <<order.at(i) <<" ";
    }
    //cout <<endl;
    cnt ++;
  }while(next_permutation(order.begin(),order.end()));
  
  double ans = sum / cnt;
  //cout <<cnt <<endl;
  printf ("%f\n",ans);
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    string n;
    cin >> n;

    int64_t r = 0;
    for (auto c : n) {
        r += c - '0';
    }

    cout << (r % 9 == 0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3708
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	const inputLines = input.split("\n");
	const line0 = inputLines[0];
	const line0vars = line0.split(" ");
	const line1 = inputLines[1];
	const line1vars = line1.split(" ");
	const q = parseInt(inputLines[2], 10);

	const n = parseInt(line0, 10);
	var sum = 0;

	const a = {};
	line1vars.forEach(ai => {
		const ai2 = parseInt(ai, 10);
		if (!a[ai2]) {
			a[ai2] = 0;
		}
		a[ai2] += 1;
		sum += ai2;
	});

	// console.log({
	// 	a: a,
	// 	sum: sum
	// });

	for (var i = 3; i < 3+q; i++) {
		const line = inputLines[i];
		const linevars = line.split(" ");
		const b = parseInt(linevars[0], 10);
		const c = parseInt(linevars[1], 10);

		if (!a[b]) {
			a[b] = 0;
		}
		if (!a[c]) {
			a[c] = 0;
		}
		sum += a[b] * (c - b);
		a[c] += a[b];
		a[b] = 0;

		// console.log({
		// 	a: a,
		// 	b: b,
		// 	c: c,
		// 	sum: sum
		// });
		console.log(sum);
	}

	// tmp = input[1].split(" ");
	// //文字列から10進数に変換するときはparseIntを使います
	// var a = parseInt(input[0], 10);
	// var b = parseInt(tmp[0], 10);
	// var c = parseInt(tmp[1], 10);
	// var s = input[2];

	//出力
	// console.log('%d %s',a+b+c,s);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

// node index.js
// 1
// 2 3
// test
// (Ctrl + D)


Measured memory_bytes: 65452
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
const int INF = 1e9;
const int EPS = 1e-9; 

int main() {
  int N;
  cin >> N;
  vector<double> v(N);
  for(int i = 0; i < N; ++i) cin >> v.at(i);
  sort(v.begin(), v.end());
  
  double ave = (v.at(0) + v.at(1))/2;
  for (int i = 2; i < N; ++i) {
    ave = (ave + v.at(i))/2;
  }
  cout << ave << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	void run() {
		Scanner sc = new Scanner(System.in);

		char[] c = sc.next().toCharArray();
		int n = c.length;
		int[] r = new int[n];
		int[] l = new int[n];

		l[0] = 1;
		for (int i = 1; i < n; i++) {
			if (c[i - 1] == c[i]) {
				l[i] = l[i - 1];
			} else {
				l[i] = l[i - 1] + 1;
			}
		}

		r[n - 1] = 1;
		for (int i = n - 2; 0 <= i; i--) {
			if (c[i] == c[i + 1]) {
				r[i] = r[i + 1];
			} else {
				r[i] = r[i + 1] + 1;
			}
		}

		int min = n;
		for (int i = 0; i < n; i++) {
			min = Math.min(min, l[i] + r[i] - 2);
		}
		System.out.println(min);
	}

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


Measured memory_bytes: 13788
import Foundation

let XKD = readLine()!.split(separator: " ").compactMap { Int($0) }
let X = XKD[0]
let K = XKD[1]
let D = XKD[2]

var minValue: Int
var requiredValue: Int
if X <= 0 {
    minValue = (-1 * X) % D
    requiredValue = (-1 * X) / D
} else {
    minValue = X % D
    requiredValue = X / D
}
if abs(minValue - D) < minValue {
    minValue = abs(minValue - D)
    requiredValue += 1
}

if requiredValue < K {
    let isOdd = (K - requiredValue) % 2 != 0
    if requiredValue % 2 == 0 {
        if isOdd {
            print(abs(minValue - D))
        } else {
            print(abs(minValue))
        }
    } else {
        if isOdd {
            print(abs(minValue - D))
        } else {
            print(abs(minValue))
        }
    }
} else {
    if X <= 0 {
        print(abs(X + K * D))
    } else {
        print(abs(X - K * D))
    }
}


Measured memory_bytes: 13592
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <string>
#include <bitset>
#include <queue>
#include <unordered_set>
#include <cstring>
#define int long long
#define pii pair<int, int>
#define double long double
#define pdd pair<double, double>
#define mp make_pair
#define debug(x) std::cout << #x << ": " << x << '\n';
using namespace std;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
} 

const int N = 2e5 + 10;
int c[N];
int s[N];
const int mod = 1e9 + 7;

signed main() {
	fast();
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}
	int d = 1;
	int pd = 1;
	int xd = -1;
	for (int i = 0; i < n; i++) {
		if (xd == c[i]) {
			d = (pd + s[c[i]]) % mod;
		} else {
			pd = d;
			xd = c[i];
			d = (d + s[c[i]]) % mod;
		}
		if (i == n - 1 || c[i] != c[i + 1]) {
			s[c[i]] += pd;
			s[c[i]] %= mod;
		}
		//cout << d << ' ';
	}
	cout << d % mod;
	return 0;
}

Measured memory_bytes: 3328
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 10;

int main() {
	int n;
	while (cin >> n, n) {
		vs s(n);
		REP(i, n) {
			cin >> s[i];
		}

		vs code(n);
		REP(i, n) {
			code[i].push_back(s[i][0]);
			int l = s[i].size();
			REP(j, l - 1) {
				char c = s[i][j];
				if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o') {
					code[i].push_back(s[i][j + 1]);
				}
			}
		}

		int l = -1;
		REP(i, n) {
			l = max(l, (int)code[i].size());
		}

		int ans = -1;
		FOR(i, 1, l) {
			set<string> ss;
			REP(j, n) {
				ss.insert(code[j].substr(0, i));
			}
			if (ss.size() == n) {
				ans = i;
				break;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1236
#include<iostream>
#include<algorithm>
using namespace std;
int x[2000][2000], a, b, c, p, sum, maxn; char f;
int main() {
	while (cin >> a >> f >> b >> f >> p) {
		if (p % 2 == 1) {
			c = p / 2 + 1;
			for (int i = -c; i <= c; i++) {
				for (int j = -c; j <= c; j++) {
					if (a + i >= 0 && b + j >= 0) {
						if ((i + j >= -c && i + j <= c) && (i - j >= -c && i - j <= c)) {
							x[a + i][b + j]++;
						}
					}
				}
			}
		}
		else {
			for (int i = -1; i <= 1; i++) {
				for (int j = -1; j <= 1; j++) {
					if (a + i >= 0 && b + j >= 0) {
						x[a + i][b + j]++;
					}
				}
			}
		}
	}
	sum = 0;
	maxn = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (x[i][j] == 0) { sum++; }
			maxn = max(maxn, x[i][j]);
		}
	}
	cout << sum << endl << maxn << endl;
}

Measured memory_bytes: 1204
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <iostream>
#include <stack>
#include <string>
using namespace std;
#define max(a,b) (a>b?a:b)

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);;
	string a,b;
	cin>>a>>b;
	cout<<b<<a<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int A[3][3];
  for(int i=0;i<3;++i) {
    for(int j=0;j<3;++j) {
      cin>>A[i][j];
    }
  }
  int N;
  cin>>N;
  int tmp;
  for(int i=0;i<N;++i) {
    cin>>tmp;
    for(int j=0;j<3;++j) {
      for(int k=0;k<3;++k) {
        if(A[j][k]==tmp) A[j][k] = -1;
      }
    }
  }
  bool can = false;
  if(A[0][0]==A[0][1] && A[0][1]==A[0][2]) can = true;
  if(A[1][0]==A[1][1] && A[1][1]==A[1][2]) can = true;
  if(A[2][0]==A[2][1] && A[2][1]==A[2][2]) can = true;
  if(A[0][0]==A[1][0] && A[1][0]==A[2][0]) can = true;
  if(A[0][1]==A[1][1] && A[1][1]==A[2][1]) can = true;
  if(A[0][2]==A[1][2] && A[1][2]==A[2][2]) can = true;
  if(A[0][0]==A[1][1] && A[1][1]==A[2][2]) can = true;
  if(A[2][0]==A[1][1] && A[1][1]==A[0][2]) can = true;
  if(can) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}



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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<ll> a(N * 3);
    rep(i, N * 3) cin >> a[i];

    // 左から累積和を取る
    vector<ll> S(N * 2 + 1, 0);
    priority_queue<ll, vector<ll>, greater<ll>> q1;
    rep(i, N) {
        S[i + 1] = S[i] + a[i];
        q1.push(a[i]);
    }
    for (int i = N; i < N * 2; i++) {
        S[i + 1] = S[i] + a[i];
        q1.push(a[i]);

        S[i + 1] -= q1.top();
        q1.pop();
    }

    // 右から累積和を取る
    vector<ll> T(N * 2 + 1, 0);
    priority_queue<ll> q2;
    rep(i, N) {
        T[i + 1] = T[i] + a[N * 3 - 1 - i];
        q2.push(a[N * 3 - 1 - i]);
    }
    for (int i = N; i < N * 2; i++) {
        T[i + 1] = T[i] + a[N * 3 - 1 - i];
        q2.push(a[N * 3 - 1 - i]);

        T[i + 1] -= q2.top();
        q2.pop();
    }

    ll ans = -(1LL << 60);
    for (int i = N; i <= N * 2; i++) chmax(ans, S[i] - T[N * 3 - i]);
    cout << ans << endl;
}

Measured memory_bytes: 8052
#include<iostream>
#include<string>
#include<cstdlib>
#include<math.h>
using namespace std;
int main(void){
    int a,b,x;
    cin >> a >> b >> x;
    if(a<=x&&a+b>=x){
        printf("YES");
    }else{
        printf("NO");
    }
    
    return 0;
    
}

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

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

    vector<pair<int, int> > p;
    int check[n];
    int ans[n];
    for(int i= 0; i < n; i++){
        check[i] = 100000000;
        ans[i] = 100000000;
    } 
    check[0] = 0;
    ans[0] = 0;
    vector<int> gra[n];

    for(int i = 0; i < m; i++){
        int k, t;
        cin >> k >> t;
        k--;
        t--;
        gra[k].push_back(t);
        gra[t].push_back(k);
    }

    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int k = q.front();
        q.pop();

        for(int i = 0; i < gra[k].size(); i++){
            if(check[gra[k][i]] > check[k] + 1){
                check[gra[k][i]] = check[k] + 1;
                q.push(gra[k][i]);
                ans[gra[k][i]] = k + 1;
            }
        }
    }

    cout << "Yes" << endl;
    for(int i = 1; i < n; i++){
        cout << ans[i] << endl;
    }

}

Measured memory_bytes: 10784
n,m = map(int,input().split())
data = []
for i in range(n):
    a,b = map(int,input().split())
    data.append([a,b])

data.sort(key = lambda x: x[0])
left = m
i = 0
ans = 0
while left != 0:
    if data[i][1] <= left:
        ans += data[i][0] * data[i][1]
        left -= data[i][1]
    else:
        ans += data[i][0] * left
        left = 0
    i += 1
print(ans)

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

// 入力
int N;
long long a[100010][3]; // a[i], b[i], c[i] をそれぞれまとめて a[i][0], a[i][1], a[i][2] にしてしまう

// DP テーブル
long long dp[100010][3];

int main() {
    int N; cin >> N;
    for (int i = 0; i < N; ++i) for (int j = 0; j < 3; ++j) cin >> a[i][j];
// ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (j == k) continue;
                dp[i+1][k] = max(dp[i+1][k], dp[i][j] + a[i][k]);
            }
        }
    }

    // 答え
    long long res = 0;
    for (int j = 0; j < 3; ++j) res=max(res, dp[N][j]);
    cout << res << endl;
}

Measured memory_bytes: 8328
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
  long long N; cin>>N;
  vector<long long>n(1),s(1);
  n[0]=9;s[0]=6;
  for(int i=1;pow(9,i+1)<=N;i++){
    n.push_back(pow(9,i+1));
  }
  for(int i=1;pow(6,i+1)<=N;i++){
    s.push_back(pow(6,i+1));
  }

  vector<int> cost(N+100,10000);
  cost[0]=0;
  for(int i=0;i<N;i++){
    if(cost[i+1]>(cost[i]+1)) cost[i+1]=cost[i]+1;
    for(int j=0;j<n.size();j++){
      if((i+n[j])<=N){
        if(cost[i+n[j]]>(cost[i]+1)) cost[i+n[j]]=cost[i]+1;
      }
    }
    for(int j=0;j<s.size();j++){
      if((i+s[j])<=N){
        if(cost[i+s[j]]>(cost[i]+1)) cost[i+s[j]]=cost[i]+1;
      }
    }
  }

  cout<<cost[N]<<endl;

  return 0;
}



Measured memory_bytes: 896
#include<stdio.h>
int main(void){
 int N;
 int i;
 int A[100];
 scanf("%d", &N);
 for(i=0;i<N;i++){
  scanf("%d",&A[i]);
 }
 int flag = 1;
 int j;
 int tmp;
 int count=0;
 while (flag){
  flag = 0;
  for(j=N-1;j>0;j--){
   if(A[j]<A[j-1]){
    tmp = A[j];
    A[j] = A[j-1];
    A[j-1] = tmp;
    flag=1;
    count++;
   }
  }
 }
 for(j=0;j<N;j++){
  if(j==N-1){
   printf("%d\n",A[j]);
  }else{
   printf("%d ",A[j]);
  }
 }
 printf("%d\n", count);

 return 0;
}

Measured memory_bytes: 1772
#include<cstdio>
using namespace std;
int a,b,c;
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	if (a==b&&b==c)
		printf("%d\n",1);
	else if (a!=b&&b!=c&&a!=c)
		printf("%d\n",3);
	else
		printf("%d\n",2);
	return 0;
}

Measured memory_bytes: 128