akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();

        int xs[] = new int[n];
        for (int i = 0; i < n; i++) {
            xs[i] = in.nextInt();
        }

        int ys[] = new int[m];
        for (int i = 0; i < m; i++) {
            ys[i] = in.nextInt();
        }

        String ans = "No War";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (xs[i] >= ys[j] || xs[i] >= y || ys[j] <= x) {
                    ans = "War";
                } 
            }
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
stack<string>a;

int main()
{
    string b;
    while(cin>>b)
    {
        if(b!="+"&&b!="-"&&b!="*")
            a.push(b);
        else{
            long d=stol(a.top());
            a.pop();
            long c=stol(a.top());
            a.pop();
            string cd;
            if(b=="+"){
                cd=to_string(c+d);
            }
            else if(b=="-")
                cd=to_string(c-d);
            else
                cd=to_string(c*d);
            a.push(cd);
        }
    }
    cout<<a.top()<<endl;
    return 0;
}



Measured memory_bytes: 3284
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

const ll MOD = 1e9+7;
template<class Type>
Type solve(Type res = Type()){
    string N; ll K;
    cin >> N >> K;

    int L = (int)N.length();

    auto dp = make_v<ll>(L+1,2,K+1);

    dp[0][0][0] = 1;
    for(int i = 0; i < L;i++){
        for(int j = 0; j < 2;j++){
            for(int k = 0; k <= K;k++){
                if(dp[i][j][k] == 0) continue;

                int lim = j ? 9 : N[i]-'0';

                for(int l = 0; l <= lim;l++){
                    if(k+(l!=0) > K) continue;

                    dp[i+1][j|(l<lim)][k+(l!=0)] += dp[i][j][k];
                }
            }
        }
    }

    res = dp[L][0][K] + dp[L][1][K];
    return res;
}
int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    // solve<ll>(0);
    cout << fixed << setprecision(12) << solve<ll>() << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define MAX(list) std::max(list)
#define MIN(list) std::min(list)

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

using ll = long long;
using namespace std;

int main() {
    int X, A;
    cin >> X >> A;
    if (X < A) {
        cout << 0 << endl;
    }
    else {
        cout << 10 << endl;
    }

    return 0;
}

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

long long n;
vector<long long> lim;

long long solve();

int main() {
  cin >> n;
  lim.resize(5);
  for(int i = 0; i < 5; ++i) cin >> lim[i];
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long ans = 0, nown = lim[0];
  for(int i = 0; i < 5; ++i) nown = min(nown, lim[i]);
  return 4 + n / nown + (n % nown != 0);
}

Measured memory_bytes: 256
use std::cmp::{max, min};
use std::collections::{HashMap, HashSet, VecDeque};
use std::io::{stdin, Read};
use std::str::FromStr;

// https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn main() {
    let k = read::<i32>();
    let x = read::<i32>();

    for i in x - k + 1..k + x {
        if (x - k + 1 < i) {
            print!(" ")
        }
        print!("{}", i)
    }
    println!()
}


Measured memory_bytes: 4352
def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, K = read_ints()
    has_snacks = [False]*N
    for _ in range(K):
        _ = read_int()
        A = read_ints()
        for a in A:
            has_snacks[a-1] = True
    return has_snacks.count(False)


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 9180
#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
  }

  //   vector<set<int> > setV;
  //   setV.push_back(set({A[0], B[0]}));
  //   set<int> appear{A[0], B[0]};
  //   for (int i = 1; i < M; i++) {
  //     for (auto itr = setV.begin(); itr != setV.end(); itr++) {
  //         if((*itr).find(A[i]) != (*itr).end()){

  //         }
  //     }
  //   }

  vector<int> group(N, -1);
  int groupId = 1;
  int groupCount = 0;
  set<int> appear;

  for (int i = 0; i < M; i++) {
    int a = A[i] - 1;
    int b = B[i] - 1;
    appear.insert(a);
    appear.insert(b);
    if (group[a] == group[b] && group[a] != -1) {
      continue;
    }
    if (group[a] == -1 && group[b] == -1) {
      group[a] = groupId;
      group[b] = groupId;
      groupCount++;
      groupId++;
      continue;
    }
    if (group[a] == -1) {
      group[a] = group[b];
      continue;
    }
    if (group[b] == -1) {
      group[b] = group[a];
      continue;
    }
    if (group[a] < group[b]) {
      int tmp = group[b];
      group[b] = group[a];
      for (int j = 0; j < N; j++) {
        if (group[j] == tmp) {
          group[j] = group[a];
        }
      }
      groupCount--;
      continue;
    } else {
      int tmp = group[a];
      group[a] = group[b];
      for (int j = 0; j < N; j++) {
        if (group[j] == tmp) {
          group[j] = group[b];
        }
      }
      groupCount--;
      continue;
    }
  }

  int result = (N - appear.size()) + (groupCount - 1);
  cout << result << endl;

  return 0;
}

Measured memory_bytes: 8472
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int A[3][3];
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> A[i][j];
    }
  }
  int N;
  cin >> N;
  while (N--) {
    int b;
    cin >> b;
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        if (A[i][j] == b) {
          A[i][j] = -1;
        }
      }
    }
  }
  bool isbingo = false;
  for (int i = 0; i < 3; i++) {
    int sum = 0;
    for (int j = 0; j < 3; j++) {
      sum += A[i][j];
    }
    isbingo |= sum == -3;
  }
  for (int j = 0; j < 3; j++) {
    int sum = 0;
    for (int i = 0; i < 3; i++) {
      sum += A[i][j];
    }
    isbingo |= sum == -3;
  }
  isbingo |= A[0][0] == -1 && A[1][1] == -1 && A[2][2] == -1;
  isbingo |= A[2][0] == -1 && A[1][1] == -1 && A[0][2] == -1;
  cout << (isbingo ? "Yes" : "No") << endl;
  return 0;
}

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

int main(){
  int n, m;
  std::cin >> n;
  set<string> u;
  for (int i = 0; i < n; i++) {
    string s;
    std::cin >> s;
    u.insert(s);
  }
  std::cin >> m;
  string t;
  bool lock = 1;
  for (int i = 0; i < m; i++) {
    std::cin >> t;
    if(u.find(t) != u.end()){
      if(lock == 1){
        std::cout << "Opened by " << t << std::endl;
      }else{
        std::cout << "Closed by " << t << std::endl;
      }
      lock = 1 - lock;
    }else{
      std::cout << "Unknown " << t << std::endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1232
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	int n,i,j;
	cin>>n;
	int t[n],x[100000],y[100000];
	for(i=1;i<=n;i++){
		cin>>t[i];
		cin>>x[i]>>y[i];
		j=fabs(x[i]-x[i-1])+fabs(y[i]-y[i-1]);
		if(t[i]-t[i-1]<j||(t[i]-t[i-1]-j)%2!=0){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	
	return 0;
} 

Measured memory_bytes: 1408
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

#define MAX_H 20
#define MAX_W 20
#define MAX_T 150

struct Data{
    int n,c,s,t;
    Data(){}
    Data(int n,int c,int s,int t) :
        n(n),c(c),s(s),t(t) {}

    bool operator < (const Data &d)const{
        return n < d.n;
    }
};

int H,W,LIMIT;
int memo[MAX_H][MAX_W][MAX_T][1<<8];
vector<Data> v;
char field[MAX_H][MAX_W];
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};

bool inField(int x,int y){
    return (0 <= x && x < W && 0 <= y && y < H);
}

bool check(int nt,int idx){
    return (v[idx].s <= nt && nt < v[idx].t);
}

int solve(int x,int y,int t,int p){
    if(t == LIMIT) return 0;
    int &res = memo[x][y][t][p];
    if(res != -1) return res;
    int S = p,cost = 0;
    for(int i = 0 ; i < 4 ; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!inField(nx,ny)) continue;
        if(field[ny][nx] == '.') continue;
        int x = field[ny][nx]-'0';
        if(S >> x & 1) continue;
        if(check(t,x)){
            S |= (1<<x);
            cost += v[x].c;
        }
    }
    for(int i = 0 ; i < 4 ; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!inField(nx,ny)) continue;
        if(field[ny][nx] != '.') continue;
        res = max(res,solve(nx,ny,t+1,S)+cost);
    }
    return res;
}

int main(){
    int sx,sy,N;
    while(cin >> W >> H, W){
        for(int i = 0 ; i < H ; i++){
            for(int j = 0 ; j < W ; j++){
                cin >> field[i][j];
                if(field[i][j] == 'P'){
                    sx = j; sy = i;
                    field[i][j] = '.';
                }
            }
        }
        LIMIT = 0;
        cin >> N;
        v.clear(); v.resize(N);
        for(int i = 0 ; i < N ; i++){
            cin >> v[i].n >> v[i].c >> v[i].s >> v[i].t;
            LIMIT = max(LIMIT,v[i].t);
        }
        LIMIT++;
        memset(memo,-1,sizeof(memo));
        cout << solve(sx,sy,0,0) << endl;
    }
    return 0;
}

Measured memory_bytes: 63100
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

class Union_Find
{
	std::vector<LL>per;
	std::vector<LL>rank;
public:
	void init(LL size)
	{
		rep(i, size)
		{
			per.push_back(i);
			rank.push_back(0);
		}
	}
	LL get_per(LL x)
	{
		if (x == per[x]) return x;
		return per[x] = get_per(per[x]);
	}
	bool is_same_per(LL x, LL y)
	{
		return get_per(x) == get_per(y);
	}
	void togett(LL x, LL y)
	{
		int x_per = get_per(x), y_per = get_per(y);
		if (x_per == y_per) return;
		if (rank[x_per] < rank[y_per]) per[x_per] = y_per;
		else
		{
			per[y_per] = x_per;
			if (rank[x_per] == rank[y_per]) ++rank[x_per];
		}
	}
};

LL N, M, ans;
Union_Find tree;

int main()
{
	in >> N >> M;
	std::vector<LL>p(N), x(M), y(M);
	tree.init(N + 1);
	rep(i, N) in >> p[i];
	rep(i, M)
	{
		in >> x[i] >> y[i];
		tree.togett(x[i], y[i]);
	}
	rep(i, N)
	{
		if (tree.is_same_per(i + 1, p[i])) ++ans;
	}
	out << ans << std::endl;
	return 0;
}


Measured memory_bytes: 4340
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){
			
			
			int N = scan.nextInt();
			int K = scan.nextInt();
			int Q = scan.nextInt();
			
			int[] A = new int[Q];//i番目に誰が正解したか
			int[] point = new int[N];//N人それぞれ何回正解したか?最初は皆０
			String[] kuria = new String[N];//N人それぞれがクリアしたかどうか
			
			for(int i =0;i<Q;i++) {
				A[i] = scan.nextInt();	
			}
			
			for(int i =0;i<Q;i++) {//Q回正解したのでポイント整理 
				point[A[i]-1]++;//i番目に正解した人に一ポイント	
			}
			
			for(int i = 0;i<N;i++) {//N人のポイント調整
				point[i]=point[i]+K-Q;
				if(point[i]>0) {
					kuria[i] = "Yes";
				}else{
					kuria[i] = "No";
				}
				
			}
			
			for(int i = 0;i<N;i++) {
				System.out.println(kuria[i]);
			}
			
			
			
			
			
			
		}
		
		
	}
		

}


Measured memory_bytes: 62508
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 998244353

using namespace std;
typedef pair<llint, llint> P;

llint n, k;
llint l[15], r[15];
llint dp[200005], sum[200005];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n>> k;
	for(int i = 1; i <= k; i++) cin >> l[i] >> r[i];
	
	dp[1] = 1, sum[1] = 1;
	for(int i = 2; i <= n; i++){
		for(int j = 1; j <= k; j++){
			llint L = i-r[j], R = i-l[j];
			if(R <= 0) continue;
			L = max(L, 1LL);
			dp[i] += sum[R] - sum[L-1] + mod, dp[i] %= mod;
		}
		sum[i] = sum[i-1] + dp[i], sum[i] %= mod;
	}
	cout << dp[n] << endl;
	
	return 0;
}

Measured memory_bytes: 6700
//SAIKH SERAJ FAHIM, CSE-19-HSTU, BANGLADESH.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int n,i,ac=0,wa=0,tle=0,re=0;
    cin>>n;
    cin.ignore();
    for(i=0; i<n; i++)
    {
        getline(cin,s);
        if(s=="AC")
            ac++;
        else if(s=="WA")
            wa++;
        else if(s=="TLE")
            tle++;
        else if(s=="RE")
            re++;
    }
    cout<<"AC "<<"x "<<ac<<endl;
    cout<<"WA "<<"x "<<wa<<endl;
    cout<<"TLE "<<"x "<<tle<<endl;
    cout<<"RE "<<"x "<<re<<endl;
    return 0;
}


Measured memory_bytes: 3628
no="UNRESTORABLE"

s=input()
t=input()
ans=list(s[:])
hatena=[ s[i]=="?" for i in range(len(s))]

left=0 ; right=len(s)
while right>=len(t):
    for i in range(right-len(t), right):
        if s[i]!="?" and s[i]!=t[i-right+len(t)]:
            break
    else:
        # hatena[right-len(t):right]=[i*2 for i in hatena[right-len(t):right]]
        ans[right-len(t):right]=list(t) 
        print( ("".join(ans)).replace("?","a") )
        exit()
    right-=1



# for i in range(len(hatena)):
#     if i==0:
#         s+=s[i]
#     elif i==1:
#         s+="a"
print(no)



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

long long N, H[100009], dp[109][109], mod = 1000000007; vector<pair<int, int>>vec[100009];

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 63; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> H[i];
	H[0] = 1; H[N + 1] = 1;
	for (int i = 1; i <= N; i++) {
		long long minx = (1LL << 60);
		for (int j = i; j <= N; j++) {
			minx = min(minx, H[j]);
			if (H[i - 1] < minx && minx > H[j + 1]) vec[j].push_back(make_pair(i, minx - max(H[i - 1], H[j + 1])));
		}
	}
	dp[0][1] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 1; j <= N; j++) {
			long long K = 0; for (int k = 0; k < vec[i + 1].size(); k++) { if (vec[i + 1][k].first >= j) K += vec[i + 1][k].second; }
			long long L = modpow(2, K, mod);
			dp[i + 1][j] += dp[i][j] * L; dp[i + 1][j] %= mod;
			long long K1 = 0; for (int k = 0; k < vec[i + 1].size(); k++) { if (vec[i + 1][k].first >= i + 1) { K1 += vec[i + 1][k].second; } }
			long long L1 = modpow(2, K1, mod);
			dp[i + 1][i + 1] += dp[i][j] * L1; dp[i + 1][i + 1] %= mod;
		}
	}
	long long sum = 0;
	for (int i = 1; i <= N; i++) sum += dp[N][i];
	cout << sum%mod << endl;
	return 0;
}

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

int main(){
  string s,t;
  std::cin >> s>>t;

  int m=100000;
  rep(i,s.size()-t.size()+1){
    string temp=s.substr(i,t.size());
    // std::cout << temp << '\n';

    int cnt=0;
    rep(k,t.size()){
      if(temp[k]!=t[k])cnt++;
    }
    m=min(m,cnt);

  }
  std::cout << m << '\n';


  return 0;
}


Measured memory_bytes: 3636
n, m = map(int, input().split())
ka = [list(map(int, input().split())) for i in range(n)]
l = [True] * m
for i in ka:
  K = i[0]
  for j in range(m):
    if j+1 not in i[1:]:
      l[j] = False
print(l.count(True))

Measured memory_bytes: 9128
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;

public class Main {
	static List<Integer> path;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String s = br.readLine();
		StringBuilder sb = new StringBuilder(s);
		br.close();

		int cnt = 0;
		for (int i = 0; i < n; i++) {
			char c = s.charAt(i);
			if (c == '(') {
				while (cnt < 0) {
					sb.insert(0, '(');
					cnt++;
				}
				cnt++;
			} else {
				cnt--;
			}
		}

		while (cnt < 0) {
			sb.insert(0, '(');
			cnt++;
		}
		while (cnt > 0) {
			sb.append(')');
			cnt--;
		}
		System.out.println(sb.toString());
	}
}


Measured memory_bytes: 21332
while True:
    h, w = map(int, input().split())
    if h == w == 0:
        break

    for i in range(h):
        chess = ''
        for j in range(w):
            if (i + j) % 2 == 0:
                chess += '#'
            else:
                chess += '.'
        print(chess)
    print()


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

using namespace std;

int main()
{
    #ifdef LOCAL_EXEC
    #else
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif // LOCAL_EXEC
    long long int n,i,j,result=0;
    cin>>n;
    long long int A[n][2];
    map<long long int,long long int>mt;
    for(i=0;i<n;i++){
        cin>>A[i][0];
        A[i][1]=i-A[i][0];
        mt[A[i][0]+i]+=1;
        result+=mt[A[i][1]];
    }
    cout<<result;
    return 0;
}


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

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,n) for(int i=1;i<=(int)(n);i++)
#define rep3(i,n) for(int i=0;i<=(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
#define repll(i,n) for(ll i=0;i<(ll)(n);i++)
#define repll2(i,n) for(ll i=1;i<=(ll)(n);i++)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define INF (int)1e9  //
#define LINF (ll)4e18  //
#define MOD (int)(1e9)+7
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define PI 3.1415926535898

//------------------------------------------------------

int main() {
    int n;
    cin >> n;
    int t[n];
    rep(i, n) cin >> t[i];
    int m;
    cin >> m;

    rep(i, m) {
        int p, x;
        cin >> p >> x;

        int time = 0;

        rep(j, n) {
            if (j == p - 1) time += x;
            else time += t[j];
        }
        cout << time << endl;
    }
    return 0;
}



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

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define mem(a, b) memset(a, b, sizeof(a))
#define MOD 1000000007
#define MAX (int) 1e9
#define PI 3.141592653589793238462643383279502884

template <typename T, typename U>
T max(T x, U y) {
    return x > y ? x : y;
}

template <typename T, typename U>
T min(T x, U y) {
    return x < y ? x : y;
}

template<typename T>
void debug(string msg, T t) {
	cout << msg << ": " << t << "\n";
}

template<typename T>
T abs(T a, T b) {
	return a > b ? a - b : b - a;
}


int toDigit(char c) { return c - '0'; }

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0); 

	ll n;
	string name;

	cin >> n;

	ll p = 26, bound = p;
	for(int i = 1; i <= 11; i++) {
		if(n <= bound) {
			n -= (bound - p + 1); // if n is 1 it refers to first name within range
			// determine each of the i characters of the name
			for(int c = i - 1; c >= 0; c--) {
				p /= 26;
				int l = n / p;
				name += 'a' + l;
				n -= l * p;
			}
			break;
		}

		p *= 26;
		bound = bound + p;
	}

	cout << name << "\n";

	return 0;
}

Measured memory_bytes: 3652
#include<iostream>//头文件
using namespace std;
int n,m,dir[8][2]={{1,0},{0,1},{-1,0},{0,-1},{-1,-1},{1,-1},{1,1},{-1,1}};//8个方向
char mp[101][101];
void dfs()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int num=0;
            if(mp[i][j]=='#')cout<<'#';
            if(mp[i][j]=='.')
            {
                for(int k=0;k<8;k++)
                {
                    int x0=i+dir[k][0];
                    int y0=j+dir[k][1];
                    if(mp[x0][y0]=='#')num++;
                }
            cout<<num;
            }

        }
        cout<<endl;
    }

}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[i][j];
    dfs();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000000;
bool prime[N+1];
int main(){
  for(int i=2;i<=N;++i) prime[i] = true;
  for(int i=2;i<=N;++i) if(prime[i]) for(int j=2;i*j<=N;++j) prime[i*j] = false;
  int a,d,n;
  while(cin>>a>>d>>n,a||d||n){
    int cnt = 0;
    while(true){
      if(prime[a]) ++cnt;
      if(cnt>=n) break;
      a+=d;
    }
    cout << a << endl;
  }
  return 0;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int field[505][505];
int K;

int main() {
    //cout.precision(10);
    cin >> K;
    if(K == 1) {
        cout << "1" << endl << "1" << endl;
        return 0;
    }
    int n = ((K + 3) / 4) * 2;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            field[i][j] = (i + j) % n + 1;
            if((i % 2) == 0) field[i][j] += n;
            if(field[i][j] > K) field[i][j] -= n;
        }
    }
    cout << n << endl;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cout << field[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}


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

int main()
{
    int n;
    int a;
    scanf("%d", &n);

    int x = n * 100 / 108;
    

    if(x * 108 / 100 == n) a = x;

    else if(x * 108 / 100 < n){
        x++;
        if(x * 108 / 100 == n) a = x;
        else {
            printf(":(\n");
            return 0;
        }
    }
    else if(x*108/100 > n){
        x--;
        if(x * 108 / 100 == n) a = x;
        else
        {
            printf(":(\n");
            return 0;
        }
    }

    printf("%d\n", a);

    return 0;
}


Measured memory_bytes: 128
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

using ll = long long;
using ull = unsigned long long;

int main() {
    char c;
    cin >> c;
    cout << (char)(c + 1) << endl;

    return 0;
}

Measured memory_bytes: 256
main :: IO ()
main = do
  n <- getLine
  putStrLn $ solve n

solve :: String -> String
solve s = if n `mod` n' == 0
          then "Yes"
          else "No"
  where
    n :: Int
    n = read s
    zero = fromEnum '0'
    n' = sum $ map (\c -> fromEnum c - zero) s


Measured memory_bytes: 508
package main

import "fmt"

func min(ms []int) int {
	min_value := ms[0]
	for _, v := range ms {
		if v < min_value {
			min_value = v
		}
	}
	return min_value
}

func main() {
	var n, x int
	fmt.Scan(&n, &x)
	ms := make([]int, n)
	for i := range ms {
		fmt.Scan(&ms[i])
		x -= ms[i]
	}
	fmt.Println(n + x/min(ms))
}


Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int N, W;
struct Item {
	int v;
	int w;
};
int C[10005];
Item items[102];
int main() {
	int v, w;

	cin >> N >> W;
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &v, &w);
		items[i].v = v;
		items[i].w = w;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = items[i].w; j <= W; j++) {
			//if (j - items[i].w >= 0) {
				C[j] = max(C[j], C[j - items[i].w] + items[i].v);
			//}
		}
	}
	cout << C[W] << endl;
	return 0;
}


Measured memory_bytes: 3272
import Control.Applicative

main = do [n,m] <- (map read) . words <$> getLine
          vecs <- map (map read) . (map words) . lines <$> getContents
          let as = take n vecs
          let bs = concat $ drop n vecs
          putStr . unlines . map show $ solve as bs

solve :: [[Int]] -> [Int] -> [Int]
solve as bs = map (innerProduct bs) as

innerProduct :: [Int] -> [Int] -> Int
innerProduct xs ys = sum $ zipWith (*) xs ys
          

Measured memory_bytes: 7516
package main

import (
	"fmt"
	"strings"
)

type line struct {
	s string
}

func main() {
	var n int
	n = 1
	// fmt.Scan(&n, &m)

	lines := []line{}
	for i := 0; i < n; i++ {
		l := line{}
		fmt.Scan(&l.s)
		lines = append(lines, l)
	}
	// fmt.Println(lines)

	test := func(lines []line) string {
		for _, l := range lines {
			rest := l.s
			maxI := -2
			terms := []string{"dream", "dreamer", "erase", "eraser"}
			for maxI != -1 {
				maxI = -1
				for _, t := range terms {
					i := strings.LastIndex(rest, t)
					if len(rest)-len(t) <= i && maxI < i {
						maxI = i
					}
				}
				if -1 < maxI {
					rest = rest[:maxI]
				}
			}
			if rest == "" {
				return "YES"
			}
		}
		return "NO"
	}
	fmt.Println(test(lines))
}


Measured memory_bytes: 1280
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptor/reversed.hpp>
#include<boost/operators.hpp>
#include<boost/dynamic_bitset.hpp>
namespace adaptor = boost::adaptors;
template<class T>using p_queue = std::priority_queue<T, std::vector<T>, std::greater<>>;

void Main()
{
	int P, Q, R;
	std::cin >> P >> Q >> R;
	std::cout << P + Q + R - std::max({ P,Q,R }) << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

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

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

	int N;
	cin>>N;

	int flag = 0,temp;

	while(N!=0)
	{
		temp = N % 10;

		if(temp == 7)
		{
			flag = 1;
			break;
		}

		N = N/10;
	}

	if(flag)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;

	return 0;
}

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

int main() {
  int n, k;
  cin >> n >> k;
  
  int min = 1;
  for (int i = 0; i < n; i++) {
    if (min * 2 < min + k) {
      min = min * 2;
    } else {
      min = min + k;
    }
  }
  
  cout << min << endl;
}

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

units = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]

dp = [100000]*(N+1)
dp[0] = 0
dp[1] = 1

for i in range(2, N+1):
    for u in units:
        p = i-u
        if p >= 0:
            dp[i] = min(dp[p]+1, dp[i])

print(dp[N])

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

int main(){
  string s[2];
  for(int i = 0; i < 2; i++) cin >> s[i];
  if(s[0][0] == s[1][2] && s[0][2] == s[1][0] && s[0][1] == s[1][1]) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
    for(auto i=begin(v); i != end(v); ++i){
        if(i !=begin(v)) os << ' ';
        os << *i;
    }
    return os;
}

int main(){
    ll H,W,A[100000],C[107][107];
    cin >> H >> W;
    ll N;
    cin >> N;
    rep(i,N){
        cin >> A[i];
    }
    ll k=0,c=0;
    rep(i,H){
        rep(j,W){
            if(i%2==0){
                C[i][j]=k+1;
                c++;
            }
            else{
                C[i][W-j-1]=k+1;
                c++;
            }
            if(c==A[k]){
                k++;
                c=0;
            }
        }
    }
    rep(i,H){
        rep(j,W){
            cout << C[i][j];
            if(j!=W-1){
                cout << " ";
            }
        }
        cout << endl;
    }
}

Measured memory_bytes: 512
#include<iostream>
#include<bits/stdc++.h>
#include <stdio.h>
#include<unordered_map>
#define Amr_Abdelazim ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define vll vector<ll>
#define vvll vector<vector<ll> >
#define vpll vector<pair<ll,ll> >
#define P complex<ld>
#define X real()
#define Y imag()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define rep(i,n)   for(int i=0;i<n;i++)
#define repp(i,s,n)   for(int i=s;i<=n;i++)
#define print(v) {for(auto i:v)cout<<i<<" ";cout<<"\n";}
#define mkp make_pair
#define clr(ar,v) memset(ar,v,sizeof(ar));
#define TC ll amr_abdelazim;cin>>amr_abdelazim;while(amr_abdelazim--)
#define popcnt(x) __builtin_popcount(x)
#define EPS 1e-9
#define INF 1000000000000000009
#define heeer cout<<"heeeeeeeeer\n";
using namespace std;
//freopen("output.txt", "w", stdout);
//freopen("input.txt", "r", stdin);
const int mod = 1000000007;
const double pi = acos(-1);
class cmp{
public:
	bool operator() (ll &A, ll &B){
		return A > B;
	}
};
bool by_sec(const pll &a, const pll &b){
	if ((abs(a.first) == abs(b.first)))
		return (abs(a.second) < abs(b.second));
	return (abs(a.first) < abs(b.first));
}
bool byth(const tuple<ll, ll, ld>& a, const tuple<ll, ll, ld>& b){
	return (get<2>(a) < get<2>(b));
}
ld dist(P a, P b){
	return (ld)abs(a - b);
}
ll fact[1000009], inv[1000009];
ll fp(ll a, ll b){
	if (b == 0)
		return 1;
	ll ans = fp(a, b / 2);
	ans = (ans * ans)%mod;
	if (b % 2 != 0)
		ans = (ans * (a%mod))%mod;
	return ans;
}
void FacInv(ll n){
	fact[0] = inv[0] = 1;
	for (ll i = 1; i <= n; i++)
	{
		fact[i] = ((i%mod) * fact[i - 1] % mod) % mod;
		inv[i] = fp(fact[i], mod - 2);
	}
}
ll ncr(ll n, ll r){
	return (((fact[n] * inv[r]) % mod) * inv[n - r]) % mod;
}
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a%b);
}
ll max(ll a, ll b){
	if (a >= b)return a;
	else return b;
}
ll min(ll a, ll b){
	if (a <= b)return a;
	else return b;
}
const int N = 2 * 1000000 + 9;


int main()
{
	Amr_Abdelazim
		ll n;
	cin >> n;
	ll ans = INF;
	rep(i, n){
		ll a;
		cin >> a;
		ll c = 0;
		while (a % 2 == 0)a /= 2, c++;
		ans = min(c, ans);
	}
	cout << ans << "\n";
	
		
	return 0;
}


Measured memory_bytes: 3668
#include <iostream>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
	int k;
	cin >> k;
	for (int i = 0; i < k; i++) {
		cout << "ACL";
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3636
import java.util.*

fun main(args: Array<String>) {
    val scanner = Scanner(System.`in`)
    val k = scanner.nextInt()
    val a = scanner.nextInt()
    val b = scanner.nextInt()
    for(i in a..b){
        if(i%k === 0){
            println("OK")
            return
        }
    }
     println("NG")
}

Measured memory_bytes: 36400
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x)(x).begin(), (x).end() // 昇順ソート
#define rall(v)(v).rbegin(), (v).rend() // 降順ソート
#define INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair < ll, ll >
#define F first
#define S second
const int MOD = 1000000007;
template < class T > bool chmax(T & a,const T & b) { if (a < b) { a = b; return true; } return false; }
template < class T > bool chmin(T & a,const T & b) { if (a > b) { a = b; return true; } return false; }
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main() {
    double N,K;cin >> N >> K;
    double sum = 0;

    int lim = min(N,K-1);

    for(int i = 1;i <= N;i++){
        double tmp = 1.0;
        double t = i;
        double ct = 0;
        while(t < K){
            t *= 2.0;
            tmp /= 2.0;
        }
        sum += tmp;
    }
    sum /= N;

    cout << std::fixed << std::setprecision(15) << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}




int main() {

	string S;
	cin >> S;
	if (S.at(S.size() - 1) == 's')cout << S + "es" << endl;
	else cout << S + "s" << endl;



}

Measured memory_bytes: 3600
import collections

n = int(input())
s = input()
#反対から種類を記録
#ls = []
#for i in range(n-1,-1,-1):
#    if s[i] not in ls:
#        ls.append(i)
dic_forward = {}
for i in range(n-2):
    if int(s[i]) not in dic_forward.keys():
        #print(i,s[i])
        dic_forward[int(s[i])] = i

dic_backward = {}
for i in range(n-1,1,-1):
    if int(s[i]) not in dic_backward.keys():
        dic_backward[int(s[i])] = i

for i in range(10):
    if i not in dic_forward.keys():
        dic_forward[i] = -1
for i in range(10):
    if i not in dic_backward.keys():
        dic_backward[i] = -1

#print(dic_forward)
#print(dic_backward)
ans = 0

for i in range(10):
    for j in range(10):
        if dic_forward[i] >= 0 and dic_backward[j] >= 0:
            if dic_backward[j] - dic_forward[i] > 1:
                #print(i,j)
                #print(collections.Counter(s[dic_forward[i]+1:dic_backward[j]]))
                #print(len(collections.Counter(s[dic_forward[i]+1:dic_backward[j]])))
                ans += len(collections.Counter(s[dic_forward[i]+1:dic_backward[j]]))
print(ans)


Measured memory_bytes: 42332
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
AB = [LIST() for _ in range(M)]

graph = defaultdict(list)
for A, B in AB:
	graph[A-1].append(B-1)
	graph[B-1].append(A-1)


color = [0] *  N
color[0] = 1
if N == 3:
	print(0)
	sys.exit()
	
def DFS(node):
	if not 0 in color:  # 2部グラフ
			w = color.count(1)
			print(w*(N-w)-M)
			sys.exit()
	for i in graph[node]:
		if not color[i]:
			color[i] = color[node] * (-1)
			DFS(i)
		else:
			if color[i] == color[node]:  # 2部グラフでない
				print(N*(N-1)//2-M)
				sys.exit()
		
DFS(0)


Measured memory_bytes: 59952
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        int[] a = new int[n];
        Arrays.setAll(a, i -> sc.nextInt());
        sc.close();
        int max = k + a[0] - a[n-1];
        for (int i = 0; i < n-1; i++) {
            if (max < a[i+1]-a[i]) max = a[i+1]-a[i];
        }
        System.out.println(k-max);
    }
}

Measured memory_bytes: 67144
n=int(input())
a=[int(input()) for _ in range(2**n)]
for i in range(0, n):
    for j in range(0, 2**n, 2**(i+1)):
        k = j+2**i
        if a[j] > a[k]:
            a[j] -= a[k]
        elif a[j] < a[k]:
            a[j] = a[k] - a[j]
print(a[0])

Measured memory_bytes: 13472
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

class LCA {
private:
    static const int MAX_LOG = 20;
    const int n;
    Graph G;
    VV par;
    V depth;
public:
    LCA(int _n) : n(_n), G(_n), par(MAX_LOG, V(_n)), depth(_n) {}
    // undirected
    void addEdge(int a, int b) {
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
    // ??????????????±?????¨???1????????????????±???????
    void dfs(int v, int p, int d) {
        par[0][v] = p;
        depth[v] = d;
        for (auto nxt : G[v]) {
            if (nxt != p) {
                dfs(nxt, v, d + 1);
            }
        }
    }
    // ????????????2^k????????????????±?????????????
    void setPar() {
        // 0????????¨??????1????????????????±???????
        dfs(0, -1, 0);

        // 2^i????????????????±???????
        rep(i, MAX_LOG - 1) {
            rep(j, n) {
                if (par[i][j] == -1) {
                    par[i + 1][j] = -1;
                } else {
                    par[i + 1][j] = par[i][par[i][j]];
                }
            }
        }
    }
    int lca(int a, int b) {
        // ??????a??¨b?????±???????????????
        if (depth[a] > depth[b]) {
            swap(a, b);
        }
        rep(i, MAX_LOG) {
            if ((depth[b] - depth[a]) >> i & 1) {
                b = par[i][b];
            }
        }
        if (a == b) return a;

        // ??¶???????????´????????§a, b????????????
        rrep(i, MAX_LOG) {
            if (par[i][a] != par[i][b]) {
                a = par[i][a];
                b = par[i][b];
            }
        }
        // a??¨b???1????????????????????´????????????
        return par[0][a];
    }
};

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

    int n;
    scanf("%lld", &n);
    LCA lca(n);
    rep(i, n) {
        int k;
        scanf("%lld", &k);
        rep(j, k) {
            int c;
            scanf("%lld", &c);
            lca.addEdge(i, c);
        }
    }

    lca.setPar();

    int Q;
    scanf("%lld", &Q);
    rep(i, Q) {
        int u, v;
        scanf("%lld%lld", &u, &v);
        printf("%lld\n", lca.lca(u, v));
    }
}

Measured memory_bytes: 28396
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int ar[110];
    int con=0;
    for(int i=0;i<n;i++)
    {
        cin>>ar[i];
    }

     for(int j=0;j<n-1;j++)
    {
        //cout<<"ar[i]="<<ar[i]<<" ar[i+1]="<<ar[i+1]<<" i="<<i<<endl;
        if(ar[j]==ar[j+1])
        {
            //cerr << "entering" << endl ;

            //cout<<"ar[i+1]="<<ar[i+1]<<" i+1 ="<<i+1<<endl;
            if(ar[j+1]!=j+1)
            {
                ar[j+1]=j+1;
                //cout<<"if ar[k+1]="<<ar[k+1]<<endl<<endl;
                con++;
            }
            else
            {
                ar[j+1]=n-j-1;
                //cout<<"else ar[i+1]="<<ar[k+1]<<endl;
                con++;
            }
        }


    }

    //cout<<endl;
    cout<<con<<endl;

    return 0;
}


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

using namespace std;

int n,s[110],sum,mi = 1000;

int main()
{
	cin >> n;
	for(int i = 0;i < n;i++)
	{
		cin >> s[i];
		sum += s[i];
		if(s[i] < mi && (s[i] % 10 != 0)) mi = s[i];
	}
	
	if(sum % 10 != 0)
	{
		cout << sum << endl;
	}
	else if(mi == 1000) cout << 0 << endl;
	else cout << sum - mi << endl;
	
	return 0;
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)

int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n,0);
    rep(i, n) {
        scanf("%d", &a[i]);
    }

    rep (i, n) {
        if (i != 0) {
            int x = i;
            while (a[x-1] > a[x] && x >= 1) {
                swap(a[x], a[x-1]);
                x--;
            }
        }
        rep(i, n) {
            printf("%d", a[i]);
            if (i != n - 1) printf(" ");
        }
        printf("\n");
    }
}


Measured memory_bytes: 3188
#include <stdio.h>
#include <math.h>

int main(void)
{
	int num, x, i, j, n;
	int a[200];

	scanf("%d", &num);

	for (i = 0; i < num; i++) {
		scanf("%d", &a[i]);
	}

	for (n = 0; n < num; n++) {
		printf("%d", a[n]);

		if (n != num - 1) {
			putchar(' ');
		}
		else {
			putchar('\n');
		}
	}

	for (i = 1; i < num; i++) {
		x = a[i];
		j = i - 1;
		while (j >= 0 && a[j] > x) {
			a[j+1] = a[j];
			j--;
		}
		a[j + 1] = x;

		for (n = 0; n < num; n++) {
			printf("%d", a[n]);
			
			if (n != num - 1) {
				putchar(' ');
			}
			else {
				putchar('\n');
			}
		}
	}

	return 0;
}


Measured memory_bytes: 2064
#include <bits/stdc++.h>
using namespace std;
#define QOEINDIEDIS freesteed
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int n,C,s,t,c;
map<int,vector<PII> > ma;
multiset<PII> mt;
vector<int> tab;
void solve(){
	cin>>n>>C;
	rep(i,0,n){
		cin>>s>>t>>c;
		ma[c].pb({s,t});
	}
	for(auto &m:ma){
		sort(all(m.se));
		rep(i,1,sz(m.se))
			if(m.se[i].fi!=m.se[i-1].se)mt.insert(m.se[i-1]);
			else m.se[i].fi = m.se[i-1].fi;
		mt.insert(m.se[sz(m.se)-1]);
	}
	for(auto m:mt){
		int f=0;
		for(int i=0;i<sz(tab);i++)
			if(m.fi>tab[i]){
				tab[i] = m.se;
				f = 1;
				break;
			}
		if(!f)tab.pb(m.se);
	}
	cout<<sz(tab); 
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//caset{
		solve();
	//}
  	return 0;
}

Measured memory_bytes: 6016
n=int(input())
a=list(map(int,input().split()))

#      0  1  2  3  evn odd
# kevn +  -  +  -   +   -
# kodd -  +  -  +   -   +

def kf(a,flag,n):
    a0=a[0]*flag
    if a0<=0:
        kevn=1-a0
        sevn=1
    elif a0>0:
        kevn=0
        sevn=a0

    for i in range(1,n):
        ai=a[i]*flag
        if i%2==0:
            if sevn+ai<=0:
                kevn=kevn+1-(ai+sevn)
                sevn=1
            elif sevn+ai>0:
                kevn=kevn
                sevn=sevn+ai
        elif i%2==1:
            if sevn+ai<0:
                kevn=kevn
                sevn=sevn+ai
            elif sevn+ai>=0:
                kevn=kevn+1+(ai+sevn)
                sevn=-1
    return kevn

print(min(kf(a,1,n),kf(a,-1,n)))
            

Measured memory_bytes: 14468
# -*- coding: utf-8 -*-
a, b, c, d = map(int, input().split())
if(c < b):
    if(d <= b):
        if(d <= a):
            time = 0
        elif(c < a):
            time = d - a
        else:
            time = d - c
    elif (c < a):
        time = b - a
    else:
        time = b - c
else:
    time = 0
print(time)


Measured memory_bytes: 3060
#include <stdio.h>

int main() {
    long int k,a,b;
    scanf("%ld %ld %ld\n",&k,&a,&b);
    if ((b - a < 3) || (k < a + 1)) {
        printf("%ld\n",k+1);
    } else {
        k -= (a + 1);
        if (k % 2 == 0) {
            k = k / 2;
            printf("%ld\n",b + (b - a) * k);
        } else {
            k -= 1;
            printf("%ld\n",b + (b - a) * k / 2 + 1);
        }
    }
}

Measured memory_bytes: 888