akhauriyash/Code-Regression huggingface dataset:
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;

namespace abc154
{
    class Program
    {
        static void Main(string[] args)
        {
            if (File.Exists("input.txt"))
            {
                Console.SetIn(new StreamReader("input.txt"));
            }
			solve_abc154A();
        }

        public static void solve_abc154B()
        {

        }

        public static void solve_abc154A()
        {
            string[] color = Console.ReadLine().Split();
            int[] number = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            string rm = Console.ReadLine();

            if (rm == color[0])
            {
                number[0]--;
                Console.WriteLine("{0} {1}", number[0], number[1]);
            }
            else
            {
                number[1]--;
                Console.WriteLine("{0} {1}", number[0], number[1]);
            }
        }
    }
}


Measured memory_bytes: 13268
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<queue>
#include<set>
#include<stack>

using namespace std;

int main(){
    long long N,H;
    long long maxA=0;
    long long b[100000];
    cin>>N>>H;
    for(int i=0;i<N;i++){
        long long a;
        cin>>a>>b[i];
        maxA=max(a,maxA);
    }
    sort(b,b+N,greater<long long>());
    long long ans=1e9;
    long long sum=0;
    for(long long i=0;i<N;i++){
        //(i+1)回刀を投げる
        sum += b[i];
        long long tmp=H-sum;
        if(tmp<0){
            ans=min(ans,i+1);
            break;
        }
        long long ans_tmp=(i+1)+(tmp+maxA-1)/maxA;
        ans=min(ans,ans_tmp);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ri register int
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef vector<int> poly;
#define pb push_back
const int rlen=1<<18|1,inf=0x3f3f3f3f;
const ll Inf=1e18;
char buf[rlen],*ib=buf,*ob=buf;
#define gc() (((ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin)),ib==ob)?-1:*ib++)
inline int read() {
  int ans=0;
  bool f=1;
  char ch=gc();
  while(!isdigit(ch)) f^=ch=='-',ch=gc();
  while(isdigit(ch)) ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
  return f?ans:-ans;
}
inline ll readl() {
  ll ans=0;
  bool f=1;
  char ch=gc();
  while(!isdigit(ch)) f^=ch=='-',ch=gc();
  while(isdigit(ch)) ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
  return f?ans:-ans;
}
inline int Read(char*s) {
  int tp=0;
  char ch=gc();
  while(!isdigit(ch)&&!isalpha(ch)) ch=gc();
  while(isdigit(ch)||isalpha(ch)) s[++tp]=ch,ch=gc();
  return tp;
}
namespace modular {
  const int mod=998244353,iv2=(mod+1)>>1;
  inline int add(int a,int b) { return a+b<mod?a+b:a+b-mod; }
  inline int dec(int a,int b) { return a<b?a-b+mod:a-b; }
  inline int mul(int a,int b) { return (ll)a*b%mod; }
  inline void Add(int&a,int b) { a=a+b<mod?a+b:a+b-mod; }
  inline void Dec(int&a,int b) { a=a<b?a-b+mod:a-b; }
  inline void Mul(int&a,int b) { a=(ll)a*b%mod; }
  inline int ksm(int a,int p) { int ret=1;for(;p;p>>=1,Mul(a,a)) (p&1)&&(Mul(ret,a),1);return ret; }
  inline int Inv(int a) { return ksm(a,mod-2); }
  inline int sqr(int a) { return mul(a,a); }
  inline int cub(int a) { return (ll)a*a%mod*a%mod; }
}
using namespace modular;
template<typename T> inline void ckmax(T&a,T b) { a<b?a=b:0; }
template<typename T> inline void ckmin(T&a,T b) { a>b?a=b:0; }
template<typename T> inline T gcd(T a,T b) { T t;while(b)t=a,a=b,b=t-t/a*a;return a; }
template<typename T> inline T Abs(T x) { return x<0?-x:x; }
const int N=1e6+5,lm=1<<10;
vector<int>e[N];
bool vs[lm+5];
int n,m,sg[N],pw[N],f[lm+5],g[3][lm+5];
inline void fwt(int*a,int typ) {
  for(ri i=1,a0,a1;i<lm;i<<=1) for(ri j=0;j<lm;j+=i<<1) for(ri k=0;k<i;++k) {
    a0=a[j+k],a1=a[j+k+i];
    a[j+k]=add(a0,a1),a[j+k+i]=dec(a0,a1);
    if(typ==-1) Mul(a[j+k],iv2),Mul(a[j+k+i],iv2);
  }
}
int main() {
  #ifdef ldxcaicai
  freopen("lx.in","r",stdin);
  #endif
  n=read(),pw[0]=1,pw[1]=Inf%mod;
  for(ri i=2;i<=n;++i) pw[i]=mul(pw[i-1],pw[1]);
  for(ri tt=0;tt<3;++tt) {
    m=read();
    for(ri i=1;i<=n;++i) e[i].clear(),sg[i]=0;
    for(ri i=1,u,v;i<=m;++i) {
      u=read(),v=read();
      e[min(u,v)].pb(max(u,v));
    }
    for(ri i=n;i;--i) {
      for(ri j=0;j<e[i].size();++j) vs[sg[e[i][j]]]=1;
      for(sg[i]=0;vs[sg[i]];++sg[i]);
      Add(g[tt][sg[i]],pw[i]);
      for(ri j=0;j<e[i].size();++j) vs[sg[e[i][j]]]=0;
    }
    fwt(g[tt],1);
  }
  for(ri i=0;i<lm;++i) f[i]=mul(mul(g[0][i],g[1][i]),g[2][i]);
  fwt(f,-1);
  cout<<f[0];
  return 0;
}

Measured memory_bytes: 32768
def inpl(): return [int(i) for i in input().split()]
i, o, t, j, l, s, z = inpl() 
i, j, l = sorted([i,j,l])
if not (l-i)%2 and not (j-i)%2:
    print(o+i+j+l)
elif i == 0 and j == 1 and l == 1:
    print(o+i+j+l-2)
else:
    print(o+i+j+l-1)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> // sort
#include <map>
#include <string>
#include <bits/stdc++.h>

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

static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;
using pint = pair<int,int>;


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

  ll res = 0;

  ll tmp = m / n;

  for(ll i = tmp; i > 0; --i)
  {
    if(m % i == 0)
    {
      cout << i << endl;
      break; 
    }
  }

  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<math.h>
using namespace std;
typedef long long int ll;
int main()
{
  ll n,d;
  cin>>n>>d;
  ll cnt=0;
  for(ll i=0;i<n;i++)
  {
    ll x,y;
    cin>>x>>y;
    if(sqrt(x*x+y*y)<=d)
      cnt++;
  }
  cout<<cnt<<"\n";
}

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

int main(){
	int N, M, C, i, j;
	scanf("%d%d%d", &N, &M, &C);
	vector<int> B(M);
	for(i = 0; i < M; i++){
		scanf("%d", &B[i]);
	}
	int ans = 0;
	for(i = 0; i < N; i++){
		int now = C;
		for(j = 0; j < M; j++){
			int A;
			scanf("%d", &A);
			now += A * B[j];
		}
		if(now > 0){
			ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <string> 
using namespace std;
#include <string> 
#define fast ios_base::sync_with_stdio(false);	cin.tie(NULL);
typedef long long ll;
#define MAX 1000000000
ll abs(ll a, ll b){
	return (a<b?b-a:a-b);
}

int main()
{
	fast;
	int a[100005],dp[100005],k,n,i,j,mi=1000000;
	cin>>n>>k;
	for(i=0;i<n;i++){
		cin>>a[i];
		dp[i]=0;
	}
	dp[0]=0;
	dp[1]=abs(a[1]-a[0]);
	
	for(i=2;i<n;i++)
	{	j=((i-k)>0)?i-k:0;
		mi=MAX;
		while(j<i && j<n){
			mi=min(dp[j]+abs(a[i]-a[j]),mi);
			j++;
		}
		dp[i]=mi;
	}
	cout<<dp[n-1]<<endl;
	return 0;
}
/*

for(i=2;i<k+1&&i<n;i++){
		j=0;
		mi=1000005;
		while(j<i && j<n){
			mi=min(dp[j]+abs(a[i]-a[j]),mi);
			j++;
		}
		dp[i]=mi;
	}
	*/

Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <assert.h>
typedef int64_t ll;
typedef uint64_t ull;
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)

#define MAXN (2000)
#define MOD (1000000007)


ll dp[MAXN+1][MAXN+1];
ll s[MAXN+1];
ll t[MAXN+1];
int main(void)
{
    ll n,m;
    scanf("%ld %ld",&n,&m);
    for(int i=0;i<n;i++) scanf("%ld",&(s[i]));
    s[n] = 0;
    for(int i=0;i<m;i++) scanf("%ld",&(t[i]));
    t[m] = 0;

    for(int i=0;i<=n;i++) dp[0][i] = 1;

    for(int j=1;j<=m;j++)
    {
        ll p = 0;
        dp[j][0] = 1;
        for(int i=1;i<=n;i++)
        {
            if(s[i-1]==t[j-1])
            {
                p+= dp[j-1][i-1];
                p%=MOD;
            }
            dp[j][i] = dp[j-1][i] + p;
            dp[j][i] %= MOD;
        }
    }

    printf("%ld\n",dp[m][n]);
    return 0;
}


Measured memory_bytes: 31488
#include <bits/stdc++.h>
#define int long long
/*#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define tr(container, it) \
for(typeof((container).begin()) it = (container).begin(); it != (container).end(); it++)
#define present(container, element) ((container).find(element) != (container).end())
#define cpresent(container, element) (find(all(container),element) != (container).end())
*/

using namespace std;

/*typedef long long ll;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > pii;
*/

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

string s,t;
cin>>s>>t;
cout<<t<<s;
return 0;
}


Measured memory_bytes: 256
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back

template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

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

//scanf("%lld", &);
//cin >> ;
//cout << ans << endl;

ll N, M, K, i, j, k, l, ans, cnt = 0;
string s;

int main(){
    //cin >> ;
    //cout << ans << endl;

    //cin >> ;
    ll A, B;
    scanf("%lld", &K);
    scanf("%lld", &A);
    scanf("%lld", &B);

    FOR(i, A, B){
        if(i % K == 0){
            cout << "OK";
            cout << endl;
            return 0;
        }
    }
    cout << "NG";

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

Measured memory_bytes: 3764
#include<stdio.h>
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int main(void){
    int x;
    scanf("%d",&x);
    ll ans=2;
    REP(i,x){
        ans+=1;
        ans*=2;
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define mk make_pair
int main()
{
  ll a,b,c,x=0;
  cin>>a>>b>>c;
  for(ll i=0;i<b;i++)
  {
    if((a*(i+1))%b==c)
    {
      x=1;
      break;
    }
  }
  if(x==0)cout<<"NO"<<endl;
  else
  cout<<"YES"<<endl;
}


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

int main(){
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;
  int result =2147483647;
  for(int i = 0; i < 200001; i += 2){
    int tmp = C * i + A * (i/2< X ? X-i/2 : 0) + B * (i/2<Y ? Y-i/2 : 0);
    if(tmp < result){
      result = tmp;
    }
  }
  cout << result << endl;
}


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

constexpr int MAXN = 100;
int G[MAXN][MAXN];
int P[MAXN];
int D[MAXN];
int C[MAXN];

constexpr int MAXINT = std::numeric_limits<int>::max();

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

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

    for (int i = 0; i < n; i++) {
        D[i] = MAXINT;
    }

    for (int i = 0; i < n; i++) {
        int id, e_num;
        std::cin >> id >> e_num;
        for (int j = 0; j < e_num; j++) {
            int t;
            std::cin >> t;
            std::cin >> G[id][t];
        }
    }

    int r = 0;
    D[r] = 0;
    while (true) {
        int mincost = MAXINT;
        int m;
        for (int i = 0; i < n; i++) {
            if ((C[i] == 0) && (D[i] < mincost)) {
                mincost = D[i];
                m = i;
            }
        }

        if (mincost == MAXINT) {
            break;
        }

        C[m] = 1;
        for (int i = 0; i < n; i++) {
            if ((C[i] != 1) && (G[m][i] != MAXINT)&& ((D[m] + G[m][i]) < D[i])) {
                P[i] = m;
                D[i] = D[m] + G[m][i];
            }
        }
    }

    for (int i = 0; i < n; i++) {
        std::cout << i << " " << D[i] << std::endl;
    }

}


Measured memory_bytes: 3140
N = int(input())
A = list(map(int, input().split()))

ans = 0
start_idx = [0] * N
for i, a in enumerate(A):
    if i+1+a < N:
        start_idx[i+1+a] += 1
    if i-a+1 >= 0:
        ans += start_idx[i-a+1]

print(ans)


Measured memory_bytes: 93008
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#include<cstring>

using namespace std;

#ifdef LDEBUG
#define debug(x) cout << #x << ":" << x << endl
#else
#define debug(...)
#endif

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

typedef unsigned long long u64;
typedef long long i64;

int n;
int v1_[100005];
int v2_[100005];
vector<pair<int,int> > v1, v2;


bool cm(const pair<int,int> &a, const pair<int,int> &b) {
        return a.first > b.first;
}

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

        cin >> n;
        REP(i, n) {
                int t;
                cin >> t;
                if (i%2 == 1)
                        v1_[t]++;
                else
                        v2_[t]++;
        }

        REP(i,100005){
                if(v1_[i] > 0)
                        v1.push_back(pair<int,int>(v1_[i],i));
                if(v2_[i] > 0)
                        v2.push_back(pair<int,int>(v2_[i],i));
        }

        debug(v1.size());
        debug(v2.size());

        sort(v1.begin(), v1.end(), cm);
        sort(v2.begin(), v2.end(), cm);

        debug(v1[0].first);
        debug(v2[0].first);
        debug(v1[0].second);
        debug(v2[0].second);

        if ( v1[0].second != v2[0].second)
                cout << n - v1[0].first - v2[0].first << endl;
        else {
                int m = 100000000;
                m = min(m, n - v1[0].first - v2[1].first);
                m = min(m, n - v2[0].first - v1[1].first);
                cout << m << endl;
        }


        return 0;
}


Measured memory_bytes: 2044
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 1000000009
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

struct edge {
  ll to;
  ll id;
  bool operator<(const edge &another) const{
    return id < another.id;
  };
  ll length;
};

vector<pair<int, vector<edge>>> tree;
vector<bool> p(false);
vector<bool> color(false);

void dfs(ll x, ll d){
  if(p.at(x)){
    return;
  }
  p.at(x) = true;
  if(d % 2 == 0){
    color.at(x) = true;
  }
  for(auto e : tree.at(x).second){
    dfs(e.to, d+e.length);
  }
}

int main(){
  ll N;
  cin >> N;
  tree.resize(N);
  p.resize(N);
  color.resize(N);
  vector<ll> u(N-1), v(N-1), w(N-1);
  rep(i, N-1){
    cin >> u.at(i) >> v.at(i) >> w.at(i);
    u.at(i)--;
    v.at(i)--;
    tree.at(u.at(i)).first = u.at(i);
    tree.at(v.at(i)).first = v.at(i);
    tree.at(u.at(i)).second.push_back({ v.at(i), i, w.at(i) });
    tree.at(v.at(i)).second.push_back({ u.at(i), i, w.at(i) });
  }
  color.at(0) = true;
  dfs(0, 0);
  rep(i, N){
    if(color.at(i)){
      cout << 0 << endl;
    }
    else{
      cout << 1 << endl;
    }
  }
}

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

#define MAX_N 1000001

using namespace std;

const int INF = (1LL<<31)-1;
int sqrtN;
int N,K;
vector<int> data;
vector<bool> lazyflag;
vector<int> lazyupdate;

void init(){
	K=(N+sqrtN-1)/sqrtN;
	data.assign(K*sqrtN,INF);
	lazyflag.assign(K,false);
	lazyupdate.assign(K,0);
}

void eval(int k){
	if(lazyflag[k]){
		lazyflag[k]=false;
		for(int i=k*sqrtN;i<(k+1)*sqrtN;i++){
			data[i]=lazyupdate[k];
		}
	}
}

void update(int s, int t, int x){
	for(int k=0;k<K;k++){
		int l=k*sqrtN;
		int r=(k+1)*sqrtN;
		if(r<=s || t<=l) continue;
		if(s<=l && r<=t){
			lazyflag[k]=true;
			lazyupdate[k]=x;
		}
		else{
			eval(k);
			for(int i=max(s,l);i<min(t,r);i++){
				data[i]=x;
			}
		}
	}
}

void find_i(int i){
	int k=i/sqrtN;
	eval(k);
	printf("%d\n",data[i]);
}

int main(){
	int q,com;
	int s,t,x;
	scanf("%d %d",&N,&q);
	sqrtN=(int)sqrt(N);
	init();
	for(int i=0;i<q;i++){
		scanf("%d",&com);
		if(com==0){
			scanf("%d %d %d",&s,&t,&x);
			update(s,t+1,x);//[s,t)
		}
		else{
			scanf("%d",&x);
			find_i(x);
		}
	}
}


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

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int sign = 0, ans = 1;
    for (int i = 1; i < n; i++) {
        int new_sign = a[i] - a[i - 1];
        if (sign < 0 && new_sign > 0 || sign > 0 && new_sign < 0) {
            ans++;
            sign = 0;
        }
        else if (new_sign)
            sign = new_sign;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1e16;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll a[n+1],b;
    a[0] = 0;
    rep(i,n){
        cin >> b;
        a[i+1] = a[i]+b;
    }
    ll ans = INF;
    rep(i,2,n-1){
        ll l = a[i]/2,r = a[i]+(a[n]-a[i])/2;
        ll i1 = upper_bound(a,a+n+1,l)-a-1;
        if (abs(a[i1]-l) > abs(a[i1+1]-l)) i1++;
        ll i2 = upper_bound(a,a+n+1,r)-a-1;
        if (abs(a[i2]-r) > abs(a[i2+1]-r)) i2++;
        rep(j,-1,2){
            rep(k,-1,2){
                i1 += j;
                i2 += k;
                chmin(ans,max({a[i1],a[i]-a[i1],a[i2]-a[i],a[n]-a[i2]})-min({a[i1],a[i]-a[i1],a[i2]-a[i],a[n]-a[i2]}));
                i1 -= j;
                i2 -= k;
            }
        }
    }
    PRINT(ans);
}


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

a=[input() for i in range(H)]

while True:
    b=a
    for i in range(len(a)-1,-1,-1):
        if not "#" in a[i]: a.pop(i)   

    for j in range(len(a[0])-1,-1,-1):
        if all(a[i][j]=="." for i in range(len(a))):
            for i in range(len(a)):
                a[i]=a[i][:j]+a[i][j+1:]


    if b==a: break

for i in range(len(a)): print(a[i])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second

using namespace std;
int main()
{
	std::ios::sync_with_stdio(false);
	string s;
	cin >> s;

	int ans = 0;
	int cnt = 0;
	for (int i = 0; i < 3; ++i) {
		if (s[i] == 'R') {
			++cnt;
		} else {
			cnt = 0;
		}
		ans = max(ans, cnt);
	}

	cout << ans << '\n';

	return 0;
}


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


int main(void)
{
	long int i, j;
	long int n, q;
	long int max;
	long int count;
	long int work;
	long int a[100];
	double sum;
	
	scanf("%ld", &n);
	
	for(i = 0; i < n; i++) {
		scanf("%ld", &a[i]);
	}
	
	sum = 0.0;
	for(i = 0; i < n; i++) {
		sum += (double)1.0 / a[i];
	}
	
	printf("%lf\n", 1.0 / sum);
	
	return 0;
}


Measured memory_bytes: 128
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();
		sc.close();
		
		if(A <= 8 && B <= 8)
			System.out.println("Yay!");
		else
			System.out.println(":(");
	}
}


Measured memory_bytes: 23124
#include<iostream>
#include<vector>
#include<string>
#include<stdlib.h>
using namespace std;
int main(){
    int N;
    int counter=0;
    bool flag=true;
    cin>>N;
    vector <int>A(N);
    for(int i=0;i<N;i++){
        cin>>A.at(i);
    }
    while(flag){
        
        for(int i =0; i<N; i++){
            if(A.at(i)%2==0){
                A.at(i)/=2;
            }
            else{
                flag=false;
                break;
            }
            
            
    
    }
        counter++;
    }
    cout<<counter-1<<endl;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

signed main(){
	int N;
	cin>>N;
	vector<string>S(N);
	vint P(N);
	rep(i,N)cin>>S[i]>>P[i];

	vint ord(N);iota(all(ord),0);
	sort(all(ord),[&](int i,int j){
		if(S[i]!=S[j])return S[i]<S[j];
		return P[i]>P[j];
	});
	rep(i,N){
		cout<<ord[i]+1<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main(){
    int N,M;cin>>N>>M;
    vl info(N);
    rep(i,M){
        int a,b;cin>>a>>b;
        info[--a]++,info[--b]++;
    }
    rep(i,N)cout<<info[i]<<endl;
    return 0;
}

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

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

  if (A+B>C+D) {
    cout << "Left" << endl;
  }
  else if (A+B<C+D){
    cout<<"Right"<<endl;
  }
  else
    cout<<"Balanced"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<iomanip>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
int main(){
  int a, b;
  cin >> a >> b;
  cout << 6 - a - b << "\n";
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

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

    int N;
    cin >> N;
    string S;
    cin >> S;
    int x = 0, ans = 0;
    for (int i = 0; i < N; ++i) {
        if (S.at(i) == 'I') {
            x++;
            ans = max(ans, x);
        } else {
            x--;
        }
    }
    cout << ans << endl;

    return 0;
}

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

typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;

const int  INF =  1e9;
const ll LINF = 1e18;
const ll MOD = 1e9+7;
const int SIZE = 100;

template<class T>
inline T gcd(T a, T b){return b ? gcd(b, a % b) : a;}

template<class T>
inline T lcm(T a, T b){return a / gcd(a, b) * b;}
 
ll fac[SIZE], inv[SIZE], facinv[SIZE];
void make() {
	fac[0] = fac[1] = 1; inv[1] = 1; facinv[0] = facinv[1] = 1;
	for (ll i = 2; i < SIZE; i++) {
		fac[i] = (fac[i-1] * i) % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		facinv[i] = facinv[i-1] * inv[i] % MOD;
	}
}
ll combi(ll a, ll b) {
	if (a < b) return 0;
	return fac[a] * (facinv[b] * facinv[a-b] % MOD) % MOD;
}

int main() {
	ll n;
	scanf ("%lld", &n);
	vector<ll> a(n);
	for (ll i = 0; i < n; i++) {
		scanf ("%lld", &a[i]);
	}
	ll ans = 0;
	ll w = 0;
	ll h = 0;
	
	sort(a.begin(), a.end(), greater<ll>());
	bool flg = false;
	for (ll i = 0; i < n-1; i++) {
		if (a[i] == a[i+1] && flg == false) {
			w = a[i];
			i++;
			flg = true;
		} else if (a[i] == a[i+1] && flg == true) {
			h = a[i];
			break;
		}
	}
	printf("%lld\n", w*h);
	
	return 0;
}


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

#define pai 3.1415926535
#define GYOU_MAX 80



int main(void)
{

	char s[13];
	scanf("%s", s);
	char s1[20]="";
	strncpy(s1, s, 4);
	strcat(s1, " ");
	strcat(s1, &s[4]);
	printf("%s\n", s1);

	return 0;


}

Measured memory_bytes: 128
#define N 2000000
#include<stdio.h>
#include<stdlib.h>

struct Node{
  int key;
  struct Node *left,*right,*parent;
};

struct Node *root,*NIL;

void insert(int n){
  struct Node *y;
  struct Node *x;
  struct Node *z;
  y = NIL;
  x = root;
  z = (struct Node *)malloc(sizeof(struct Node));
  z->key = n;
  z->left = NIL;
  z->right = NIL;
  while(x != NIL){
    y = x;
    if(z->key<x->key){
      x = x->left;
    }
    else{
      x = x->right;
    }
  }
  z->parent = y;
  if(y == NIL){
    root = z;
  }
  else{
    if(z->key < y->key){
      y->left = z;
    }
    else{
      y->right = z;
    }
  }
}

void middle(struct Node *k){
  if(k == NIL)return;
  middle(k->left);
  printf(" %d",k->key);
  middle(k->right);
 
}

void precede(struct Node *k){
  if(k == NIL)return;
  printf(" %d",k->key);
  precede(k->left);
  precede(k->right);
}








int main(){
  int n,i,j;
  char m[N];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",m);
    if(m[0] == 'i'){
      scanf("%d",&j);
      insert(j);
    }
    else if(m[0] == 'p'){
      middle(root);
      printf("\n");
      precede(root);
      printf("\n");
    }
  }
  return 0;
}

Measured memory_bytes: 24048
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pb emplace_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define F first
#define S second
#define vll vector<ll>
#define fast ios:: sync_with_stdio(false),cin.tie(0);
#define COUT cout<<fixed<<setprecision(12)
#define SET set<ll,greater<ll>>gquiz
#define ITERATOR set<ll,greater<ll>> :: iterator itr
#define V vector<ll>vector
#define sz size()
//#define A vector<pair<ll,ll>>vect
ll N=100000,M=100000;
#define B vect.push_back(make_pair(N,M));
ll MOD=1000000007;
 
ll gcd(ll a,ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
/*ll ncr(ll n,ll r)
{
	if(n==1 || r==0)
	return 1;
	if(r>n/2)
	r=n-r;
	ll ans=1;
	for(ll i=1;i<=r;i++)
	{
		ans=((ans * n )/i);
		n--;
	}
	return ans;
}*/
ll pow1(ll n,ll k,ll mm){
    if(k==0)return 1;
    if(k%2==0)return (pow1((n%mm)*(n%mm),k/2,mm))%mm;
    return ((n%mm)*(pow1((n%mm)*(n%mm),k/2,mm)%mm))%mm;
}
ll pow(ll a,ll b,ll m)
{
	ll ans=1;
	while(b>0)
	{
		if(b&1)
			ans=(ans*a)%m;
		b=b/2;
		a=(a*a)%m;
	}
	return ans;
}
 
ll modinv(ll k)
{
	return pow(k,MOD-2,MOD);
}

ll ncr(ll n,ll c)
{
    ll t=1;
    c=min(c,n-c);
    for(ll i=1;i<=c;i++)
    {
     	t=(t*(n-i+1))%MOD;
        t=(t*modinv(i))%MOD;
	}
    return t;
}
int main()
{
	ll n;
	cin>>n;
	ll cnt=0;
	ll ans=0;
	while(n>0)
	{
		n=n/2;
		ans=ans+pow(2,cnt);
		cnt++;
	}
	cout<<ans;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define ll long long
int cmp(const void *a, const void *b){return *(long long*)b - *(long long*)a;}
int main(){
    int n;
    scanf("%d",&n);
    ll a[n + 1];
    for(int i = 0; i < n; i++)
        scanf("%lld",a + i);
    qsort(a,n,sizeof(long long),cmp);
    ll ans = 0;
    for(int i = 1; i < n; i++)
        ans += a[i / 2];
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 4680
a,b = map(int,input().split())
S = input()
def crazy(a,b,S):
    num = "0123456789"
    if S[a] != "-":
        return False
    for i in S[:a]:
        if i not in num:
            return False
    for i in S[a + 1:]:
        if i not in num:
            return False
    return True

if crazy(a,b,S):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
#include<stdio.h>
int main(void){
  int N,V[50],C[50],i,s[50],sum;
  scanf("%d",&N);
  for(i=0;i<=N-1;i++){
scanf("%d",&V[i]);
  }
  for(i=0;i<=N-1;i++){
    scanf("%d",&C[i]);
  }
  sum=0;
  for(i=0;i<=N-1;i++){
    s[i]=V[i]-C[i];
    if(s[i]>=0)
      sum+=s[i];
  }
  printf("%d",sum);
  return 0;
}


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

min_num = 10**18
for i in range(1<<N):
    cost = 0
    l = [0]*M
    for j in range(N):
        if (i>>j)&1:
            c, *a = CA[j]
            cost += c
            for k, ak in enumerate(a):
                l[k] += ak
    if all(lj >= X for lj in l):
        min_num = min(min_num, cost)
    # print(l)

print(-1 if min_num == 10**18 else min_num)

Measured memory_bytes: 9216
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define PB push_back
#define SP << " " <<





int main(void){
	ll N;
    cin >> N;
    vector<ll> L;
    rep(i,N){
        ll a;
        cin >> a;
        L.PB(a);
    }

    ll ans = 0;

    sort(all(L));

    

    rep(i,N){
        rep(j,i){
            if(i!=j){
                ll ab = L[i]+L[j];
                for(int k=i+1; k<N; k++){
                    if(ab>L[k]){
                        ans++;
                    }else{
                        break;
                    }
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
n, m = map(int,input().split())

A = [list(map(int,input().split())) for _ in range(n)]
b = [int(input()) for _ in range(m)]

for i in range(n):
    ans = 0
    for j in range(m):
        ans += A[i][j] * b[j]
    print(ans)


Measured memory_bytes: 6020
// Problem : F - Simplified Reversi
// Contest : AtCoder - AtCoder Beginner Contest 179
// URL : https://atcoder.jp/contests/abc179/tasks/abc179_f
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// $%U%$
// Mere bas ka nahi hai
// still i'm trying
// apna time aayega
//
//        .--------------.  
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |  
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'                          		  
//
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll power(ll x,ll y,ll m){if(y==0)return 1;ll p=power(x,y/2,m)%m;p=(p*p)%m;return (y%2==0)?p:(x*p)%m;}
ll nCr(ll n,ll r,ll m){if(r>n)return 0;ll a=1,b=1,i;for(i=0;i<r;i++){a=(a*n)%m;--n;}while(r){b=(b*r)%m;--r;}return (a*power(b,m-2,m))%m;}
#define Test int t;cin>>t;while(t--)
#define endl '\n'
void solve()
{
	ll n,q;
	cin >> n >> q;
	map<ll,ll> v,h;
	map<ll,bool> v1,h1;
	ll ans=(n-2)*(n-2);
	while(q-->0)
	{
		ll a,b;
		cin >> a >> b;
		if(a==1)
		{
			if(v1.find(b)!=v1.end())
			{
				continue;
			}
			v1[b]=1;
			if(h.empty())
			{
				ans-=n-2;
				if(v.find(n)==v.end())
				v[n]=b;
				else
				v[n]=min(v[n],b);
			}
			else
			{
				auto it=h.upper_bound(b);
				if(it==h.end())
				{
					ans-=n-2;
					if(v.find(n)==v.end())
					v[n]=b;
					else
					v[n]=min(v[n],b);
				}
				else
				{
					ll temp=(*it).second;
					ans-=temp-2;
					if(v.find(temp)==v.end())
					v[temp]=b;
					else
					v[temp]=min(b,v[temp]);
				}
			}
		}
		else
		{
			swap(a,b);
			if(h1.find(a)!=h1.end())
			{
				continue;
			}
			h1[a]=1;
			if(v.empty())
			{
				ans-=n-2;
				if(h.find(n)==h.end())
				h[n]=a;
				else
				h[n]=min(h[n],a);
			}
			else
			{
				auto it=v.upper_bound(a);
				if(it==v.end())
				{
					ans-=n-2;
					if(h.find(n)==h.end())
					h[n]=a;
					else
					h[n]=min(h[n],a);
				}
				else
				{
					ll temp=(*it).second;
					ans-=temp-2;
					if(h.find(temp)==h.end())
					h[temp]=a;
					else
					h[temp]=min(a,h[temp]);
				}
			}
		}
		//cout << ans << endl;
	}
	cout << ans << endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//Test
	solve();
	return 0;
}


Measured memory_bytes: 22168
// AOJ 2057 The Closest Circle
// 2018.3.14 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define INF     1e12
#define EPS     1e-7
#define PI180   0.01745329251994329576923690768489		// PI/180

typedef struct { double x, y, r; } T;
T tbl[100002];

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

double getdbl()
{
	int minus = 0;
	double x, y;
	int n = 0, c = getchar_unlocked();
	if (c == '-') minus = 1, c = getchar_unlocked();
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');

	if (c == '.') {
		x = 0;
		y = 1, c = getchar_unlocked();
		do y *= 0.1, x += y * (c & 0xf), c = getchar_unlocked(); while (c >= '0');
		x += n;
	} else x = n;
	if (minus) x = -x;
	return x;
}

int cmp(T *a, T *b)
{
	if (fabs(a->x - b->x) < EPS) {
		if (fabs(a->y - b->y) < EPS) return 0;
		if (a->y < b->y) return -1; return 1;
	}
	if (a->x < b->x) return -1;	return 1;
}

double dist(T *a, T *b)
{
	return hypot(a->x-b->x, a->y-b->y) - a->r - b->r;
}

int main()
{
	int N, angle, i, j, lim;
	double _sin, _cos, x, y, t, ans;

	srand((unsigned)time(NULL));
	while (N = in()) {
		angle = rand() % 44;
		
		_sin = sin(PI180 * angle), _cos = cos(PI180 * angle);
		for (i = 0; i < N; i++) {
			tbl[i].r = getdbl(), x = getdbl(), y = getdbl();
			tbl[i].x = x*_cos - y*_sin;
			tbl[i].y = x*_sin + y*_cos;
		}

		qsort(tbl, N, sizeof(T), cmp);

		ans = INF;
		for (i = 0; i < N; i++) {
			lim = i+6; if (lim > N) lim = N;
			for (j = i+1; j < lim; j++) {
				t = dist(tbl+i, tbl+j);
				if (t < ans) ans = t;
			}
		}
		printf("%.8lf\n", ans);
	}
	return 0;
}


Measured memory_bytes: 6616
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <list>
using namespace std;

string str;
string t;
char mapp[30][30];
int n;
int c[50];

bool dfs(int u){
    c[u]=-1;
    for(int v=0;v<26;++v) if(mapp[u][v]==1){
        if(c[v]<0) return false;
            else if(!c[v] && !dfs(v)) return false;
    }
    c[u]=1;
    return true;
}

bool toposort(){
    memset(c,0,sizeof(c));
    for(int u=0;u<26;++u) if(!c[u])
        if(!dfs(u)) return false;
    return true;
}

int main(){

    while(scanf("%d",&n)!=EOF){
        if(n==0) break;
        cin>>t;

        char flag=0;
        memset(mapp,0,sizeof(mapp));

        if(n==1) { printf("yes\n"); continue; }
        for(int i=2;i<=n;++i){
            cin>>str;   int L1=t.size(),L2=str.size();
            for(int j=0;j<min(L1,L2);++j){
                if(flag) break;
                if(t[j]!=str[j]){
                    //cout<<t[j]<<" "<<str[j]<<endl;
                    if(mapp[str[j]-'a'][t[j]-'a']==1) {flag=1; break;}
                        else { mapp[t[j]-'a'][str[j]-'a']=1; break; }
                }
                if(j+1==L2 && L1>L2) {flag=1; break;}
            }
            t=str;
        }

        //for(int i=0;i<=26;++i)
          //  for(int j=0;j<=26;++j) if(mapp[i][j]==1) cout<<i+'a'-1<<" "<<j+'a'-1<<endl;

        if(flag) printf("no\n");
            else{
                if(toposort()) printf("yes\n"); else printf("no\n");
            }
    }
}

Measured memory_bytes: 1212
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#define maxn 200010
using namespace std;
int n,m,a[200010],b[200010];
map<int,int>mp;
int a1[maxn];int b1[maxn];
int main(){
	scanf("%d",&n);int id=0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&a[i]);
		if(!mp[a[i]])mp[a[i]]=++id;
		a1[mp[a[i]]]++;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&b[i]);
	}
	for(int i=1;i<=m;i++){
		if(!mp[b[i]]){
			printf("NO\n");return 0;
		}
		b1[mp[b[i]]]++;
	}
	for(int i=1;i<=m;i++){
		if(b1[mp[b[i]]]>a1[mp[b[i]]]){
			printf("NO\n");return 0;
		}
	}
	printf("YES\n");
	return 0;
}

Measured memory_bytes: 12800
# -*- coding: utf-8 -*-
# E

from collections import defaultdict
from itertools import accumulate
from collections import deque

N, K = map(int, input().split())
a = list(map(int, input().split()))
a = [a-1 for a in a]
# print(a)

s = [0] + list(accumulate(a))
# print(s)
s = [s % K for s in s]
# print(s)

d = defaultdict(int)
queue = deque()

ans = 0
for idx, s in enumerate(s):
    queue.append(s)
    if idx >= K:
        s_prev = queue.popleft()
        d[s_prev] -= 1

    ans += d[s]
    d[s] += 1
    # print(d)

print(ans)


Measured memory_bytes: 123860
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds; 

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define f first
#define s second
#define sz(x) ll(x.size())
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout << (x) << endl
#define watch2(x,y) cout << (x) << " " << (y) << endl
#define watch3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
 
typedef long long ll;
typedef long double ld; 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
 
const ll mod = 1e9 + 9;
const int inf = 1e9 + 5;
const int N = 1e5 + 5;

signed main(){
    fastio;
    int n,m;
    cin>>n>>m;
    cout<<n*(n-1)/2+m*(m-1)/2;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9

typedef long long ll;

using namespace std;

const ll inf = 1e18;
const ll mod = 1e9+7;
const int N = 1e5+5;
//int a[N];

int main()

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

    int n;

    cin >> n;

    n--;

    int arr[n];

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

        cin >> arr[i];
    }

    int ans = arr[0];

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

        ans += min(arr[i-1], arr[i]);
    }

	ans += arr[n-1];

    cout << ans;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 111111111
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
const ll MOD = 1e9+7;

int n;
int dp[1<<17];
int nw[17];
int ma[17][17];

int rec(int s){
  if(dp[s]!=-1)return dp[s];
  int res=INF;
  for(int i=0;i<n;i++){
	if(s>>i&1){
	  int mc=INF;
	  for(int j=0;j<n;j++){
		if(s>>j&1)mc=min(mc,ma[i][j]);
	  }
	  res=min(res,mc+rec(s-(1<<i)));
	}
  }
  return dp[s]=res;
}

int main(){
  while(cin>>n,n){
  fill_n(dp,1<<16,-1);
  for(int i=0;i<n;i++){
	cin>>dp[1<<i];
	for(int j=0;j<n;j++)
	  cin>>ma[i][j];
	ma[i][i]=dp[1<<i];
  }

  cout<<rec((1<<n)-1)<<endl;
  }
  return 0;
}



Measured memory_bytes: 3328
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
int sum[200010];
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    int A[200010];
    rep(i, N) cin >> A[i];
    rep(i, N) A[i]--;
    rep(i, N) A[i] %= K;
    rep(i, N) {
        sum[i + 1] = (sum[i] + A[i]) % K;
    }
    // rep(i, N + 1) cout << sum[i] << " ";
    // cout << endl;
    map<int, int> mp;
   rep(i, min(N + 1, K)) {
        mp[sum[i]]++;
    }
    int ans = 0;
    rep(i, N) {
        ans += mp[sum[i]] - 1;
        mp[sum[i]]--;
        if (i + K <= N) mp[sum[i + K]]++;
        //cout << ans << endl;
    }
    cout << ans << endl;

    return 0;
}
//  1 4 2 3 5
//  0 3 1 2 4
//0 0 3 4 6 10

//4 2 4 2 4 2 4 2
//  3 1 3 1 3 1 3 1
//0 3 4 7 8 11 12 15 16

//  14 15 92 65 35 89 79 32 38 46
//  6  0  0  1  6  4  1  3  2  3
//0 6  6  6  7  13 17 18 21 23 26 
//  x        x
//     X
//     x  x
//     x        x
//        X
//        x     x
//           x  x
//              x         x

Measured memory_bytes: 15872
h,w,x=map(int,input().split())
c=[list(input()) for i in range(h)]
ans=0
for i in range(2**h):
  gyou=[]
  for j in range(h):
    if (i>>j)&1:
      gyou.append(j)
  for j in range(2**w):
    retu=[]
    cnt=0
    for k in range(w):
      if (j>>k)&1:
        retu.append(k)
    for j in gyou:
      for k in retu:
        if c[j][k]=="#":
          cnt+=1
    if cnt==x:
      ans+=1
print(ans)

Measured memory_bytes: 9232
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main()
{
  int n;cin >> n;
  vector<int> a(n),b(n),c(n);
  rep(i,n) cin >> a[i] >> b[i] >> c[i];
  vector<vector<int>> v(n,vector<int>(3));
  rep(i,n){
    v[i][0] = a[i];
    v[i][1] = b[i];
    v[i][2] = c[i];
  }
  vector<vector<int>> dp(n+1,vector<int>(3,0));
  rep(i,n){
    rep(j,3){
      dp[i+1][ (j + 1) % 3 ] = max( dp[i+1][ (j + 1) % 3 ] , dp[i][j] + v[i][j] );
      dp[i+1][ (j + 2) % 3 ] = max( dp[i+1][ (j + 2) % 3 ] , dp[i][j] + v[i][j] );      
    }
  }

  cout << max( dp[n][0] , max( dp[n][1] , dp[n][2] ) ) << "\n";
  
  return 0;
}


Measured memory_bytes: 12416
n=int(input())
ss=[input() for i in range(n)]
d={}
ans=0
for i in ss:
    a=[c for c in i]
    a.sort()
    a="".join(a)

    if a in d:
        ans+=d[a]
        d[a]+=1
    
    else:
        d[a]=1

print(ans)

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

public class Main {
	
	private static final Scanner IN = new Scanner(System.in);
	
	public static void main(String[] args) {
		
		new Main().run();
	}
	
	private static final int MAX_N = 100000;
	private static final int MAX_Q = 100000;
	
	private int n;
	private int q;
	
	private final int[] p = new int[MAX_N - 1];
	private final boolean[] isQuery = new boolean[MAX_Q];
	private final int[] v = new int[MAX_Q];
	
	private final int[] marked = new int[MAX_N];
	private final int[] value = new int[MAX_N];
	
	private void run() {
		
		while(((n = IN.nextInt()) | (q = IN.nextInt())) != 0) {
			
			for (int i = 0; i < n - 1; i ++) {
				
				p[i] = IN.nextInt() - 1;
			}
			Arrays.fill(marked, 0, n, - 1);
			marked[0] = q;
			for (int i = 0; i < q; i ++) {
				
				isQuery[i] = IN.next().charAt(0) == 'Q';
				v[i] = IN.nextInt() - 1;
				if(!isQuery[i] && marked[v[i]] < 0) {
					
					marked[v[i]] = i;
				}
			}
			
			initialize();
			for (int i = 0; i < n; i ++) if (marked[i] < 0) union(i, p[i - 1]);
			
			long summation = 0;
			for (int i = q - 1; i >= 0; i --) {
				
				if (isQuery[i]) {
					
					summation += value[find(v[i])];
					
				} else if (marked[v[i]] == i) {
					
					union(v[i], p[v[i] - 1]);
				}
			}
			System.out.println(summation);
		}
	}
	
	private final int[] parent = new int[MAX_N];
	private final int[] rank = new int[MAX_N];
	
	private void initialize() {
		
		for (int i = 0; i < n; i ++) {
			
			parent[i] = i;
			rank[i] = 0;
			value[i] = i + 1;
		}
	}
	
	private int find(int x) {
		
		if (parent[x] != x) parent[x] = find(parent[x]);
		return parent[x];
	}
	
	private void union(int x, int y) {
		
		x = find(x);
		y = find(y);
		if (x == y) {
			
			return;
		}
		
		if (rank[x] < rank[y]) {
			
			parent[x] = y;
			
		} else {
			
			parent[y] = x;
			value[x] = value[y];
			
			if (rank[x] == rank[y]) {
				
				rank[x] ++;
			}
		}
	}
}

Measured memory_bytes: 15000
import java.util.*;
public class Main{
  public static void main (String args[]){
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    double[] list = new double[n];
    
    double sum = 0;
    for (int i = 0; i < n; i++){
      list[i] = sc.nextDouble();
      sum += list[i];
    }
    
    long p = Math.round(sum/n);
    
    double ans = 0;
    for (int i = 0; i < n; i++){
      double d = Math.pow(list[i]-p, 2);
      ans += d;
    }
    
    System.out.print((int)ans);
    
  }
}

Measured memory_bytes: 25044