akhauriyash/Code-Regression huggingface dataset:
'''
Created on 2020/09/26

@author: harurun
'''
#UnionFind(要素数)で初期化
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        #parents 各要素の親番号を格納するリストを返す

    #要素xが属するグループを返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    #要素xとyが属するグループを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    #要素xが属するグループのサイズ
    def size(self, x):
        return -self.parents[self.find(x)]

    #要素xとyが同じグループに属するかどうか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    #要素xが属するグループを返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    #すべての根の要素
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    #グループの数
    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N,M=map(int,pin().split())
  ans=0
  uf=UnionFind(N)
  for i in range(M):
    A,B=map(int,pin().split())
    uf.union(A-1, B-1)
  print(uf.group_count()-1)
  return 
main()


Measured memory_bytes: 12944
#include <stdio.h>
#include <math.h>
#include <string.h>
typedef long long ll;
int main(int argc,int *argv[])
{
	char s[4];
	scanf("%s",s);
	if(s[0]==s[1] && s[0]==s[1] && s[1]==s[2])
		printf("No");
	else
		printf("Yes");
		return 0;
}


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

typedef long long int ll;
typedef vector<long long>lve;
typedef vector<pair<ll,ll> > lvp;
typedef vector<vector<int> > ivve;

#define sp         ' '
#define endl       '\n'
#define F          first
#define S          second
#define pp         pop_back`
#define pb         push_back
#define mp         make_pair 
#define GCD(x,y)   __gcd(x,y)
#define lb         lower_bound
#define up         upper_bound
#define setp       setprecision
#define bs         binary_search
#define all(x)     x.begin(),x.end()
#define LCM(x,y)   ((x*y)/__gcd(x,y))
#define spc(x)     cout<<fixed<<setp(x)

const   long long  inf = 1e18;
const   long long  cs =  200005;
const   long long  mod = 1000000007;
const   double     PI =  2 * acos(0.0);
void solve()
{
    ll t,n,m,a,b,c,d,e,i,j,k,x,y,z,cnt=0,cnt1=0;
    bool flag = false;  

    cin>>n;
    cout<<n*n<<endl;

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

    // freopen ("input.txt","r",stdin);
    // freopen ("output.txt","w",stdout);

    // int32_t tc;
    // cin>>tc;
    // while(tc--)
    solve();

    return 0;
}


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

public class Main {
    static final Scanner sc  = new Scanner(System.in);
    static final int MOD = (int) 1E9 + 7;
    static final int INF = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        int N = nint();
        double[] p = ndoubles(N, 1, 0);
        int K = N*2 + 1;
        double[][] dp = new double[K+2][N+1];
        dp[N+1][0] = 1;
        
        for (int n = 1; n <= N; n++) {
            for (int k = 1; k <= K; k++) {
                dp[k][n] += dp[k-1][n-1] * p[n];
                dp[k][n] += dp[k+1][n-1] * (1 - p[n]);
            }
        }
        
        double ans = 0;
        for (int k = N+1; k <= K; k++) {
            ans += dp[k][N];
        }
        System.out.println(ans);
    }
    
    
    static long max(long... longs) {
        return Arrays.stream(longs).max().getAsLong();
    }
    
    static long min(long... longs) {
        return Arrays.stream(longs).min().getAsLong();
    }

    private static long nlong() {
        return sc.nextLong();
    }

    private static int nint() {
        return sc.nextInt();
    }

    private static String nstr() {
        return sc.next();
    }

    private static char[] nchars() {
        return sc.next().toCharArray();
    }

    private static char[] nchars(int padL, int padR) {
        char[] temp = sc.next().toCharArray();
        char[] ret = new char[temp.length + padL + padR];
        System.arraycopy(temp, 0, ret, padL, temp.length);
        return ret;
    }

    private static int[] nints(int n) {
        return nints(n, 0, 0);
    }

    private static int[] nints(int n, int padL, int padR) {
        int[] a = new int[padL + n + padR];
        for (int i = 0; i < n; i++)
            a[padL + i] = nint();
        return a;
    }
    
    private static double[] ndoubles(int n) {
        return ndoubles(n, 0, 0);
    }
    
    private static double[] ndoubles(int n, int padL, int padR) {
        double[] d = new double[n + padL + padR];
        for (int i = 0; i < n; i++) {
            d[padL + i] = sc.nextDouble();
        }
        return d;
    }

    private static char[][] nchars2(int h, int w) {
        return nchars2(h, w, 0);
    }

    private static char[][] nchars2(int h, int w, int pad) {
        char[][] a2 = new char[h + pad * 2][w + pad * 2];
        for (int i = 0; i < h; i++)
            System.arraycopy(nchars(), 0, a2[pad + i], pad, w);
        return a2;
    }
}


Measured memory_bytes: 245504
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(ll i##_len=(n) ,i=i##_len-1;i>=0;--i)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define fe(vec,lambda) std::for_each(vec.begin(), vec.end(), lambda );
#define printd(val) std::cout<< #val" = " <<val<<"\n";
#define printv(val) std::for_each(val.begin(),val.end(),[](auto x){cout<<x<<"\n";});
#define lim 1000000007ll
#include<bits/stdc++.h>
using ll = long long;
using pii = std::pair<ll,ll>;
using namespace std;
template<class T>T chmin(T& a,T b){if(a>b){a^=b;b^=a;a^=b;return 1;}return 0;}
template<class T>T chmax(T& b,T a){if(a>b){a^=b;b^=a;a^=b;return 1;}return 0;}
template <class T> T gcd(T a, T b){if (a < b) {a ^= b;b ^= a;a ^= b;} return b ? gcd(b, a % b) : a;}
template <class T> T lcm(T a, T b){return a * b / gcd(a, b);}
inline bool operator<(const pii &lhs,const pii &rhs){return(lhs.second<rhs.second);}
template<class T> vector<pair<T,T>> duplicator(const vector<T>& input){vector<pair<T,T>> out(input.size()-1);rep(i,input.size()-1){out[i].first =input[i  ];out[i].second=input[i+1];}return(out);}
vector<char> String_to_vector_char(const string& input){vector<char> out(input.size());rep(i,input.size()){out[i]=input[i];}return out;}


ll a,b,c;
map<ll,ll>v;
void input(){
    cin>>a>>b>>c;
    v[a]=1;
    v[b]=1;
    v[c]=1;
}
void src(){
    cout<< v.size();
}

int main(int argc,char* argv[]){
    ios::sync_with_stdio(false);
    //ifstream in( argv[1] ); cin.rdbuf(in.rdbuf());
    input();
    src();    
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args){
		FastScanner sc = new FastScanner(System.in);
		int N = sc.nextInt();
		int max = sc.nextInt();
		int count = 1;
		int height;
		for (int i=1;i<N;i++) {
			height = sc.nextInt();
			if (height >= max) {
				count++;
				max = height;
			}
		}
		System.out.println(count);

	}

}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
     }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    }
}

Measured memory_bytes: 21716
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> v(n);
  
  for (int i=0; i<n; i++) {
    cin >> v[i];
  }

  sort(v.begin(), v.end(), greater<int>());

  int A=0, B=0;
  for (int i=0; i<n; i++) {
    if (i%2==0) A+=v[i];
    else B+=v[i];
  }

  printf("%d\n", A-B);
  return 0;
}

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

int n;
int64_t s[100000 + 1];

int binarysearch(int64_t t){
    int left = 0, right = n, mid;
    while(left < right){
        mid = (left + right) / 2;
        if(s[mid] == t) return 1;
        else if(s[mid] > t) right = mid;
        else left = mid + 1;
    }
    return 0;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> s[i];
    int q;
    cin >> q;
    int ans = 0;
    for(int i = 0; i < q; i++){
        int64_t t;
        cin >> t;
        ans += binarysearch(t);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3784
import java.util.Scanner;

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

    String[] string_array = scanner.next().split("");

    System.out.println(Integer.parseInt(string_array[0])+Integer.parseInt(string_array[1])+Integer.parseInt(string_array[2]));
  }
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cout << H << " "; debug_out(T...); }
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

struct V {
  ll x, y, h;
};

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n;
  cin >> n;
  vector<V> a(n);
  rep(i,n) {
    V v;
    cin >> v.x >> v.y >> v.h;
    a[i] = v;
  }
  for (ll cx = 0; cx <= 100; ++cx) {
    for (ll cy = 0; cy <= 100; ++cy) {
      bool ok = true;
      ll H = -1;
      rep (i,n) {
        if (a[i].h > 0) {
          H = a[i].h + llabs(a[i].x - cx) + llabs(a[i].y - cy); //初期化
          break;
        }
      }
      rep(i,n) {
        if (a[i].h != max(H - llabs(a[i].x - cx) - llabs(a[i].y - cy), 0LL)) {
          ok = false;
          break; 
        }
      }
      if (ok) {
        cout << cx << " " << cy << " " << H << endl;
        return 0;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<list>
using namespace std;
#define MAX 8

int fact(int n){
    int f=1;
    for (int i=0; i<n; i++){
        f *= i+1;
    }
    return f;
}

int order(int a[], int n){
    int ord = 1, i, pos;
    list<int> lis;
    for(i=0; i<n; i++) lis.push_back(i+1);
    
    for(i=0; i<n-1; i++){
        pos = 1;
        for(auto it=lis.begin(); it!=lis.end(); it++){
            // cout << *it << " ";
            if(*it == a[i]){
                // cout << "pos" << pos <<endl;
                break;
            } 
            pos++;
        }
        lis.erase(next(lis.begin(), pos-1));
        ord += (pos-1) * fact(n-i-1);
        pos = 1;
    }

    return ord;
}


int main(){
    int i, n, p[MAX], q[MAX];
    cin >> n;
    for(i=0; i<n; i++) cin >> p[i];
    for(i=0; i<n; i++) cin >> q[i];

    int a, b;
    a = order(p, n);
    b = order(q, n);
    // cout << a << endl;
    // cout << b << endl;
    cout << abs(a-b) << endl;

}



Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines  

from collections import Counter

N = int(input())
S = [input().rstrip().decode() for _ in range(N)]
S = Counter(S)
max_S = max(S.values())

name = sorted([k for k, v in S.items() if v == max_S])
print(*name, sep="\n")


Measured memory_bytes: 35556
import sys; sys.setrecursionlimit(50000)
input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

result = []
for x in range(X):
    for y in range(Y):
        for z in range(Z):
            if x * y * z > K: break
            result.append(A[x]+B[y]+C[z])
result.sort(reverse=True)
for i in range(K):
    print(result[i])


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

#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define endl "\n"
#define int long long

const int N = 2005;

int n;
int a[N], cache[N][N];
pair<int, int> b[N];

int dp(int idx, int i, int j)
{
    if (idx > n)
        return 0;
    int &ans = cache[idx][i];
    if (ans != -1)
        return ans;
    ans = abs(i - b[idx].second) * b[idx].first + dp(idx + 1, i + 1, j);
    ans = max(ans, abs(j - b[idx].second) * b[idx].first + dp(idx + 1, i, j - 1));
    return ans;
}

int32_t main()
{
    IOS;
    memset(cache, -1, sizeof(cache));
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i].first = a[i];
        b[i].second = i;
    }
    sort(b + 1, b + n + 1);
    reverse(b + 1, b + n + 1);
    int ans = dp(1, 1, n);
    cout << ans;
    return 0;
}


Measured memory_bytes: 35264
#include<bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
#define lcm( a, b ) ((a)/__gcd(a,b)*(b))
#define MP make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<int, P> i_P;
typedef pair< LL, LL > L_P;

const int INF = INT_MAX;
const int MIN = INT_MIN;
const LL LINF = LLONG_MAX;
const int MOD = 1000000000 + 7;
const int SIZE = 300005;

void update( L_P segtree[], int pos );

LL b;

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

    LL n, r, l;
    cin >> n >> r >> l;
    b = 1;
    int bi = 1;
    while( b < n ) {
        b *= 2;

    }

    b = b * 2 + 1;
    LL res[SIZE] = {};
    L_P segtree[SIZE];
    for( int i = 0; i <= b; ++i ) {
        segtree[i].F = 0;
        segtree[i].S = 1;

    }
    for( int i = b / 2, j = 1; i <= b / 2 + n; ++i, ++j ) {
        segtree[i].S = j;

    }
    for( int i = b / 2 + n + 1; i <= b; ++i ) {
        segtree[i].F = MIN;

    }

    int team = 1;
    int ltime = 0;
    for( int i = 0; i < r; ++i ) {
        LL d, t, x;
        cin >> d >> t >> x;
        res[team] += t - ltime;
        ltime = t;

        //cout << segtree[b / 2 + d - 1].S << endl;
        segtree[b / 2 + d - 1].F += x;
        update( segtree, ( d + b / 2 - 1 ) / 2 );
        team = segtree[1].S;
        //cout << segtree[d + b / 2 - 1].F << endl;

    }
    res[team] += l - ltime;
    LL mx = 0, mxpos = 0;
    for( int i = 1; i <= n; ++i ) {
        if( mx < res[i] ) {
            mxpos = i;
            mx = res[i];

        }
    }
    cout << mxpos << endl;

    return 0;
}

void update( L_P segtree[], int pos ) {
    if( segtree[pos * 2].F < segtree[pos * 2 + 1].F ) {
        segtree[pos].F = segtree[pos * 2 + 1].F;
        segtree[pos].S = segtree[pos * 2 + 1].S;

    } else {
        segtree[pos].F = segtree[pos * 2].F;
        segtree[pos].S = segtree[pos * 2].S;

    }
    if( pos == 1 ) return;

    update( segtree, pos / 2 );
    return;

}



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

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    for (int i = 0; i < M; i++) cin >> A[i];
    cout << max(N - accumulate(A.begin(), A.end(), 0), -1) << endl;
    return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ac=0,per=0;
int p[100010],ad[100010];
string s[100010];
bool t[100010];
int main() {
	ios::sync_with_stdio(false);
	memset(t,0,sizeof(t));
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>p[i]>>s[i];
	for(int i=1;i<=m;i++) {
		if(t[p[i]]) continue;
		if(s[i]=="AC") ac++,t[p[i]]=true,per+=ad[p[i]];
		else ad[p[i]]++;
	}
	cout<<ac<<' '<<per;
	return 0;
}

Measured memory_bytes: 6656
#include<iostream>

#define	mp	make_pair
#define	pb	push_back

using namespace std;

typedef	pair<int,int>	pii;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int main(){
	char maze[30][31],nextmaze[30][30];
	int chk[30][30];

	for(int w,h;cin>>w>>h,w;){
		for(int i=0;i<h;i++)	cin>>maze[i];

		int man=0;
		for(int i=0;i<h;i++)for(int j=0;j<w;j++){
			if(maze[i][j]!='.' && maze[i][j]!='X' && maze[i][j]!='#'){
				if     (maze[i][j]=='E')	maze[i][j]=0;
				else if(maze[i][j]=='N')	maze[i][j]=1;
				else if(maze[i][j]=='W')	maze[i][j]=2;
				else if(maze[i][j]=='S')	maze[i][j]=3;
				man++;
			}
		}

		int ans=-1;
		for(int t=0;t<=180;t++){
			if(man==0){ ans=t; break; }

			for(int i=0;i<h;i++)for(int j=0;j<w;j++)	chk[i][j]=777;

			for(int i=0;i<h;i++)for(int j=0;j<w;j++){
				if(maze[i][j]>3)	continue;
				for(int k=0,l=(maze[i][j]+3)%4;k<4;k++,l=(l+1)%4){
					int y=i+dy[l],x=j+dx[l];
					if(0<=y && y<h && 0<=x && x<w && (maze[y][x]=='.' || maze[y][x]=='X')){
						maze[i][j]=l;
						chk[y][x]=min(chk[y][x],(l+2)%4);
						break;
					}
				}
			}

			for(int i=0;i<h;i++)for(int j=0;j<w;j++)	nextmaze[i][j]=maze[i][j];

			for(int i=0;i<h;i++)for(int j=0;j<w;j++){
				if(maze[i][j]>3)	continue;
				int y=i+dy[maze[i][j]],x=j+dx[maze[i][j]];
				if(0<=y && y<h && 0<=x && x<w && chk[y][x]==(maze[i][j]+2)%4){	// movable
					if(maze[y][x]=='.')	nextmaze[y][x]=maze[i][j];
					else if(maze[y][x]=='X')	man--;
					else{while(1);}
					nextmaze[i][j]='.';
				}
			}

			for(int i=0;i<h;i++)for(int j=0;j<w;j++)	maze[i][j]=nextmaze[i][j];
		}

		if(~ans)	cout<<ans<<endl;
		else		cout<<"NA"<<endl;
	}

	return 0;
}

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

public class Main {

	final static long MOD = 1000000007;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static void main(String[] args) throws Exception {

		int N=nextInt();
		int M=nextInt();

		int[] G = new int[N+1];
		Arrays.fill(G, 0);
		for(int i=0;i<M;i++){
			int[] p = nextInts();
			G[p[0]-1]++;
			G[p[1]]--;
		}

		for(int i=0;i<N;i++){
			G[i+1]+=G[i];
		}
		long ans = 0;
		for(int i=0;i<N;i++){
			if(G[i]==M)
				ans++;
		}
		System.out.println(ans);
	}


	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}


}


Measured memory_bytes: 47660
#include <algorithm>
#include <vector>
#include <cmath>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <queue>
#include <numeric>
#include <iostream>

using namespace std;


int main() {

    long X;
    cin >> X;

    long sum = 0;
    long i = 0;
    while (sum < X) {
        i += 1;
        sum = (i * (i + 1)) / 2;
    }

    cout << i << "\n";

    return 0;
}

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

using namespace std;

int main()
{

    int acute = 0;
    int obtuse = 0;
    int right = 0;

    while (true) {
        int a, b, c;
        cin >> a >> b >> c;

        auto checkTriangle = [](int a, int b, int c) { return a < (b + c); };
        auto angle = [](int a, int b, int c) {
            auto x = static_cast<double>(b * b + c * c - a * a) / (2 * b * c);
            return acos(x);
        };
        auto isObtuse = [](double theta) {
            return M_PI_2 < theta && theta < M_PI;
        };
        auto isRight = [](double theta) {
            return abs(theta - M_PI_2) < 0.0001;
        };

        if (checkTriangle(a, b, c) && checkTriangle(b, a, c) &&
            checkTriangle(c, a, b)) {
            auto theta1 = angle(a, b, c);
            auto theta2 = angle(b, a, c);
            auto theta3 = angle(c, a, b);
            if (isRight(theta1) || isRight(theta2) || isRight(theta3)) {
                right += 1;
            }
            else if (isObtuse(theta1) || isObtuse(theta2) || isObtuse(theta3)) {
                obtuse += 1;
            }
            else {
                acute += 1;
            }
        }
        else {
            cout << (acute + obtuse + right) << " " << right << " " << acute
                 << " " << obtuse << endl;
            break;
        }
    }
}


Measured memory_bytes: 3216
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtTest.HUPC_day2
{
    class B
    {
        static void Main(string[] args)
        {
            Method(args);
        }

        static void Method(string[] args)
        {
            int[] hw = ReadInts();
            int h = hw[0];
            int w = hw[1];
            List<int[]> poses = new List<int[]>();
            List<int> plus = new List<int>();
            List<int> minus = new List<int>();
            for(int i = 0; i < h; i++)
            {
                string s = Read();
                for(int j = 0; j < w; j++)
                {
                    if (s[j] == 'B')
                    {
                        plus.Add(i + j);
                        minus.Add(i - j);
                    }
                }
            }
            plus.Sort();
            minus.Sort();

            WriteLine(Max(plus[plus.Count - 1] - plus[0],
                minus[minus.Count - 1] - minus[0]));
        }

        private static string Read() { return ReadLine(); }
        private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}



Measured memory_bytes: 18044
import sys
from statistics import *
from collections import *
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
li = deque(na())
li.appendleft(0)
li.append(0)
s = 0
for i in range(len(li) - 1):
    s += abs(li[i + 1] - li[i])
for i in range(1, len(li) - 1):
    print(s - abs(li[i+1] - li[i]) - abs(li[i] - li[i-1]) + abs(li[i+1] -li[i-1]))

Measured memory_bytes: 16328
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
bool vis[maxn];
vector<int>graph[maxn];
int __in_deg[maxn];
int dist[maxn];
int dfs(int x){
	if(!vis[x])
		vis[x]=true;
	for(auto it:graph[x]){
		dist[it]=max(dist[it],dist[x]+1);
		--__in_deg[it];
		if(__in_deg[it]==0)
			dfs(it);
	}
}
int main(){

	//freopen("Z:\\LPU\\FYear\\Practice_Contest_CF_CL\\inputf.in","r",stdin);
	//freopen("Z:\\LPU\\FYear\\Practice_Contest_CF_CL\\outputf.in","w",stdout);
	int n,m;
	cin>>n>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		graph[a].push_back(b);
		++__in_deg[b];
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]&&__in_deg[i]==0){
			dfs(i);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dist[i]);
	}
	cout<<ans;
}

Measured memory_bytes: 9728
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int main(void) {
	while (1) {
		int sum_s = 0, sum_t = 0;
		cin >> n >> m;
		vector<int> s(n), t(m);
		if (n == 0 && m == 0) break;
		for (int i = 0; i < n; i++) cin >> s[i], sum_s += s[i];
		for (int i = 0; i < m; i++) cin >> t[i], sum_t += t[i];
		sort(s.begin(),s.end());
		sort(t.begin(),t.end());
		int tmp1,tmp2;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				tmp1 = sum_s - s[i] + t[j];
				tmp2 = sum_t + s[i] - t[j];
				if (tmp1 == tmp2) {
					cout << s[i] << " " << t[j] << endl;
					i = n,j = m;
				}
				if(i == n-1 && j == m-1){
				    cout << -1 << endl;
				    break;
				}
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3056
#include <iostream>
#include <string>
#include <unordered_set>

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

	std::unordered_set<std::string> set;

	std::string s;
	for (int i = 0; i < n; ++i) {
		std::cin >> s;

		set.insert(s);
	}

	std::cout << set.size() << std::endl;
}

Measured memory_bytes: 17616
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
using namespace std;

void solve(){
  int n; cin >> n;
  map<int, int> mp;
  for(int i = 0; i < n; i++){
    int x; cin >> x;
    mp[x]++;
  }
  unsigned long long int sum = 0;
  for(auto itr = mp.begin(); itr != mp.end(); itr++){
    if(itr->first > itr->second){
      sum += itr->second;
    }
    else if(itr->first < itr->second){
      sum += itr->second - itr->first;
    }
  }
  cout << sum << endl;
  return;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 4736
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int N;
long long a[100001];
const long long Ma = 1000000000000000000;
long long ans = 1;
int main(){
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> a[i];
		if(a[i] == 0){cout << "0" << endl; return 0;}
	}
	for(int i=0;i<N;i++){
		if( Ma/ans< a[i]) {cout << "-1" << endl; return 0;}
		else ans*=a[i];
	}
	cout << ans << endl;
	return 0;

}

Measured memory_bytes: 4348
#include <bits/stdc++.h>
						using namespace std;
						#define pll pair<ll,ll>
						typedef long long ll;
						#define mod 51123987
						#define fi first
						#define se second
						#define mp make_pair
						#define pb push_back
						#define INF 1e15
						const int N=2e5+5;
						const int LG=21;
						
						int main()
						{
							ll n;
							cin>>n;
							ll m;
							cin>>m;
							vector<ll> v(n+1);
							for(ll i=0;i<=n;i++)
								v[i]=-1;
							for(ll i=0;i<m;i++)
							{
								ll s,c;
								cin>>s>>c;
								if(v[s]!=-1 && v[s]!=c)
								{
									cout<<-1;
									exit(0);
								}
								v[s]=c;
							}
							ll i;
							for(i=0;i<1000;i++)
							{
								vector<ll> res;
								ll k=i;
								if(i==0)
									res.pb(0);
								while(k)
								{
									res.pb(k%10);
									k=k/10;
								}
								reverse(res.begin(),res.end());
								if(res.size()!=n)
									continue;
								int f=1;
								for(ll j=1;j<=n;j++)
								{
									if(v[j]!=-1)
									{
										if(res[j-1]!=v[j])
											{
												f=0;
												
											}
											
									}
									
								}
								if(f)
									break;
							}
							if(i==1000)
								cout<<-1;
							else
								cout<<i;
						}


Measured memory_bytes: 256
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int array[] = new int [n];
		for (int i = 0; i < n; i++) {
			int num = sc.nextInt();
			array[i]  =num;
		}

		for (int i = n - 1; i >= 0; i--) {
			if(i == 0){
				System.out.println(array[i]);
			}else{
				System.out.print(array[i] + " ");
			}
		}
		sc.close();

	}
}


Measured memory_bytes: 26376
/* ex 3-2
    kas056 */
#include <stdio.h>
int main(void){
    int N , R;
 
    // Nの読み込み
    scanf("%d", &N);
    //余り(remain)で考える
    R = N % 10;//以下条件によって場合分け（「または」を使うとき）
    //remainが2,4,5,7,9の場合
    if (R==2 || R==4 || R==5 || R==7 || R==9){
        printf("hon\n");
    }
    //remainが0,1,6,8の場合
    else if (R==0 || R==1 || R==6 || R==8){
        printf("pon\n");
    }
    //remainが3の場合
    else{
        printf("bon\n");
    }
    return 0;
}

Measured memory_bytes: 1616
import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		String sa = scan.next();
		String sb = scan.next();
		String sc = scan.next();

		char flag = 'a';

		int a_count = 0, b_count = 0, c_count = 0;

		while (true) {
			if (flag == 'a') {
				if (a_count == sa.length()) {
					System.out.print("A");
					break;
				}
				flag = sa.charAt(a_count);
				a_count++;
			}

			if (flag == 'b') {
				if (b_count == sb.length()) {
					System.out.print("B");
					break;
				}
				flag = sb.charAt(b_count);
				b_count++;
			}

			if (flag == 'c') {
				if (c_count == sc.length()) {
					System.out.print("C");
					break;
				}
				flag = sc.charAt(c_count);
				c_count++;
			}
		}

	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define dbg(x) cerr<<#x" = "<<x<<endl
#define rep(i,a,b) for(register int i=(a),i##_end=(b);i<=i##_end;++i)
#define per(i,a,b) for(register int i=(a),i##_st=(b);i>=i##_st;--i)
#define rpg(i,x) for(register int i=fir[x];i;i=e[i].nxt)
#define ull unsigned long long
#define fi first
#define se second
#define pb push_back
#define bin(i) (1<<i)
#define cla(x) memset(x,0,sizeof x)
#define meminf(x) memset(x,127,sizeof x)
typedef pair<int,int> pa;
typedef long long LL;
const int INF = 0x7fffffff;
const int oo = 0x3f3f3f3f;
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
    return *p1++;
}
//#define  getchar() nc()
inline int rd()
{
    int x = 0 , f = 1; char CH = getchar();
    while(CH<'0'||CH>'9') {if(CH=='-')f=0;CH=getchar();}
    while(CH>='0'&&CH<='9') {x=(x<<3)+(x<<1)+(CH-48);CH=getchar();}
    return f ? x : -x;
}
LL f[2050];
int main()
{
#ifdef	iloi
	freopen("test.txt","r",stdin);
#endif
	f[0]=2;
	f[1]=1;
	for(int i=2;f[i-1]>0;i++)
		f[i]=f[i-1]+f[i-2];
	int n=rd();
	cout<<f[n]<<endl;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <vector>
#include <assert.h>

using namespace std;

const int MAX_N = 5000;
int n, m;
int a[MAX_N];
vector<int>win[MAX_N];
int listw[MAX_N];
vector<int>listj;

int main()
{
	scanf("%d",&n);
	scanf("%d",&m);
	memset(a,0,sizeof(int) * n);
	for (int i = 0; i < m; ++i)
	{
		int p, q;
		scanf("%d %d",&p,&q);
		++a[q - 1];
		win[p - 1].push_back(q - 1);
	}
	for (int i = 0; i < n; ++i)
	{
		int first = 0;
		for (int j = 0; j < n; ++j)
		{
			if (a[j] == 0)
			{
				first = j;
				a[j] = -1;
				break;
			}
		}
		listw[first] = i + 1;
		listj.push_back(first);
		for (int lose : win[first])
		{
			--a[lose];
		}
	}
	for (int i = 0;i < n;++i)
	{
		printf("%d\n",listj[i] + 1);
	}
	bool uniq = true;
	for (int i = 0; i < n - 1; ++i)
	{
		bool setted = false;
		for (int lose : win[listj[i]])
		{
			if (lose == listj[i + 1])
			{
				setted = true;
			}
		}
		if (!setted)uniq = false;
	}
	if (uniq)
	{
		printf("0\n");
	}
	else
	{
		printf("1\n");
	}
	return 0;
}

Measured memory_bytes: 3404
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }

int main() {
	ios::sync_with_stdio(false);
	int n; cin >> n;
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	string s;
	cin >> s;
	auto judge = [&](int x, int y) {
		--x; --y;
		for(int i = x; i + 1 < y; ++i) if(s[i] == '#' && s[i + 1] == '#') return false;
		return true;
	};
	bool ok = judge(a, c) && judge(b, d);
	if(ok && d < c) {
		bool pos = false;
		for(int i = b - 1; i <= d - 1; ++i) if(s[i] == '.' && s[i - 1] == '.' && s[i + 1] == '.')
			pos = true;
		ok &= pos;
	}
	cout << (ok ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 764
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
#include <random>
#include <time.h>
//#include <boost/multiprecision/cpp_int.hpp>



using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const double EPS = 1e-10;
long long const MOD = 1000000007;

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for (int i = 0;i < 60; i++) {
        if (n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

void fastInput() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int main(void) {
    int N; cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    vector<int> C(N-1);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        A[i]--;
    }
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }
    for (int i = 0; i < N-1; i++) {
        cin >> C[i];
    }

    int ans = B[A[0]];
    for (int i = 1; i < N; i++) {
        ans += B[A[i]];
        if (A[i] - 1 == A[i-1]) {
            ans += C[A[i-1]];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 888
# include <bits/stdc++.h>
using namespace std;
long long int a[2005];
long long int price[2005];
 
int main()
{
	long long int N,x,maxi=0,Ans=0;
	scanf("%lld %lld",&N,&x);
 
	for (long long int i = 0; i < N; ++i)
	{
		scanf("%lld",a+i);
		price[i]=a[i];
	}
	for (int i = 0; i < N; ++i)
	{
		long long int maxi=0;

		for (int j = 0; j < N; ++j)
			if(a[j]<price[(i+j)%N])
				price[(i+j)%N]=a[j];
		maxi=i*x;
		for (int j = 0; j < N; ++j)
			maxi+=price[j];
		if(Ans==0)
			Ans=maxi;
		else
			Ans=min(Ans,maxi);
	}
	printf("%lld\n", Ans);
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using lli = int_fast64_t;
using ulli = uint_fast64_t;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugst(x) auto xt = x;cerr << #x << " : {";for(int i=0;i<x.size();i++){ cerr << xt.top() << ", ";xt.pop();}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl

const lli MOD = 1000000007;
const lli LIMIT = 1000000000000000000 * 5;
const int tenfive = 100000;

int main() {
	int N;
	cin >> N;
	vector<int> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	auto vc = v;
	int color = 1000;
	int s = 0;
	for (int i = 0; i < N-1; i++) {
		if (vc[i] == vc[i + 1]) {
			vc[i + 1] = color;
			color--;
			s++;
		}
	}
	int m = 0;
	for (int i = N-1; i > 0; i--) {
		if (v[i] == v[i - 1]) {
			v[i - 1] = color;
			color--;
			m++;
		}
	}
	cout << min(s, m) << endl;
	return 0;
}



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

#define INF 1145141919
#define MAX_N 114514
#define MAX_LOOP 5000

int x[MAX_N], pass[MAX_N], shortest[MAX_N];
int n;

void _set(int p) {
	int loop;
	int cx;
	for (int i = 0; i < p; i++) {
		loop = 0;
		cx = i;
		while (x[cx] != 0) {
			cx += x[cx];
			loop++;
			if (loop >= MAX_LOOP) {
				pass[i] = INF;
				goto E;
			}
		}
		pass[i] = cx;
	E:;
	}
}

int shortestpath(int p) {
	for (int i = 0; i < p; i++) { shortest[i] = INF; }
	shortest[0] = 0;
	for (int i = 0; i < 500; i++) {
		for (int j = 0; j < p; j++) {
			if (shortest[j] != INF) {
				for (int k = 1; k <= 6; k++) {
					if (pass[j + k] != INF) {
						shortest[pass[j + k]] = min(shortest[pass[j + k]], shortest[j] + 1);
					}
				}
			}
		}
	}
	return shortest[p - 1];
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	_set(n);
	cout << shortestpath(n) << endl;
	return 0;
}

Measured memory_bytes: 2336
#include <iostream>
#include <string>
typedef long long int ll;
#define rep(i,k,n) for(int i=k;i<n;++i)

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::string s,t;
    std::cin >> s;
    std::cin >> t;
    std::string ans="No";
    if(t.size()-s.size()==1){
        s.push_back(t[t.size()-1]);
        if(s==t){
            ans="Yes";
        }
    }
    
    std::cout << ans << std::endl;
    return 0;
}

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

using namespace std;

bool exist[2021];

int main() {
    int n;
    cin >> n;
    string  s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'O' && s[i + 1] == 'X') {
            ++ans;
            ++i;
        } else if (s[i] == 'X' && s[i + 1] == 'O') {
            ++ans;
            ++i;
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 3348
#include "bits/stdc++.h"
#define ed cout<<"\n";
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define All(obj) (obj).begin(),(obj).end()

using namespace std;


int main() {
	speed;
	int n;
	cin >> n;
	vector<int >a(n);
	int sum = 0;
	rep(i, n) {
		cin >> a[i];
		sum += a[i];
	}
	int mini = sum;
	int fst = 0;
	rep(i, n) {
		fst += a[i];
		mini = min(mini, abs(fst-(sum - fst)));
	}
	cout << mini;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;

int main() {
    int A, B, C;
    

    cin >> A >> B >> C;

    int nums[3] = {A, B, C};
    sort(nums, nums+3);
    int max_num = nums[2];

    int min_num = nums[0];
    int mid_num = nums[1];

    int count = 0;
    bool over_flag = false;

    REP(i, 60){
        if (mid_num == max_num){
            break;
        }

        min_num += 1;
        mid_num += 1;
        count += 1;        
    }

    REP(i, 60){
        if (min_num == max_num){
            break;
        }

        if (min_num > max_num){
            over_flag = true;
            break;
        }

        min_num += 2;
        count += 1;        
    }

    if (over_flag){
        count += 1;
    }

    cout << count << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int a = 0, b = 0, x, y, n, i;
	for (;;){
		scanf("%d", &n);
		if (n == 0)
			break;
		for (i = 0; i < n; i++){
			scanf("%d %d", &x, &y);
			if (x > y){
				a += x + y;
			}
			else if (x == y){
				a += x;
				b += y;
			}
			else
				b += x + y;
		}
		printf("%d %d\n", a, b);
		a = 0;
		b = 0;
	}
	return 0;
}

Measured memory_bytes: 1028
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<int,int>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
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;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
int dp[3005][3005];
int main(){
string s,t;
cin>>s>>t;
int n=s.size(),m=t.size();
for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(s[i]==t[j])chmax(dp[i+1][j+1],dp[i][j]+1);
        else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
    }
}
int d=dp[n][m];
string ans={};
while(1){
    if(d==0)break;
    if(n>0&&dp[n-1][m]==d)n--;
    else if(m>0&&dp[n][m-1]==d)m--;
    else if(n>0&&m>0){
           n--;m--;d--;
           ans.push_back(s[n]);
    }
}
reverse(all(ans));
cout<<ans<<endl;
}


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

using namespace std;


void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (auto& x: a) {
        cin >> x;
        x--;
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == i) {
            res++;
            i++;
        }
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 640
from collections import deque


def main():
    K = int(input())
    q = deque([(1, 1)])
    visited = [False] * K
    while len(q):
        n, s = q.popleft()
        if visited[n]:
            continue
        visited[n] = True
        if n == 0:
            print(s)
            return
        q.appendleft((n*10 % K, s))
        q.append(((n+1) % K, s+1))


if __name__ == "__main__":
    main()


Measured memory_bytes: 42864
from collections import deque, defaultdict


def bfs(graph, start):

    queue = deque([start])
    visited = set()
    visited.add(start)
    parent = defaultdict(int)
    parent[start] = 0
    while queue:
        current_vertex = queue.popleft()
        for v in graph[current_vertex]:
            if v not in visited:
                queue.append(v)
                visited.add(v)
                parent[v] = current_vertex
    return parent

N, M = map(int, input().split())
paths = [tuple(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
for A, B in paths:
    graph[A].add(B)
    graph[B].add(A)

parent = bfs(graph, 1)

print('Yes')
for k, v in sorted(parent.items()):
    if v != 0:
        print(v)


Measured memory_bytes: 164512
#include<iostream>
using namespace std;
int main()
{
	for(int i=0 ; i<4 ; ++i){
		int t,n;
		cin >> t >> n;
		if(t==1){
			cout << 6000*n << endl;
		}else if(t==2){
			cout << 4000*n << endl;
		}else if(t==3){
			cout << 3000*n << endl;
		}else{
			cout << 2000*n << endl;
		}
	}
	return 0;
}

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

int main(){
  int N,T;
  cin>>N;
  T=N;
  int sum=0;
  while(N>0){
    sum+=N%10;
    N/=10;
    }
  if (T%sum==0)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 3568
#include<bits/stdc++.h>
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.begin(),v.end()
#define sz(x) (int)sz.size()
#define PB push_back
#define PI 3.1415926535897932384626433832795
#define what(x) cout<<#x<<" is "<<x<<endl;
using namespace std;

#ifdef LOCAL//ONLINE_JUDGE
#include "D:\c_c++\template.h"
#else
#define debug(...) 42
#endif

ll powmod(ll a,ll b,ll mod) {
    ll res=1;a%=mod;
    for(;b;b>>=1){
        if(b&1)res=res*a%mod;
			a=a*a%mod;
    }
    return res;
}
const int mxn = 2e5+10;
vector<ll> pre(mxn),dp(mxn);
const ll M = 998244353;
ll prefix(ll l,ll r,ll n){
	if(r<0){
		return 0;
	}
	if(l>n){
		return 0;
	}
	if(l<0){
		l=0;
		r=min(n,r);
	}
	if(r>n){
		r=n;
		l=max(l,0LL);
	}
	debug(r,l);
	if(l>0)
	return ((pre[r]-pre[l-1])%M+M)%M;
	return pre[r]%M;
}

void solve(){
	ll n,k;
	cin>>n>>k;
	dp[1]=1;
	pre[1]=1;
	vector<array<ll,2>> vp;
	for(int i=0,x,y;i<k;i++){
		cin>>x>>y;
		vp.push_back({x,y});
	}
	for(ll i=2;i<=n;i++){
		ll sum=0;
		for(int j=0;j<k;j++){
			sum=(sum+prefix(i-vp[j][1],i-vp[j][0],i))%M;
		}
		dp[i]=sum;
		pre[i]=(pre[i-1]+dp[i])%M;
		debug(dp[i],pre[i]);
	}
	cout<<dp[n]<<'\n';
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
//    #ifdef LOCAL
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    #endif
    int tc=1;
    // cin>>tc;
    while(tc--)solve();
}


Measured memory_bytes: 6228
//  Created by liszt on 2019/07/21.
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n; cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    
    int cost=INT_MAX;
    for(int i=-100;i<=100;i++){
        int costi=0;
        for(int j=0;j<n;j++){
            costi+=(a[j]-i)*(a[j]-i);
        }
        cost=min(cost,costi);
    }
    cout<<cost<<endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
a = list(map(int,input().split()))
min_num = min(a)
max_num = max(a)
ans = []

for num in range(min_num,max_num+1):
    count = 0
    for i in a:
        count += (i-num)**2
    ans.append(count)
print(min(ans))

Measured memory_bytes: 3060
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m),n||m){
        vector<int>V(n,0);
        int cnt=0,b=m;
        while(true){
            cnt%=n;
            if(b){
                b--;
                V[cnt]++;
            }
            else{
                b=V[cnt];
                V[cnt]=0;
            }
            if(V[cnt]==m){
                printf("%d\n",cnt);
                break;
            }
            cnt++;


        }
    }

}

Measured memory_bytes: 1032