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

using namespace std;

long long MOD=1000000007, Dp[1001][1001], F[1001], t, R, Sa;
long long Pow[1001];

long long Power(long long a, long long k)
{
    t = 1;
    R = 1;
    Sa = a;
    while (k)
    {
        if (k & t)
        {
            k -= t;
            R *= Sa;
            R %= MOD;
        }
        Sa *= Sa;
        Sa %= MOD;
        t <<= 1;
    }
    return R;
}

int main()
{
    //ios::sync_with_stdio(false);
    long long N, A, B, C, D, S=0;
    cin >> N >> A >> B >> C >> D;
    for (int i = 0; i <= 1000; i++)
    {
        for (int y = 0; y <= 1000; y++)
        {
            Dp[i][y] = 0;
        }
    }
    Dp[A-1][0] = 1;
    F[1] = 1;
    F[0] = 1;
    for (int i = 2; i <= 1000; i++)
    {
        F[i] = F[i-1] * i;
        F[i] %= MOD;
    }
    for (int i = 0; i <= 1000; i++)
    {
        Pow[i] = Power(F[i], MOD-2);
    }
    for (int i = A; i <= B; i++)
    {
        for (int y = 0; y <= N; y++)
        {
            Dp[i][y] += Dp[i-1][y];
            if (Dp[i][y] > MOD)
            {
                Dp[i][y] -= MOD;
            }
            for (int u = C; u <= D; u++)
            {
                if (u*i + y > N)
                {
                    break;
                }
                S = Dp[i-1][y];
                S *= F[N-y];
                S %= MOD;
                S *= Pow[N-y-u*i];
                S %= MOD;
                S *= Power(F[i], MOD-u-1);
                S %= MOD;
                S *= Pow[u];
                S %= MOD;
                Dp[i][y+u*i] += S;
                if (Dp[i][y+u*i] > MOD)
                {
                    Dp[i][y+u*i] -= MOD;
                }
            }
        }
    }
    cout << Dp[B][N];
    return 0;
}


Measured memory_bytes: 8064
#include<stdio.h>
#include<string.h>
#define max(a,b)(a>b?a:b)
int dp[3004][3004];
int main()
{
    char s[3002],t[3002],ans[3002];
    scanf("%s",s);
    scanf(" %s",t);
   int n=strlen(s),m=strlen(t),count=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i-1]==t[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    int i=n,j=m;
    while(i!=0 && j!=0)
    {
        if(s[i-1]==t[j-1])
        { ans[count++]=t[j-1];i--;j--;}
        else if(dp[i-1][j] > dp[i][j-1])
            i--;
        else j--;
    }
  for(int i=count-1;i>=0;i--)
    printf("%c",ans[i]);
  printf("\n");
return 0;
}



Measured memory_bytes: 35328
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LLP;

bool check(vector<int> d, int x) {
    int sum = 0;
    int N = d.size();
    if (N == 0) return x == 0;
    rep(i,N) sum += d[i];
    if ((x + sum) % 2 == 1) return false;
    int S = (x + sum) / 2;

    vector<vector<bool>> dp(N, vector<bool>(S + 1, false));
    dp[0][0] = true;
    dp[0][d[0]] = true;
    for (int i = 1; i < N; i++) for (int j = 0; j <= S; j++) {
        if (dp[i - 1][j]) dp[i][j] = true;
        if (j - d[i] >= 0 && dp[i - 1][j - d[i]]) dp[i][j] = true;
    }
    return dp[N - 1][S];
}

int main() {

    string S;
    cin >> S;
    int N = S.length();
    int x, y;
    cin >> x >> y;

    vector<vector<int>> d(2);
    int count = 0;
    bool isX = true;
    bool isInit = true;

    rep(i,N) {
        if (S[i] == 'F') count++;
        else if (isInit) {
            x -= count;
            count = 0;
            isX = false;
            isInit = false;
        } else {
            if (count > 0) {
                if (isX) d[0].push_back(count);
                else d[1].push_back(count);
                count = 0;
            }
            isX = !isX;
        }
    }
    if (isInit) {
        x -= count;
        count = 0;
        isX = false;
        isInit = false;
    }
    if (count > 0) {
        if (isX) d[0].push_back(count);
        else d[1].push_back(count);
    }
    count = 0;
    isX = !isX;

    if (check(d[0], abs(x)) && check(d[1], abs(y))) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 4296
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N=6666;
ll n,k,c[N][N];
ll dp[N];
ll C(ll n,ll m)
{
    if(c[n][m]) return c[n][m];
    if(m==0||n==m) return 1;
    if(m==1) return n;
    return c[n][m]=(C(n-1,m-1)+C(n-1,m))%mod;
}
int main()
{
    scanf("%lld%lld",&n,&k);
    ll s=n-k;
    for(ll i=1;i<=s;i++)
        dp[i]=C(s-1,i-1)%mod;
    for(ll i=1;i<=k;i++)
    {
        ll ans=0;
        if(s==0&&i==1) ans=1;
        ans=(ans+C(k-1,i-1)*dp[i-1])%mod;
        ans=(ans+C(k-1,i-1)*dp[i]%mod*2%mod)%mod;
        ans=(ans+C(k-1,i-1)*dp[i+1]%mod)%mod;
        printf("%lld\n",ans);
    }
}


Measured memory_bytes: 102912
tri = 0
right = 0
acute = 0
obtuse = 0

while True:
    a, b, c = map(int, input().split())
    if a < b:
        a, b = b, a
    if b < c:
        b, c = c, b
    if a < b:
        a, b = b, a   
    
    if (a + b > c) and (b + c > a) and (c + a > b):
        tri += 1
        A = b**2 + c**2 - a**2
        if A > 0:
            acute += 1
        elif A == 0:
            right += 1
        else:
            obtuse += 1
    else:
        break

print(tri, right, acute, obtuse)



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

int main(){
  int N;
  cin>>N;
  vector<int> L (N);
  for(int i=0;i<N;i++){
    cin>>L.at(i);
  }
  //soat
  int temp;
  for(int k=0;k<(N-1);k++){
    for(int i=(N-1);i>k;i--){
      if(L.at(i-1)>L.at(i)){
        temp=L.at(i-1);
        L.at(i-1)=L.at(i);
        L.at(i)=temp;
      }
    }
  }
  int M=0;
  for(int k=0;k<(N-2);k++){
    for(int i=k+1;i<(N-1);i++){
      for(int n=i+1;n<N;n++){
        if((L.at(k)+L.at(i))>L.at(n))
          M++;
      }
    }
  }
  cout<<M<<endl;
}

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

#define ipair pair<int,int>
#define rep(i,n) for(i=0;i<n;i++)
#define repj(i,j,n) for(i=j;i<n;i++)

#define PB(a,i) (a).push_back(i)
#define ALL(a) (a).begin(),(a).end()
#define SIZE(a,n) (a).resize(n)

#define OK(i) cout<<"OK "<<i<<endl
#define Yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define NO cout<<"NO"<<endl

using namespace std;

typedef long long int lli;
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector<int> > Matrix;

int main() {
	Matrix dh, dw;
	int h, w, i, j, k, ans, x, y, c, count, dx1, dy1, dx2, dy2;
	vector<string>s;

	cin >> h >> w;
	SIZE(s, h);
	SIZE(dh, h);
	SIZE(dw, h);
	rep(i, h) {
		cin >> s[i];
		SIZE(dh[i], w);
		SIZE(dw[i], w);
	}

	ans = 0;
	rep(i, h) {
		rep(j, w) {
			if (s[i][j] == '#')continue;
			if (dh[i][j] == 0) {
				count = 1;
				dy1 = i - 1;
				dy2 = i + 1;
				while (dy1 >= 0 && s[dy1][j] == '.') {
					count++;
					dy1--;
				}
				while (dy2 < h && s[dy2][j] == '.') {
					count++;
					dy2++;
				}
				repj(k, dy1 + 1, dy2) {
					dh[k][j] = count;
				}
			}
			if (dw[i][j] == 0) {
				count = 1;
				dx1 = j - 1;
				dx2 = j + 1;
				while (dx1 >= 0 && s[i][dx1] == '.') {
					count++;
					dx1--;
				}
				while (dx2 < w && s[i][dx2] == '.') {
					count++;
					dx2++;
				}
				repj(k, dx1 + 1, dx2) {
					dw[i][k] = count;
				}
			}
			count = dh[i][j] + dw[i][j] - 1;
			ans = max(ans, count);
		}
	}
	cout << ans;

	return 0;
}


Measured memory_bytes: 35712
# pragma GCC optimize("O3")
# include <bits/stdc++.h>
# define maxn 100005
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define sz(x) (int)((x).size())
# define int ll
using namespace std;

map<int,int>m;
int n,M,x,y,viz[1 << 17];
vector<int>vec[1 << 17];

int32_t main(){_
    //freopen("input","r",stdin);
	cin >> n >> M;
	for(int i = 1;i <= M;i++)
	{
		cin >> x >> y;
		vec[x].pb(y);
		vec[y].pb(x);
	}
	queue<int>q;
	q.push(1);
	viz[1] = 1;
	m[1]++;
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		for(auto it : vec[x])
		{
			if(!viz[it])
			{
				q.push(it);
				viz[it] = (-1) * viz[x];
				m[viz[it]]++;
			}
			else if(viz[it] == viz[x]) rc((n * (n - 1)) / 2- M);
		}
	}
	rc((m[-1] * m[1]) - M);
}


Measured memory_bytes: 8576
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define ll long long int
#define MOD ((int)(1e9) + 7)

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

  int arr[3][3];

  for(int i=0; i<3; i++) {
    for(int j=0; j<3; j++) {
      int t;
      cin >> t;
      arr[i][j] = t;
    }
  }

  for(int i=0; i<2; i++) {
    for(int j=0; j<3; j++)
      arr[i][j] -= arr[2][j];
  }

  if(arr[0][0] == arr[0][1] && arr[0][1] == arr[0][2] && arr[1][0] == arr[1][1] && arr[1][1] == arr[1][2])
    cout << "Yes\n";
  else
  {
    cout << "No\n";
  }
  

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,rem,a[4],i=0,d,ans=0;
 cin>>n;
 while(n>0){
     rem=n%10;
    
     a[i]=rem;
      n=n/10;
      i++;
 }
    
 d=a[0];
for(i=1;i<4;i++){
    if(a[i]==d){
        ans++;
        break;
    }
    d=a[i];
}
if(ans==1)
cout<<"Bad";
else
cout<<"Good";
  }

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int cnt=0;
	int length=s.length();
	for(int i=0;i<length/2;i++){
		if(s[i]!=s[length-1-i]){
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
}

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

int gcd(int x, int y);

int main()
{
  int x,y,tmp;
  cin >> x >> y;
  if( x<y ){
    tmp = x;
    x = y;
    y = tmp;
  }                                          
  cout << gcd(x,y) << endl;
  return 0;
}

int gcd(int x, int y)
{
  if(y==0) return x;
  else return gcd(y, x%y);
}

Measured memory_bytes: 1164
def main():
    A, B, C, D = map(int, input().split())
    K = D
    D -= A
    if D <= 0:
        print(min(A, K))
        exit()

    D -= B
    if D <= 0:
        print(A)
    else:
        print(A - D)
    

if __name__ == "__main__":
    main()

Measured memory_bytes: 9180
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        int min = Math.max(0, A+B-N);
        System.out.println(Math.min(A, B) + " " + min);

        System.out.println();
        sc.close();
    }

}


Measured memory_bytes: 23636
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  int a, b;
  cin>>a>>b;
  cout << a * b << endl;
  return 0;
}


Measured memory_bytes: 3680
while True:
    n =	int(raw_input())
    if n == 0: break
    k =	map(int, raw_input().split())
    c0 = c1 = 0
    for	c in k:
	if c ==	1: c1 += 1
	elif c == 0: c0 += 1
    print "NA" if c1 + c0 == n else n - c0 + 1

Measured memory_bytes: 5524
#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 rep(i,a,b) for(i=(a);i<=(b);i++)
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define maxn 100005
#define inf 1e18
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define fr freopen("source.txt","r",stdin),freopen("output.txt","w",stdout)
#define SET(a,b) memset(a,b,sizeof(a))
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
#define ps(x,y) fixed<<setprecision(y)<<x
//template<typename T>
//using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out <<  "(" << a.F << ", " << a.S << ")";
}
 
template<class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out << "[";
	for (auto it = a.begin(); it != a.end(); ++it) {
		if (it != a.begin())
			out << ", ";
		out << *it;
	}
	return out << "]";
}
int main()
{
    boost;
    ll n,i,j,x,t,y,a,b,c;
	cin>>x>>y>>a>>b>>c;
	ll A[a],B[b],C[c];
	for(i=0;i<a;i++) cin>>A[i];
	for(i=0;i<b;i++) cin>>B[i];
	for(i=0;i<c;i++) cin>>C[i];
	sort(A,A+a,greater<ll>());
	sort(B,B+b,greater<ll>());
	sort(C,C+c,greater<ll>());
	priority_queue<ll,vector<ll>,greater<ll>>v1,v2;
	for(i=0;i<x;i++) v1.push(A[i]);
	for(i=0;i<y;i++) v2.push(B[i]);
	for(i=0;i<c;i++){
		if(v1.top()<v2.top()) {
			if(C[i]>v1.top()){
				v1.pop();
				v1.push(C[i]);
			}
		}
		else {
			if(C[i]>v2.top()){
				v2.pop();
				v2.push(C[i]);
			}
		}
	}
	ll ans=0;
	while(!v1.empty()){
		ans+=v1.top();
		v1.pop();
	}
	while(!v2.empty()){
		ans+=v2.top();
		v2.pop();
	}
	cout<<ans;
}

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

const string YES = "YES";
const string NO = "NO";

void solve(long long X){
if(X==3 || X==5 || X==7){
	cout<<YES<<endl;
}else{
cout<<NO<<endl;
}
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long X;
    scanf("%lld",&X);
    solve(X);
    return 0;
}


Measured memory_bytes: 3788
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
set<string> c;
const ll mod=1000000007;
const ll mod2=998244353;
const ll inf=100000000000000000;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
map<char,ll> moji,tmp;
int main(){
  int n;
  cin>>n;
  vector<string> s(n);
  for(int i=0;i<n;i++)cin>>s.at(i);
  for(int i=0;i<s.at(0).size();i++)moji[s.at(0).at(i)]++;
  for(int i=1;i<n;i++){
      for(int j=0;j<s.at(i).size();j++){
              tmp[s.at(i).at(j)]++;
      }
      for(char c='a';c<='z';c++){
          moji[c]=min(moji[c],tmp[c]);
      }
      tmp.clear();
  }
   string ans={};
   for(char c='a';c<='z';c++){
          if(moji[c]>0){
              while(moji[c]--){
                  ans.push_back(c);
              }
          }
      }
      sort(all(ans));
      cout<<ans<<endl;
}


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

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
aa = [i-1 for i in a]
print(sum(aa))


Measured memory_bytes: 9472
#include <bits/stdc++.h>
using namespace std;
 
#define fio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
// #define double long double
// #define mp make_pair
// #define pb push_back
// Upper case English alphabet to lower case ch |= ' ';
// Lower case English alphabet to upper case ch &= '_’ ;
//__builtin_popcount(x)

int INF=(int)1e9+7,t=-1,till=0;
int gcd(int a, int b) { return b!=0 ? gcd(b, a % b) : a; }
// int digits(int n){return floor(log10(n))+1 ;}
// bool ispoweroftwo (int x) { return x && (!(x&(x-1))); }
//vector<int> vis,parent,ti,tout,dis;
// vector<vector<int> > adj;
// map<int,int> vis;
// vector<int> row={-1,1,0,0};
// vector<int> col={0,0,-1,1};
// //map<pair<int,int>,int> dp;
// int n=1;
// int th=0;
// vector<int> dp;

// void dfs(int v){
//     vis[v]=1;
//     for(int x:adj[v]){
//         if(!vis[x])
//             dfs(x);
//         dp[v]=max(dp[v],1+dp[x]);
//     }
// }




signed main(){
    fio;
    int h,w;
    cin>>h>>w;
    char arr[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++) cin>>arr[i][j];
    }
    int dp[h][w];
    dp[0][0]=1;
    for(int i=1;i<h;i++){
        if(arr[i][0]=='#') dp[i][0]=0;
        else dp[i][0]=dp[i-1][0];
    }
    for(int i=1;i<w;i++){
        if(arr[0][i]=='#') dp[0][i]=0;
        else dp[0][i]=dp[0][i-1];
    }
    for(int i=1;i<h;i++){
        for(int j=1;j<w;j++){
            dp[i][j]=0;
            if(arr[i][j]=='#'){
                continue;
            }
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
            dp[i][j]%=INF;
        }
    }
    cout<<dp[h-1][w-1]<<endl;

}


Measured memory_bytes: 9088
import java.util.*;
import java.lang.*;
import java.io.*;

class Main{
	public static void main (String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		while((line = br.readLine()) != null){
			String[] strs = line.split(" ", 2);
			int num1 = Integer.parseInt(strs[0]);
			int num2 = Integer.parseInt(strs[1]);
			int num = num1 + num2;
			String str = String.valueOf(num);
			System.out.println(str.length());
		}
	}
}

Measured memory_bytes: 24268
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		char arr[] = sc.nextLine().toCharArray();
		if(arr[0] != arr[1] && arr[1] != arr[2] && arr[2] != arr[0])
			System.out.println("Yes");
		else System.out.println("No");
	}
}

Measured memory_bytes: 21844
use std::io::{self, BufRead};

pub fn lower_bound<T: Ord>(vec: &[T], val: T) -> usize {
  let mut lo = 0;
  let mut hi = vec.len();
  while hi - lo > 0 {
    let p = (hi + lo) / 2;
    if vec[p] < val {
      lo = p + 1;
    } else {
      hi = p;
    }
  }
  return lo;
}

fn to_index(c: char) -> usize {
  c as usize - 'a' as usize
}

fn main() {
  let stdin = io::stdin();
  let mut lines = stdin.lock().lines();
  let s: Vec<char> = lines.next().unwrap().unwrap().chars().collect();
  let t: Vec<char> = lines.next().unwrap().unwrap().chars().collect();
  let mut cs: Vec<Vec<usize>> = vec![vec![]; 26];
  for i in 0..s.len() {
    let j = to_index(s[i]);
    cs[j].push(i);
  }
  let mut i: usize = 0;
  let mut round: usize = 0;
  for &c in &t {
    let j = to_index(c);
    if cs[j].len() == 0 {
      println!("-1");
      return;
    }
    let mut k = lower_bound(&cs[j], i);
    if k == cs[j].len() {
      k = 0;
      round += 1;
    }
    i = cs[j][k] + 1;
  }
  println!("{}", round * s.len() + i);
}

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

int main(){
	string s; cin >> s;
	ll n = s.size();
	bool r = true;
	rep(i,n){
		if(s[i] != s[n-1-i])r = false;
	}
	rep(i,(n-1)/2){
		if(s[i] != s[(n-1)/2 -1-i])r = false;
	}
	rep(i,(n-1)/2){
		if(s[(n+1)/2 +i] != s[n-1-i])r = false;
	}
	r ? cout << "Yes" << endl : cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner

object MainKt {
	@JvmStatic
	fun main(args: Array<String>) {
		val scanner = Scanner(System.`in`)
		val x = scanner.nextInt()
		val y = scanner.nextInt()
		val z = scanner.nextInt()
		val k = scanner.nextInt()
		val a = LongArray(x)
		val b = LongArray(y)
		val c = LongArray(z)
		for (i in 0 .. x-1) a[i] = scanner.nextLong()
		for (i in 0 .. y-1) b[i] = scanner.nextLong()
		for (i in 0 .. z-1) c[i] = scanner.nextLong()

		a.sort()
		a.reverse()
		b.sort()
		b.reverse()
		c.sort()
		c.reverse()

		val map = mutableMapOf<Long, Int>()
		for (i in 0 .. Math.min(k,x)-1){
			for (j in 0 .. Math.min(k/(i+1), y)-1) {
				for (l in 0 .. Math.min(k/(i+1)/(j+1), z)-1){
					val v = a[i]+b[j]+c[l]
					map[v] = map[v]?.plus(1) ?: 1
				}
			}
		}
		val keys = map.keys.sortedDescending()
		var cnt = 0
		keys.forEach {
			val times = Math.min(k-cnt, map[it]!!)
			for (i in 1..times) println(it)
			cnt += times
		}

	}
}

Measured memory_bytes: 53292
input()
H = [int(x) for x in input().split()]

ans = 0
c = 0
p = 0
s = 0
while any(h != 0 for h in H):
    for i, h in enumerate(H):
        if h > p:
            c = 1
            p = h
            s = i
        elif h < p:
            break
        else:
            c += 1
    ans += 1
    for i in range(c):
        H[s + i] -= 1
    p = 0
print(ans)

Measured memory_bytes: 3064
#include<stdio.h>
int n,A[50];
int solve(int i,int m){
 if(m==0)return 1;
 if(i>=n)return 0;
 return solve(i+1,m)||solve(i+1,m-A[i]);
}
int main(){
 int q,M,i;
 scanf("%d",&n);
 for(i=0;i<n;i++)scanf("%d",&A[i]);
 scanf("%d",&q);
 for(i=0;i<q;i++){
  scanf("%d",&M);
  if(solve(0,M))printf("yes\n");
  else printf("no\n");
 }
 return 0;
}


Measured memory_bytes: 2656
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <functional>

#define mp make_pair
#define pb push_back
#define mes(a,b) memset(a,b,sizeof(a))
#define mes0(a) memset(a,0,sizeof(a))
#define lson l,mid,pos<<1
#define rson mid+1,r,pos<<1|1
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define fi first
#define se second
#define sss(a) a::iterator
#define all(a) a.begin(),a.end()

using namespace std;

typedef double DB;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<long long ,int> pli;
typedef pair<int,long long > pil;
typedef pair<string,int> psi;
typedef pair<long long ,long long > pll;

const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const int maxn = 100000+10;
vector <int > s[1234];
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int n,m,k,t;
    scanf("%d%d",&n,&m);
    scanf("%d",&k);
    int pre=0;
    for (int i=0;i<k;i++){
        scanf("%d",&t);
        for (int j=0;j<t;j++){
            s[pre/m].pb(i+1);
            pre++;
        }
    }
    for (int i=0;i<n;i++){
        if (i&1)reverse(all(s[i]));
        for (int j=0;j<m;j++){
            printf(j?" %d":"%d",s[i][j]);
        }
        puts("");
    }
    return 0;
}


Measured memory_bytes: 384
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,q = inpl()
g = [[]for i in range(n)]
c = [0 for i in range(n)]
seen = [False] * n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for i in range(q):
    a,b = inpl()
    c[a-1] += b
def dfs(node):
    for v in g[node]:
        if seen[v]:
            continue
        c[v] += c[node]
        seen[v] = True
        dfs(v) 
seen[0] = True
dfs(0)
for i in c:
    print(i)

Measured memory_bytes: 237760
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <climits>



using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
const int mod = 1000000007;
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second
#define ednl endl

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")


P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}



int main(){
  int n;cin>>n;
  for(int i = 1; 10 > i; i++){
    for(int j = 1; 10 > j; j++){
      if(i*j == n){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int64_t INF = (1LL << 31) - 1;
const int64_t MAXN = (1 << 17); // 131072

int64_t n, dat[2 * MAXN - 1];

void init(int64_t _n)
{
  n = 1;
  while (n < _n)
  {
    n *= 2; // 要素数をnの冪乗に
  }
  for (int i = 0; i < 2 * n - 1; i++)
  {
    dat[i] = INF;
  }
}

// k番目の値(0-indexed)をaに変更
void update(int64_t k, int64_t a)
{
  k += n - 1;
  dat[k] = a;
  while (k > 0)
  {
    k = (k - 1) / 2;
    dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
  }
}

// [a, b)の最小値を求める
// kは節点の番号、l,rはその節点が[l, r)に対応していることを示す
int64_t query(int64_t a, int64_t b, int64_t k, int64_t l, int64_t r)
{
  if (b <= l || r <= a)
    return INF;
  if (a <= l && r <= b)
    return dat[k];
  int64_t vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
  int64_t vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
  return min(vl, vr);
}

int main()
{
  int64_t N, Q, q, x, y;
  queue<int64_t> ans;
  cin >> N >> Q;
  init(N);
  for (int i = 0; i < Q; i++)
  {
    cin >> q >> x >> y;
    if (q)
    {
      ans.push(query(x, y + 1, 0, 0, n));
    }
    else
    {
      update(x, y);
    }
  }
  while (ans.size())
  {
    cout << ans.front() << endl;
    ans.pop();
  }
}


Measured memory_bytes: 5376
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

vector<int> nums;
int maxSum;
int num;


int main() {
	for(int i = 0; i < 3; i++) {
		scanf("%d", &num);
		nums.push_back(num);
	}
	sort(nums.begin(), nums.end());
	reverse(nums.begin(), nums.end());
	maxSum = nums[0] * 10 + nums[1] + nums[2];
	printf("%d\n", maxSum);
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 256
#!/usr/bin/python


def main():
    while True:
        try:
            num_data = int(raw_input())
            if num_data == 0:
                break

            data = []
            for i in xrange(num_data):
                data.append(int(raw_input()))

            max = max_sum_sequence(data)
            print(max)
        except:
            break


def max_sum_sequence(data):
    sum = [0]
    n = len(data)

    for i in xrange(n):
        sum.append(sum[-1] + data[i])

    mx = - (1 << 30)
    for i in xrange(n):
        for j in xrange(i + 1, n + 1):
            mx = max(mx, sum[j] - sum[i])

    return mx


main()

Measured memory_bytes: 4428
package main

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

func main() {
	r := readLineInt()[0]
	fmt.Println(r*r)
}

/////////////////////////////////////////

func readLineInt() []int {
	result := make([]int, 0)
	for _, v := range strings.Split(readLine(), " ") {
		i, _ := strconv.Atoi(v)
		result = append(result, i)
	}
	return result
}

var reader = bufio.NewReaderSize(os.Stdin, 1e6)

func readLine() string {
	result := make([]byte, 0, 1e6)
	for {
		line, remains, e := reader.ReadLine()
		if e != nil {
			panic(e)
		}
		result = append(result, line...)
		if !remains {
			break
		}
	}
	return string(result)
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
using Graph=vector<vector<int>>;

int main(){
    int n;
    cin>>n;
    vector<long> a(n);
    for (int i=0; i<n; i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    int ans=1;
    int count=0;
    for (int i=1; i<a.size(); i++){
        if(a[i]!=a[i-1]){
            ans++;
            count=0;
        }
        else{
            count++;
            if(count%2==0)ans++;
            else ans--;
        }
    }
    cout<<ans;
    return 0;
}



Measured memory_bytes: 1024
h, w, k = gets.split.map(&:to_i)
s = h.times.map { gets.chomp }

id = {} # [i,j]をkeyとするイチゴの番号
cnt = 1
non_empty_row = Array.new(h, false)
s.each_with_index do |row, i|
  w.times do |j|
    if s[i][j] == "#"
      non_empty_row[i] = true
      id["#{i}, #{j}"] = cnt
      cnt += 1
    end
  end
end

cake = Array.new(h) { Array.new(w, "?") }

# まずは横方向
h.times do |i|
  row = s[i]
  prev = "?"
  w.times do |j|
    if row[j] == "#"
      cake[i][j] = id["#{i}, #{j}"]
      prev = id["#{i}, #{j}"]
    else
      cake[i][j] = prev
    end
  end
  # 右端が?だったらその行にはイチゴがないのでとりあえずぱす
  next if cake[i][-1] == "?"
  next if cake[i][0] != "?"

  first_ichigo_id = -1
  cake[i].each_with_index do |c, j|
    if c != "?"
      first_ichigo_id = j
      break
    end
  end
  # pp first_ichigo_id
  w.times do |j|
    if cake[i][j] == "?"
      cake[i][j] = cake[i][first_ichigo_id]
    end
  end
end



empty_i = non_empty_row.map.with_index{|_, i| i}.select{|i| non_empty_row[i] == false}
nonempty_i = non_empty_row.map.with_index{|_, i| i}.select{|i| non_empty_row[i] == true}
# p empty_i
# p nonempty_i
# pp cake
# 上にある?行に対して上のをコピーする
empty_i.each do |i|
  # iより大きいjをnonempty_iからさがす
  nonempty_i.each do |j|
    if j > i
      cake[i] = cake[j]
      break
    end
  end
end

h.times do |i|
  if cake[i].include?("?")
    cake[i] = cake[nonempty_i[-1]]
  end
end


puts cake.map{|tmp| tmp.join(" ")}


Measured memory_bytes: 16892
#include <stdio.h>
#include <stdlib.h>
#define NIL NULL

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

Node treeMinimum(Node);
Node treeFind(Node,int);
Node treeSuccessor(Node);
void treeDelete(Node);
void insert(int);
void inorder(Node);
void preorder(Node);

Node root;

/*
Node treeMaximum(Node x){
  }
*/

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeFind(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    }
    else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    }
    else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeFind(root, x));
    }
  }

  return 0;
}


Node treeMinimum(Node x){
  while(x->left != NIL) x = x->left;
  return x;
}

Node treeFind(Node u, int k){
  while(u != NIL && k != u->key){
    if(k < u->key) u = u->left;
    else u = u->right;
  }
  return u;
}

Node treeSuccessor(Node x){
  if(x->right != NIL) return treeMinimum(x->right);
  Node y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if(z->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);
  if(y->left != NIL) x = y->left;
  else x = y->right;

  if(x != NIL) x->parent = y->parent;
  
  if(y->parent == NIL) root = x;
  else{
    if(y == y->parent->left) y->parent->left = x;
    else y->parent->right = x;
  }
  if(y != z) z->key = y->key;
  free(y);
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  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 inorder(Node u){
  if(u == NIL) return;
  inorder(u->left);
  printf(" ");
  printf("%d",u->key);
  inorder(u->right);
}

void preorder(Node u){
  if(u == NIL) return;
  printf(" ");
  printf("%d",u->key);
  preorder(u->left);
  preorder(u->right);
}



Measured memory_bytes: 20448
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    int a, b;
    
    cin >> a >> b;
    
    if(a%3==0){
        
        cout << "Possible" << endl;
        
    } else if(b%3==0){
        
        cout << "Possible" << endl;
        
    } else if((a+b)%3==0){
        
        cout << "Possible" << endl;
        
    } else {
        
        cout << "Impossible" << endl;
        
    }
    
    return 0;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
#include <queue>
using namespace std;
typedef long long ll;

int main(){
    int n,m;cin>>n>>m;
    vector<ll> v(m),dist(m-1);
    for(int i=0;i<m;i++)cin>>v[i];
    sort(v.begin(),v.end());
    for(int i=0;i<m-1;i++)dist[i]=v[i+1]-v[i];
    ll sum=accumulate(dist.begin(),dist.end(),0ll);
    sort(dist.rbegin(),dist.rend());
    if(n<=m){
        for(int i=0;i<n-1;i++)sum-=dist[i];
    }
    if(n>m)sum=0;
    cout<<sum;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define f(i, a, n) for( i=a; i<n;i++)
const int N = (int)(1*1e6+10);
int fen[N];
typedef long long ss;
int main()
{
    start;
    int i,j,n,m,k,s=0;
    cin>>n>>k;
    int sh[n];
    f(i,0,n)
    cin>>sh[i];
    sort(sh,sh+n);
    for(i=0;i<k;i++)
        s+=sh[i];
    cout<<s<<endl;
    return 0;
}


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

int main() {
	int N, a[100];
	int x = 0, y = 0;
	int max;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= N; i++) {
		max = 0;
		for (int j = 0; j < N; j++) {
			if (max <= a[j]) {
				max = a[j];
			}
		}
		for (int j = 0; j < N; j++) {
			if (a[j] == max) {
				a[j] = 0;
				break;
			}
		}
		switch (i % 2) {
		case 1: x += max; break;
		case 0: y += max; break;
		}
	}
	cout << x - y << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
double a1[200005],a[200005],n,sum[200005],ans;
long long k;
map <long long, long long> mp;
int main()
{
	cin>>n>>k;
	for (int i=1; i<=n; i++)
	{
		cin>>a[i];
	}	
	for (int i=1; i<=n; i++)
	{
		a1[i]=((a[i]*(a[i]+1))/2)/a[i];
	}
	sum[1]=a1[1];
	for (int i=2; i<=n; i++)
	{
		sum[i]=sum[i-1]+a1[i];
	}
	for (int i=1; i<=n-k+1; i++)
	{
		ans=max(ans,sum[i+k-1]-sum[i-1]);
	}
	std::cout << std::setprecision(10)<<ans <<endl;
}
    

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

vector<int> G[200000];
int N, K;

int dfs(int v, int par, int& ans) {
    int h = 0;
    for (int to : G[v]) {
        if (to == v or to == par) continue;
        h = max(h, dfs(to, v, ans) + 1);
    }
    if (par != 0 and h >= K - 1) {
        h = -1;
        ans++;
    }
    return h;
}

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

    cin >> N >> K;

    int ans = 0;

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

        if (i == 0 and a[i] != 0) {
            a[i] = 0;
            ans++;
        }

        G[i].push_back(a[i]);
        G[a[i]].push_back(i);
    }

    dfs(0, 0, ans);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 14720
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <climits>
#include <map>
#include <set>
const int mod = 1e9 + 7;
const int inf = 1 << 20;
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;


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


Measured memory_bytes: 3128
def ina
  gets.split(' ').map(&:to_i)
end
t1, t2 = ina
a1, a2 = ina
b1, b2 = ina
k1 = t1 * (a1 - b1)
k2 = t2 * (a2 - b2)
stride = k1 + k2
if stride.zero?
  puts 'infinity'
elsif (k1 * stride).positive?
  puts 0
else
  ceil = (k1.abs + (stride.abs - 1)) / stride.abs
  bent = k1 % stride == 0
  res = (ceil - 1) + ceil + (bent ? 1 : 0)
  p res
end

Measured memory_bytes: 14368
# 時間内に解ける
import numpy as np
N, K = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted(list(map(int, input().split())), reverse=True))

left = - 1
right = 10**12

def f(x):
    #return np.maximum(0, A - x//F) .sum()<= K
    return A.sum() - np.minimum(A, x//F).sum()<= K

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)

Measured memory_bytes: 37292
import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(m):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
a=0
for e in it.permutations(range(n)):
    #print(e)
    count=1
    if e[0]!=0:
        break
    
    for i in range(n-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count*=1
        else:
            count*=0
            break
            
    a+=count
    
print(a)

Measured memory_bytes: 9128
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;

class UnionFind {
private:
	vector<int> data;
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }

public:
	UnionFind(int size) : data(size, -1) { }
	bool is_same(int x, int y) { return root(x) == root(y); }
	lint size(int x) { return -data[root(x)]; }

	void unify(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
	}
};

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	
	vector<pair<int, int>> bridge(M);
	for (int i = 0; i < M; i++) cin >> bridge[i].first >> bridge[i].second;

	vector<lint> ans(M);
	lint unconf = (lint)N * (N - 1) / 2, tmp;
	UnionFind land(N);
	for (int i = M - 1; i >= 0; i--) {

		ans[i] = unconf;
		tmp = land.size(bridge[i].first - 1) * land.size(bridge[i].second - 1);
		land.unify(bridge[i].first - 1, bridge[i].second - 1);
		
		// unify前後でtmpの大きさが変化していなかったら既に同根である島をつないだだけなので引かない
		unconf -= tmp == land.size(bridge[i].first - 1) * land.size(bridge[i].second - 1) ? 0 : tmp;

	}

	for (const auto &elem : ans) cout << elem << "\n";

	return 0;
}

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

int dp[1001][1001];
string s, t;
int n, m, a;

int main(){
  cin >> a;
  for(int b = 0; b < a; b++){
    cin >> s >> t;
    for(int i = 0; i <= 1000; i++)
      for(int j = 0; j <= 1000; j++) dp[i][j] = 0;
    m = s.size();
    n = t.size();
    for(int i = 1; i <= m; i++){
      for(int j = 1; j <= n; j++){
        if(s[i - 1] == t[j - 1]){
          dp[i][j] = dp[i-1][j-1] + 1;
        }
      else{
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }  
    cout << dp[m][n] << endl;
  }
  return 0;
}


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

int main() {
	int a,b; cin >> a >> b;
	int aki = 1;
	int count = 0;
	rep(i,21) {
		if(aki>=b) break;
		aki += a-1;
		count ++;
	}
	cout << count << endl;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include "bits/stdc++.h"

#define REP(i,x,y) for(int i=(x);i<(y);i++)
#define RREP(i,x,y) for(int i=(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
//#define int long long

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

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#else
#define eprintf(...)
#define dump(x)
#define debug(x)
#endif

typedef long long ll;

const ll MOD = 1e9 + 7;

class DEqueue {
public:
	void solve(std::istream& in, std::ostream& out) {
	    int N, K;
	    in >> N >> K;
	    vector<int> V(N);
	    REP(i,0,N) in >> V[i];

	    int answer = 0;
	    REP(l,0,K+1) {
	        REP(r,0,K+1) {
	            if (l+r > min(K, N)) break;

	            int pushCount = K - (l+r);
	            vector<int> holds;
	            REP(i,0,l) holds.push_back(V[i]);
	            RREP(i,N-r, N) holds.push_back(V[i]);
	            sort(all(holds), greater<int>());
	            while (!holds.empty() && pushCount > 0) {
	                if (holds.back() >= 0) break;
	                holds.pop_back();
	                pushCount--;
	            }
	            answer = max(answer, accumulate(all(holds), 0));
	        }
	    }
	    out << answer << "\n";
	}
};


int main() {
	DEqueue solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
// Aizu 2350: A-B Problem
// 2017.9.27 bal4u@uu

#include <stdio.h>
#include <string.h>

char a[15], b[15], c[15];
char f[15];					// ??°???????????????????????????????????????
int len;

int getint(char *b, int w)
{
	int n = 0;
	while (w-- > 0) n = 10 * n + (*b++);
	return n;
}

int main()
{
	int i, j, k, m, bw, ans;
	char tmp[15];

	scanf("%s%s%d", a, tmp, &k);
	len = strlen(a); for (i = 0; i < len; i++) a[i] -= '0';
	m = strlen(tmp); for (i = 0; i < m; i++) tmp[i] -= '0';
	memset(b, 0, sizeof(b));
	for (i = 0; i < m; i++) b[i+len-m] = tmp[i];

	memset(f, 0, sizeof(f));
	for (bw = 0, j = len - 1; j >= 0; j--) {
		if (a[j] - bw >= b[j]) bw = 0;
		else bw = 1, f[j-1] = 1;
	}

	ans = 0;
	memset(c, 0, sizeof(c));
	for (m = 0, j = 0; m < k && j < len; j++) {
		if (m == 0) { c[j] = a[j] - b[j]; if (f[j]) m++; }
		else if (f[j-1]) {
			int m1, m2;
			m1 = (10 + a[j] - b[j]) % 10;
			m2 = 9 + a[j] - b[j];
			if (m1 > m2) c[j] = m1, m++;
			else         c[j] = m2;
		} else c[j] = a[j] - b[j];
	}

	for (bw = 0, i = j, j = len - 1; j >= i; j--) {
		if (a[j] - bw >= b[j]) c[j] = a[j] - bw - b[j], bw = 0;
		else c[j] = a[j] - bw + 10 - b[j], bw = 1;
	}

	printf("%d\n", getint(c, len));
	return 0;
}

Measured memory_bytes: 1844
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> 
#define ff first 
#define endl "\n"
#define ss second 
#define li list<int>
#define vi vector<int>
#define ll long long int
#define pii pair<int,int>
#define vii vector<pair<int,int> >
#define mp make_pair
#define pb push_back
#define setbits(x) __builtin_popcountll(x)
#define custom  pair<int,pair<int,int> >
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> pbds; 
#define mod 1000000007
double dp[3001][3001];
double solve(double* arr,int i,int n,int count){
    if(i==n){
        if(n-count>count){
        return 1;
      }
        return 0;
    }
    if(dp[i][count]>-0.9){
        return dp[i][count];
    }
    double one=arr[i]*solve(arr,i+1,n,count);
    double two=(1-arr[i])*solve(arr,i+1,n,count+1);
 //   cout<<one+two<<endl;
    return dp[i][count]=one+two;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    double arr[n];
    memset(dp,-1,sizeof dp);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    double prob= solve(arr,0,n,0);
    cout<<fixed<<setprecision(9)<<prob;
    return 0;
}

Measured memory_bytes: 74360
#include<iostream>
using namespace std;
int main()
{
    int a;
    cin >> a;

    switch (a) {
        case 7:
            cout << "YES" << endl;
            break;
        case 5:
            cout << "YES" << endl;
            break;
        case 3:
            cout << "YES" << endl;
            break;
        default:
            cout << "NO" << endl;
            break;
    }

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int time,plus,a=1;
    scanf("%d",&time);
    scanf("%d",&plus);

for(int n=0;n<time;n++){
if(a<=plus){
a=a*2;
}else{
a=a+plus;
}
}
printf("%d",a);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
 	int n,a,b,c;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		if((a-b-c)%2||b+c>a)
		{
			printf("No\n");
			return 0;
		}	
	}
	printf("Yes\n");
	return 0;
} 

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

int main (void) {
  int W, H, x, y;
  cin >> W >> H >> x >> y;
  cout << fixed << setprecision(10) << (double)W * (double)H / 2 << " " << (x + x == W && y + y == H ? 1 : 0) << endl;
  return 0;
}


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

#define o cout<<"Hello did you expect this?"<<endl;
#define ll long long
#define pb push_back
#define mp make_pair//with Z
#define F first
#define S second

using namespace std;

const int N = 2e5 + 100;
const int mod = 1e9 + 7;

void hey ()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
map<int,ll> was, was2;
int main ()
{
	#define int ll
	hey();
	int n;
	cin >> n;
	int a[n + 1];
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int x = i - a[i];
		int x2 = i + a[i];
		was[x]++;
		was2[x2]++;	
	}
	for (int i = 1; i <= n; i++)
	{
		int x = i - a[i];
		int x2 = i + a[i];
		ans += (long long)was[x] * was2[x];
		ans += (long long)was[x2] * was2[x2];
		was[x] = 0;
		was2[x] = 0;
		was[x2] = 0;
		was[x2] = 0;
	}
	cout << ans;
}	




Measured memory_bytes: 50532
n = int(input())
a = list(map(int, input().split()))
iseven=(n%2==0)

if n==2:
    print(max(a))
    exit()
dp = [[-float("inf") for _ in range(3)] for _ in range(n)]
dp[0][0]=a[0]
dp[1][1]=a[1]
if n>2:
    dp[2][2]=a[2]

for i in range(n):
    for k in range(3):
        if i+2<n:
            dp[i+2][k] = max(dp[i+2][k], dp[i][k] + a[i+2])
        if k<=1 and i+3<n:
            dp[i+3][k+1] = max(dp[i+3][k+1], dp[i][k] + a[i+3])
        if not iseven and k==0 and i+4<n:
            dp[i+4][k+2] = max(dp[i+4][k+2], dp[i][k] + a[i+4])


if iseven:
    ans=max([dp[-1][0],dp[-1][1]])
else:
    ans=max([dp[-3][0],dp[-2][1],dp[-1][2]])
print(ans)

Measured memory_bytes: 140688